A degree version of the Hilton-Milner theorem

DOI10.1016/J.JCTA.2017.11.019zbMATH Open1377.05189arXiv1703.03896OpenAlexW2606666068MaRDI QIDQ1689057

Author name not available (Why is that?)

Publication date: 12 January 2018

Published in: (Search for Journal in Brave)

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 ErdH{o}s--Ko--Rado theorem: when $n>2k$, every non-trivial intersecting family of $k$-subsets of $[n]$ has at most $$ members. One extremal family $mathcal{HM}_{n,k}$ consists of a $k$-set $S$ and all $k$-subsets of $[n]$ containing a fixed element $xotinS$ and at least one element of $S$. We prove a degree version of the Hilton--Milner theorem: if $n=Omega(k^2)$ and $mathcalF$ is a non-trivial intersecting family of $k$-subsets of $[n]$, then $delta(mathcalF)ledelta(mathcal{HM}_{n.k})$, where $delta(mathcalF)$ denotes the minimum (vertex) degree of $mathcalF$. Our proof uses several fundamental results in extremal set theory, the concept of kernels, and a new variant of the ErdH{o}s--Ko--Rado theorem.

Full work available at URL: https://arxiv.org/abs/1703.03896

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: A degree version of the Hilton-Milner theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689057)