# zbMATH — the first resource for mathematics

Intersection theorems for systems of finite sets. (English) Zbl 0100.01902
Let $$\{ a_1,...,a_2\}$$ be a system of subsets of a set of finite cardinality $$m$$ such that $$a_\mu \not\subset a_\nu$$ for $$\mu \neq \nu$$. The authors impose an upper limitation $$l$$ on the cardinals of the sets $$a_\nu$$, in symbols $$|a_\nu| \leq l$$, and a lower limitation $$k$$ on the cardinals of the intersection of any two sets $$a_\mu$$ and $$a_\nu$$, in symbols $$|a_\mu a_\nu| \geq k$$, and deduce upper estimates for the number $$n$$. If $$k=1$$ and $$1\leq l \leq {1 \over 2} m$$, then $$n \leq {m-1 \choose l-1}$$, the inequality being strict in case $$|a_\nu| < l$$ for some $$\nu$$. Let $$k \leq l \leq m$$, $$n \geq 2$$ and either $$2l \leq 1+m$$ or $$2l \leq k+m$$, $$|a_\nu| = l$$ for each $$\nu$$. Then (i) either $$|a_1 \cdots a_n| \geq k$$, $$n \leq {m-k \choose l-1}$$ or $$|a_1 \cdots a_n| < k < l < m$$, $$n \leq {m-k-1 \choose l-k-1} {l \choose k}^3;$$ (ii) if $$m \geq k+(l-k){l \choose k}^3$$, then $$n\leq {m-k \choose l-k}$$. Finally, the authors discuss the inequality imposed on $$m$$ in (ii) and present some problems due to the replacement of the condition $$a_\mu \not\subset a_\nu$$ by $$a_\mu \neq a_\nu$$.
Reviewer: A.Salomaa
Show Scanned Page ##### MSC:
 05D05 Extremal set theory
combinatorics
Full Text: