Set systems without a simplex or a cluster
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)].
- 4-books of three pages
- A homological approach to two problems on finite sets
- A new generalization of Mantel's theorem to \(k\)-graphs
- A new generalization of the Erdős-Ko-Rado theorem
- A Remark on Stirling's Formula
- An Elementary View of Euler's Summation Formula
- An exact Turán result for the generalized triangle
- An Extremal Set-Intersection Theorem
- An intersection theorem for four sets
- Erdős--Ko--Rado for three sets
- Erdős-Ko-Rado theorem with conditions on the maximal degree
- Exact solution of some Turán-type problems
- Intersecting Families are Essentially Contained in Juntas
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Minimal paths and cycles in set systems
- On a Conjecture of Chvátal on m -Intersecting Hypergraphs
- On a hypergraph Turán problem of Frankl
- On a problem of Chvatal and Erdoes on hypergraphs containing no generalized simplex
- On Sperner families satisfying an additional condition
- On the hardness of approximating minimum vertex cover
- On the measure of intersecting families, uniqueness and stability
- On Triple Systems with Independent Neighbourhoods
- Pairwise intersections and forbidden configurations
- Proof of a conjecture of Erdős on triangles in set-systems
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Stability theorems for cancellative hypergraphs
- Structure and stability of triangle-free set systems
- The complete intersection theorem for systems of finite sets
- The number of graphs without forbidden subgraphs
- The Turán number of the Fano plane
- Triple Systems Not Containing a Fano Configuration
- Set systems with union and intersection constraints
- A homological approach to two problems on finite sets
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- On set systems without a simplex-cluster and the junta method
- On the \(d\)-cluster generalization of Erdős-Ko-Rado
- New results on simplex-clusters in set systems
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- Regular intersecting families
- Removal and stability for Erdős-Ko-Rado
- The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
- Unavoidable subhypergraphs: a-clusters
- Set systems without a strong simplex
- A simple removal lemma for large nearly-intersecting families
- Transference for the Erdős-Ko-Rado theorem
- Simplex stability
- Families of sets with intersecting clusters
- A hypergraph regularity method for generalized Turán problems
- On Mubayi's conjecture and conditionally intersecting sets
- An unstable hypergraph problem with a unique optimal solution
- Vertex isoperimetry and independent set stability for tensor powers of cliques
- Exchange properties of finite set-systems
- Hypergraphs without non-trivial intersecting subgraphs
- Triangles in intersecting families
- Unavoidable subhypergraphs: \(\mathbf a\)-clusters
- Set systems without a 3-simplex
- 3-cluster-free families of subspaces
- Some exact and asymptotic results for hypergraph Turán problems in _2-norm
- On the stability of the Erdős-Ko-Rado theorem
- Shadows and intersections: Stability and new proofs
- Note on set systems without a strong simplex
This page was built for publication: Set systems without a simplex or a cluster
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q532128)
