×

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

MSC:
05D05 Extremal set theory
Keywords:
combinatorics
PDF BibTeX XML Cite
Full Text: DOI