An intersection theorem for four sets (Q2383002)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An intersection theorem for four sets |
scientific article |
Statements
An intersection theorem for four sets (English)
0 references
5 October 2007
0 references
Recently the author [J. Comb. Theory, Ser. A 113, 547--550 (2006; Zbl 1088.05041)] conjectured that if \(r\geq d\geq 3\), \(\mathcal F\subseteq\{A\subseteq\{1,\dots,n\}: | A| =r\}\), and for any distinct \(A_1,\dots,A_d\in\mathcal F\) either \(| \bigcup_{i=1}^dA_i| >2r\) or \(\bigcap_{i=1}^d A_i\not=\emptyset\), then \(| \mathcal F| \leq\binom{n-1}{r-1}\) (and equality holds only if \(\bigcap_{F\in \mathcal F}F\not=\emptyset\)) provided that \(n\) is sufficiently large (e.g., \(n\geq rd/(d-1)\)). In the case \(d=3\), this was essentially proved by \textit{P. Frankl} and \textit{Z. Füredi} [Combinatorica 3, 341--349 (1983; Zbl 0529.05001)]. In the paper under review, the author confirms the conjecture for \(d=4\). The proof needs an auxiliary stability result.
0 references
Extremal set theory
0 references
intersection family
0 references
Erdős-Ko-Rado theorem
0 references