Erdős--Ko--Rado for three sets (Q2368657)

From MaRDI portal





scientific article; zbMATH DE number 5019726
Language Label Description Also known as
default for all languages
No label defined
    English
    Erdős--Ko--Rado for three sets
    scientific article; zbMATH DE number 5019726

      Statements

      Erdős--Ko--Rado for three sets (English)
      0 references
      0 references
      28 April 2006
      0 references
      Let \(k\leq s\leq 3\dot{k}.\) Then \(f(n,k,s)\) denotes the maximum size of family \(\mathcal{F}\subset [ n]^{k\text{ }}\) so that if \(A,B,C\in \mathcal{F}\) satisfy \(\left| A\cup B\cup C\right| \leq s,\) then \( A\cap B\cap C\neq \emptyset .\) The function \(f\) has been introduced by Katona. \textit{P. Frankl} and \textit{Z. Fueredi} [Combinatorica 3, 341--349 (1983; Zbl 0529.05001)] proved that, if \(2k\leq s\leq 3\dot{k},\) and \(n\geq k^{2}+3k,\) then \(f(n,k,s)= \binom{n-1}{k-1}.\) In the paper it is shown that for \(k\geq 3\) and \(n\geq 3k/2\) we have \(f(n,k,2k)=\binom{n-1}{k-1}\) which answers in the affirmative a conjecture by Frankl and Fueredi.
      0 references
      set systems
      0 references
      nontrivial family
      0 references
      Erdős-Ko-Rado
      0 references
      0 references

      Identifiers