Degree versions of theorems on intersecting families via stability

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:168

Article

Kupayskii, Andrey^1,2 

[1] Univ Oxford, Oxford, England

[2] Moscow Inst Phys & Technol, Moscow, Russia

关键词: Intersecting families;    Erdos-Ko-Rado theorem;    Extremal set theory;    Stability;   

DOI  :  10.1016/j.jcta.2019.06.002

来源: Elsevier

【 摘 要 】

For a family of subsets of an n-element set, its matching number is the maximum number of pairwise disjoint sets. Families with matching number 1 are called intersecting. The famous Erdos-Ko-Rado theorem determines the size of the largest intersecting family of k-sets. The problem of determining the largest family of k-sets with matching number s > 1 is known under the name of the Eras Matching Conjecture and is still open for a wide range of parameters. In this paper, we study the degree versions of both theorems. More precisely, we give degree and t-degree versions of the Erdos-Ko-Rado and the Hilton-Milner theorems, extending the results of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in which the degree version of the Erdos Matching Conjecture holds. (C) 2019 Elsevier Inc. All rights reserved.

【 授权许可】

Free