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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Erdős--Ko--Rado for three sets
scientific article

    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