2023/11/03 by Kupavskii, Andrey · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.02246
A family \mathcal C of sets is hereditary if whenever A∈ \mathcal C and B⊂ A, we have B∈ \mathcal C. Chvátal conjectured that the largest intersecting subfamily of a hereditary family is the family of all sets containing a fixed element. This is a generalization of the non-uniform Erdős-Ko-Rado theorem. A natural uniform variant of this question, which is essentially a generalization for the uniform Erdős-Ko-Rado theorem, was suggested by Borg: given a hereditary family \mathcal C, in which all maximal sets have size at least n, what is the largest intersecting subfamily of the family of all k-element sets in \mathcal C? The answer, of course, depends on n and k, and Borg conjectured that for n≥ 2k the it is again the family of all k-element sets containing a singleton. Borg proved this conjecture for n≥ k3. He also considered a t-intersecting variant of the question. In this paper, we improve the bound on n for both intersecting and t-intersecting cases, showing that for n≥ Cktlog2\frac nk and n≥ Cklog k the largest t-intersecting subfamily of the k-th layer of a hereditary family with maximal sets of size at least n is the family of all sets containing a fixed t-element set. We also prove a stability result.