A degree version of the Hilton--Milner theorem

Abstract

An intersecting family of sets is trivial if all of its members share a common element. Hilton and Milner proved a strong stability result for the celebrated Erdős--Ko--Rado theorem: when $n>2k$, every non-trivial intersecting family of $k$-subsets of $[n]$ has at most $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)-\left(\genfrac{}{}{0ex}{}{n-k-1}{k-1}\right)+1$ members. One extremal family ${\mathcal{H}\mathcal{M}}_{n,k}$ consists of a $k$-set $S$ and all $k$-subsets of $[n]$ containing a fixed element $x\notin S$ and at least one element of $S$. We prove a degree version of the Hilton--Milner theorem: if $n=\Omega (k^2)$ and $\mathcal{F}$ is a non-trivial intersecting family of $k$-subsets of $[n]$, then $\delta (\mathcal{F})\le \delta ({\mathcal{H}\mathcal{M}}_{n.k})$, where $\delta (\mathcal{F})$ denotes the minimum (vertex) degree of $\mathcal{F}$. Our proof uses several fundamental results in extremal set theory, the concept of kernels, and a new variant of the Erdős--Ko--Rado theorem.

7 pages

References in corpus (1)

• Degree versions of the Erdos-Ko-Rado Theorem and Erdos hypergraph matching conjecture