Intersecting $k$-Uniform Families Containing all the $k$-Subsets of a Given Set

  • Wei-Tian Li
  • Bor-Liang Chen
  • Kuo-Ching Huang
  • Ko-Wei Lih
Keywords: intersecting family, cross-intersecting family, Erdős-Ko-Rado, Milner-Hilton, Kneser graph


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.

Author Biographies

Wei-Tian Li, National Chung Hsing University
Department of Applied Mathematics
Bor-Liang Chen, National Taichung University of Science and Technology
Department of Business Administration
Kuo-Ching Huang, Providence University
Department of Financial and Computational Mathematics
Ko-Wei Lih, Academia Sinica
Institute of Mathematics
Article Number