IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Intersecting $k$-uniform families containing all the $k$-subsets of a given set

  • Jan. 30, 2015
  • 2:30 p.m.
  • LeConte 312

Abstract

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 ${[n] \choose k} \subseteq \mathcal{F} \subseteq {[m] \choose 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\H{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, or $m$ sufficiently large.

Joint work with Bor-Liang Chen, Kuo-Ching Huang, and Ko-Wei Lih ( http://arxiv.org/abs/1304.1861 ).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC