Combinatorics Seminar
Yi Zhao
Georgia State
Degree versions of the Erdos-Ko-Rado and Hilton-Milner theorems
Abstract: A family of sets is intersecting if any two members have a nonempty intersection.
We call an intersecting family trivial if all of its members have a nonempty intersection.
Let X be a set of n elements. The celebrated Erdos-Ko-Rado theorem (EKR) says that whenever n\ge 2k, the maximum size of an intersecting family of k-subsets of X is attained by trivial intersecting families. The Hilton-Milner theorem says that the maximum size of a nontrivial intersecting family of k-subsets of X is attained by the family HM, which consists a fixed k-set S and all k-subsets of X that contains a fixed element x\in X-S and at least one element from S. We prove a minimum degree version of the EKR, which implies the EKR as a corollary. We also prove a degree version of the Hilton-Milner theorem for n> 30k^2.
These are joint works with Jie Han and Hao Huang.
Monday March 13, 2017 at 2:00 PM in SEO 612