Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.jcta.2017.11.019 | Journal of Combinatorial Theory, Series A |
Keywords | Field | DocType |
Intersecting families,Hilton–Milner theorem,Erdős–Ko–Rado theorem | Discrete mathematics,Set theory,Family of sets,Combinatorics,Erdős–Ko–Rado theorem,Vertex (geometry),Mathematics | Journal |
Volume | ISSN | Citations |
155 | 0097-3165 | 3 |
PageRank | References | Authors |
0.49 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Frankl | 1 | 578 | 126.03 |
| Jie Han | 2 | 31 | 8.16 |
| Hao Huang | 3 | 10 | 2.12 |
| Yi Zhao | 4 | 40 | 6.92 |