





















A family $\mathcal C$ of sets is hereditary if whenever $A\in \mathcal C$ and $B\subset A$, we have $B\in \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\ge 2k$ the it is again the family of all $k$-element sets containing a singleton. Borg proved this conjecture for $n\ge k^3$. 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\ge Ckt\log^2\frac nk$ and $n\ge Ck\log 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。