A degree version of the Hilton–Milner theorem

Peter Frankl, Jie Han, Hao Huang, Yi Zhao

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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 (n−1k−1)−(n−k−1k−1)+1 members. One extremal family HMn,k consists of a k-set S and all k-subsets of [n] containing a fixed element x∉S and at least one element of S. We prove a degree version of the Hilton–Milner theorem: if n=Ω(k2) and F is a non-trivial intersecting family of k-subsets of [n], then δ(F)≤δ(HMn.k), where δ(F) denotes the minimum (vertex) degree of 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.

Original languageEnglish
Pages (from-to)493-502
Number of pages10
JournalJournal of Combinatorial Theory. Series A
Volume155
DOIs
Publication statusPublished - Apr 2018
Externally publishedYes

Keywords

  • Erdős–Ko–Rado theorem
  • Hilton–Milner theorem
  • Intersecting families

Fingerprint

Dive into the research topics of 'A degree version of the Hilton–Milner theorem'. Together they form a unique fingerprint.

Cite this