2019/01/26 by Péter Frankl, Frankl, Peter, Andrey Kupavskii +1
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1901.09278
openalex publication_date 2019/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A family \mathcal F⊂ [n]\choose k is U(s,q) of for any F1,…, Fs∈ \mathcal F we have |F1∪…∪ Fs|≤ q. This notion generalizes the property of a family to be t-intersecting and to have matching number smaller than s. In this paper, we find the maximum |\mathcal F| for \mathcal F that are U(s,q), provided n>C(s,q)k with moderate C(s,q). In particular, we generalize the result of the first author on the Erdős Matching Conjecture and prove a generalization of the Erdős-Ko-Rado theorem, which states that for n> s2k the largest family \mathcal F⊂ [n]\choose k with property U(s,s(k-1)+1) is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in [n]\choose k is U(s,s(k-1)+1).) We investigate the case k=3 more thoroughly, showing that, unlike in the case of the Erdős Matching Conjecture, in general there may be 3 extremal families.