An Erdos-Ko-Rado theorem for direct products

被引:27
作者
Frankl, P [1 ]
机构
[1] UNIV PARIS 05,F-75005 PARIS,FRANCE
关键词
D O I
10.1006/eujc.1996.0063
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let n(i), k(i) be positive integers, i=1,..., d, satisfying n(i) greater than or equal to 2k(i). Let X(1),...,X(d) be pairwise disjoint sets with \X(i)\ = n(i). Let H be the family of those (k(1) +...+ k(d))-element sets which have exactly k(i) elements in X(i), i = 1,..., d. It is shown that F subset of H is an intersecting family then \H\/\H\less than or equal to max(i)k(i)/n(i), and this is best possible. The proof is algebraic, although in the d = 2 case a combinatorial argument is presented as well.
引用
收藏
页码:727 / 730
页数:4
相关论文
共 8 条
[1]   ERDOS-KO-RADO THEOREM - 22 YEARS LATER [J].
DEZA, M ;
FRANKL, P .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (04) :419-431
[2]   INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].
ERDOS, P ;
RADO, R ;
KO, C .
QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&
[3]  
FRANKL P, 1978, P C MATH SOC J BOLYA, V18, P365
[4]  
FRANZLE O, 1993, SPR S PHY E, V13, P1
[5]  
Katona G. O. H., 1972, J. Comb. Theory Ser. B, V13, P183, DOI [10.1016/0095-8956(72)90054-8, DOI 10.1016/0095-8956(72)90054-8]
[6]   ON THE SHANNON CAPACITY OF A GRAPH [J].
LOVASZ, L .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1979, 25 (01) :1-7
[7]   SOME INTERSECTION-THEOREMS [J].
SALI, A .
COMBINATORICA, 1992, 12 (03) :351-361
[8]   THE EXACT BOUND IN THE ERDOS-KO-RADO THEOREM [J].
WILSON, RM .
COMBINATORICA, 1984, 4 (2-3) :247-257