##
**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 = **{**l_{1},...,l_{r}**}**, l_{1} < ... < l_{r} and K = **{**k_{1},...,k_{s}**}**, k_{1} < ... k_{s} are sets of integers: an (n,L,K)-system is a collection *A* of subsets of X such that for each A_{1},A_{2} in *A*, |A_{1}| ,|A_{2}| in K and |A_{1}cap A_{2}| in L. Define K_{i} = K\cap**{**l_{i}*1,...,L_{i+1}**}**, 0 \leq i \leq r, where l_{0} = -1, L_{r+1} = k_{s}, and k_{1}^* = min**{**k| k in K_{i}**}**. Theorem 7. (1) If |*A*| > k_{s}c(k_{s},L)**prod**_{i = 2}^{r}(n-l_{i})/(k_{i}^*-l_{i}) then there exists a set D such that |D| = l_{1} and D\subseteq A for every A in *A* . (ii) If |*A*| > k_{s}^{3}2^{r-1}n^{r-1} then there exists a k in K_{r} such that l_{i}-l_{i-1} divides l_{i+1}-l_{i}, 2 \leq i \leq r, l_{r+1} = k. (iii) |*A*| \leq **sum**_{i = 0}^{r}\epsilon_{1}**prod**(n-l_{j})/(k_{i}^*-l_{j}) where \epsilon = 0or1 according as K_{i} = Ø or not, and the product is taken over those j, 1 \leq j \leq r for which l_{j} < k_{i}^*.

Theorem 8. If K = **{**k**}** and for a fixed q \geq 1 we can find, among any A_{1},...,A_{q+1} in *A*, two of them A_{1},A_{j} such that |A_{i}\cap A_{j}| in L, then there is a constant c = c(k,q) such that if |*A*| > (q-1)**prod**_{i = 1}^{r}(n-l_{i})/(k-l_{i})+cn^{r-1} then there are sets D_{1},...,D_{s}, each of cardinality l_{1}, such that for every A in *A* there is an i for which D_{i}\subset A. Further, if q_{i} is the maximum number of sets A_{j}, 1 \leq j \leq q_{i}, such that D_{i}\subset A_{j}, but for h\ne i, D_{n}\not\subset A_{j} and |A_{j1}\cap A_{j2}|\notin L for 1 \leq j_{1} < j_{2} \leq q_{1}, then **sum**_{i = 1}^{s}q_{i} = q. Also, for n > n_{0}(k,q), |*A*| \leq **prod**_{i = 1}^{r}(n-l_{i})/(k-l_{i})+0(n^{r-1}).

Theorem 9. If, for any t different members of *A*, > |A_{1}\cap...\cap A_{t}| in L, then there is a constant c = c(k,t) such that if |*A*| > cn^{r-1}, then there is a set D, |D| = l_{1}, D\subset A for every A in *A*, and l_{i}-l_{i-1} divides l_{i+1}-l_{i}, 2 \leq i \leq r. Also, for n > n_{0}(k,t), |*A*| \leq (t-1)**prod**_{i = 1}^{r}(n-l_{i})/(k-l_{i}). 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*'\subseteq*A*. 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