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

From MaRDI portal





scientific article; zbMATH DE number 6330310
Language Label Description Also known as
default for all languages
No label defined
    English
    Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set
    scientific article; zbMATH DE number 6330310

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

      Identifiers