pith. machine review for the scientific record. sign in

arxiv: 1703.03896 · v2 · pith:WCE4U6VHnew · submitted 2017-03-11 · 🧮 math.CO

A degree version of the Hilton--Milner theorem

classification 🧮 math.CO
keywords mathcalfamilytheoremdegreedeltaelementintersectingsubsets
0
0 comments X
read the original 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\H{o}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=\Omega(k^2)$ and $\mathcal{F}$ is a non-trivial intersecting family of $k$-subsets of $[n]$, then $\delta(\mathcal{F})\le \delta(\mathcal{HM}_{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\H{o}s--Ko--Rado theorem.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.