On generalizations of the deBruijn-Erdős theorem (Q1336453): Difference between revisions

Let \(X\) be a finite set with \(n\) elements, and let \(\mathcal L\) be a set of \(k\) positive integers. Frankl and Wilson's celebrated theorem states that if \(\mathcal A\) is a set system on \(X\) and for every pair out of \(\mathcal A\), \(| A_ i\cap A_ j|\in {\mathcal L}\) holds, then \(| {\mathcal A}|\leq \sum^ k_{i=1}{n\choose i}\). This was a generalization of the deBruijn-Erdős theorem, where \({\mathcal L}= \{1\}\), and it was one of the very first results in extremal set theory. The paper under review improves the Frankl-Wilson theorem in many aspects, proving that if \({\mathcal C}= \{A_ i\in {\mathcal A}: | A_ i|\in {\mathcal L}\}\) and if \({\mathcal C}= \varnothing\) or if \(\bigcap_{A_ i\in {\mathcal C}} A_ i\neq\varnothing\) then \(|{\mathcal A}|\leq \sum^ k_{i=1} {n- 1\choose i}\). A modular version is also given. It is a strengthening of the Alon-Babai-Suzuki theorem in many cases. The proof uses linear polynomials of \(n\) variables, utilizing a method of Blokhuis.