On generalizations of the deBruijn-Erdős theorem
type: Item
instance of: scholarly article
title: On generalizations of the deBruijn-Erdős theorem
zbMATH Open document ID: 0806.05063
DOI: 10.1016/0097-3165(94)90103-1
published in: Journal of Combinatorial Theory. Series A
publication date: 1994-11-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 665838
zbMATH Keywords: de Bruijn-Erdős theorem
zbMATH Keywords: Frankl-Wilson theorem
zbMATH Keywords: Alon-Babai-Suzuki theorem
zbMATH Keywords: method of Blokhuis
author: Hunter Snevily
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: 0097-3165(94)90103-1
OpenAlex ID: W1995921843
cites work: Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems
cites work: Q3339659
cites work: Helly families of maximal size
cites work: A Note on Fisher's Inequality for Balanced Incomplete Block Designs
cites work: Q3693528
cites work: Intersection theorems with geometric consequences
cites work: An extension of a Frankl-Füredi theorem
cites work: An extension of a theorem of the Bruijn and Erdős on combinatorial designs
cites work: A sharp bound for the number of sets that pairwise intersect at \(k\) positive values
description: scientific article; zbMATH DE number 665838