Set systems without a simplex or a cluster (Q532128): Difference between revisions

A \(d\)-simplex on \([n]\) is a collection of \(d+1\) subsets of \(\{1,2,\dots,n\}\) with empty intersection, every \(d\) of which have non-empty intersection; a set system is \(k\)-uniform if all sets in the collection have cardinality \(k\); a collection of \(d+1\) \(k\)-sets with empty intersection and union of size at most \(2k\) is a \(k\)-uniform \(d\)-cluster. Theorem 2.1 addresses conjectures of \textit{V. Chvatal} [``An extremal set-intersection theorem,'' J. Lond. Math. Soc., II. Ser. 9, 355--359 (1974; Zbl 0296.05002)] and \textit{D. Mubayi} [``Erdős-Ko-Rado for three sets,'' J. Comb. Theory, Ser. A 113, No.~3, 547--550 (2006; Zbl 1088.05041)]: For all \(\zeta>0\) and \(d\geq2\), there exist a \(\delta>0\) and integers \(N\), \(T\) such that the following holds for all \(n>N\): If \(\mathcal G\) is a \(k\)-uniform set system on \([n]\), where {\parindent=7mm \begin{itemize}\item[(i)]\(k=\frac n2-t\); \item[(ii)]\(T<t<\left(\frac12-\zeta\right)n\); \item[(iii)]\(| {\mathcal G}| >\left(1-\frac{\delta t}n\right){{n-1}\choose{k-1}}\); \item[(iv)]either \(\mathcal G\) contains no strong \(d\)-simplex or \(\mathcal G\) contains no \(d\)-cluster, then there exists an element \(x\) contained in all members of \(\mathcal G\), so \(| {\mathcal G}| \leq{{n-1}\choose{k-1}}\). \end{itemize}} The main nonuniform result, Theorem 2.3, generalizes a question of Erdős and a result of Milner: Suppose \(d\geq2\), and \(\mathcal G\) is a set system on \([n]\) that contains no \(d\)-simplex. Then, for \(n\) sufficiently large, \(| {\mathcal G}| \leq2^{n-1}+\sum_{i=0}^{d-1}{{n-1}\choose i}\), with equality iff \(\mathcal G\) consists either of all sets containing a fixed element \(x\), or all sets having size at most \(d-1\). Each of these results is proved via a corresponding stability result, which gives structural information on any \(\mathcal G\) whose size is close to the maximum. These stability results rely on results of \textit{P. Frankl} [``Erdős-Ko-Rado theorem with conditions on the maximal degree,'' J. Comb. Theory, Ser. A 46, No.~1--2, 252--263 (1987; Zbl 0661.05002)] and \textit{R. Ahlswede and L. H. Khachatrian} [``The complete intersection theorem for systems of finite sets,'' Eur. J. Comb. 18, No.~2, 125--136 (1997; Zbl 0869.05066)], and strengthen results of \textit{E. Friedgut} [``On the measure of intersecting families, uniqueness and stability,'' Combinatorica 28, No. 5, 503--528 (2008; Zbl 1199.05319)] and \textit{I. Dinur} and \textit{E. Friedgut} [``Intersecting families are essentially contained in juntas,'' Comb. Probab. Comput. 18, No.~1--2, 107--122 (2009; Zbl 1243.05235)].