Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set (Q396872)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set
scientific article

    Statements

    Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    14 August 2014
    0 references
    Summary: Let \(m, n\), and \(k\) be integers satisfying \(0 < k \leq n < 2k \leq m\). A family of sets \(\mathcal{F}\) is called an \((m,n,k)\)-intersecting family if \(\binom{[n]}{k} \subseteq \mathcal{F} \subseteq \binom{[m]}{k}\) and any pair of members of \(\mathcal{F}\) have nonempty intersection. Maximum \((m,k,k)\)- and \((m,k+1,k)\)-intersecting families are determined by the theorems of Erdős-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases \(n = 2k-1, 2k-2, 2k-3\), and \(m\) sufficiently large.
    0 references
    0 references
    intersecting family
    0 references
    cross-intersecting family
    0 references
    Erdős-Ko-Rado theorem
    0 references
    Milner-Hilton theorem
    0 references
    Kneser graph
    0 references