



















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 $\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$ members. One extremal family $\mathcal{HM}_{n, k}$ consists of a $k$-set $S$ and all $k$-subsets of $[n]$ containing a fixed element $x\not\in S$ and at least one element of $S$. We prove a degree version of the Hilton--Milner theorem: if $n=Ω(k^2)$ and $\mathcal{F}$ is a non-trivial intersecting family of $k$-subsets of $[n]$, then $δ(\mathcal{F})\le δ(\mathcal{HM}_{n.k})$, where $δ(\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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。