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
    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
    0 references

    Identifiers