Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 407.05006
Autor: Deza, M.; Erdös, Paul; Frankl, P.
Title: Intersection properties of systems of finite sets. (In English)
Source: Proc. Lond. Math. Soc., III. Ser. 36, 369-384 (1978).
Review: The authors use a theorem of Erdös-Rado [P.Erdös and R.Rado, J. London Math. Soc. 35, 85-90 (1960; Zbl 103.27901)] to generalize theorems of Erdös-Ko-Rado [P.Erdös, Chao Ko and R.Rado, Quart. J. Math., Oxford II. Ser. 12, 313-320 (1961; Zbl 100.01902)] , M.Deza [J. Comb. Theory, Ser. B 16, 166-167 (1974; Zbl 263.05007)] , A.Hajnal and R. Rothschild [J. Comb. Theory, Ser. B 15, 359-362 (1973; Zbl 269.05003)] and A.J.W.Hilton and E.C.Milner [Theorem 2 in Quart. J. Math. Oxford II. Ser. 18, 369-384 (1967; Zbl 168.26205)]. X is a finite set with |X| = n, L = {l1,...,lr}, l1 < ... < lr and K = {k1,...,ks}, k1 < ... ks are sets of integers: an (n,L,K)-system is a collection A of subsets of X such that for each A1,A2 in A, |A1| ,|A2| in K and |A1cap A2| in L. Define Ki = K\cap{li*1,...,Li+1}, 0 \leq i \leq r, where l0 = -1, Lr+1 = ks, and k1^* = min{k| k in Ki}. Theorem 7. (1) If |A| > ksc(ks,L)prodi = 2r(n-li)/(ki^*-li) then there exists a set D such that |D| = l1 and D\subseteq A for every A in A . (ii) If |A| > ks32r-1nr-1 then there exists a k in Kr such that li-li-1 divides li+1-li, 2 \leq i \leq r, lr+1 = k. (iii) |A| \leq sumi = 0r\epsilon1prod(n-lj)/(ki^*-lj) where \epsilon = 0or1 according as Ki = Ø or not, and the product is taken over those j, 1 \leq j \leq r for which lj < ki^*.
Theorem 8. If K = {k} and for a fixed q \geq 1 we can find, among any A1,...,Aq+1 in A, two of them A1,Aj such that |Ai\cap Aj| in L, then there is a constant c = c(k,q) such that if |A| > (q-1)prodi = 1r(n-li)/(k-li)+cnr-1 then there are sets D1,...,Ds, each of cardinality l1, such that for every A in A there is an i for which Di\subset A. Further, if qi is the maximum number of sets Aj, 1 \leq j \leq qi, such that Di\subset Aj, but for h\ne i, Dn\not\subset Aj and |Aj1\cap Aj2|\notin L for 1 \leq j1 < j2 \leq q1, then sumi = 1sqi = q. Also, for n > n0(k,q), |A| \leq prodi = 1r(n-li)/(k-li)+0(nr-1).
Theorem 9. If, for any t different members of A, > |A1\cap...\cap At| in L, then there is a constant c = c(k,t) such that if |A| > cnr-1, then there is a set D, |D| = l1, D\subset A for every A in A, and li-li-1 divides li+1-li, 2 \leq i \leq r. Also, for n > n0(k,t), |A| \leq (t-1)prodi = 1r(n-li)/(k-li). The authors ask if it is true that L'\subset L implies the existence, for large enough n, of (n,L,k)- and (n,L',k)-systems A and A', each of maximum cardinaly with A'\subseteqA. They note that Theorem 7 and 9 may be simultaneously generalized to the families called quasi-block-designs by Vera T. Sós [Colloq. int. Teorie comb., Roma 1973, Tomo II, 223-233 (1976; Zbl 261.05022)].
Reviewer: R.K.Guy
Classif.: * 05A05 Combinatorial choice problems
Keywords: intersection properties; systems of finite sets
Citations: Zbl.168.262; Zbl.261.05022; Zbl.103.027; Zbl.100.019; Zbl.263.05007; Zbl.269.05003
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag