An intersection theorem for four sets (Q2383002)

From MaRDI portal





scientific article; zbMATH DE number 5197736
Language Label Description Also known as
default for all languages
No label defined
    English
    An intersection theorem for four sets
    scientific article; zbMATH DE number 5197736

      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