New results on simplex-clusters in set systems

DOI10.1007/S00493-020-4441-1MaRDI QIDQ2236657zbMATH OpenOpenAlexFDO

Authors Gabriel Currier

Publication date 25 October 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.01812

zbMATH Keywords

extremal combinatorics\(d\)-cluster\(d\)-simlex\(d\)-simplex-clusterErdős-Chvátal \(d\)-simplex conjecture

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: A $d$-simplex is defined to be a collection $A_1,dots,A_{d+1}$ of subsets of size $k$ of $[n]$ such that the intersection of all of them is empty, but the intersection of any $d$ of them is non-empty. Furthermore, a $d$-cluster is a collection of $d+1$ such sets with empty intersection and union of size $le2k$, and a $d$-simplex-cluster is such a collection that is both a $d$-simplex and a $d$-cluster. The ErdH{o}s-Chv'{a}tal $d$-simplex Conjecture from 1974 states that any family of $k$-subsets of $[n]$ containing no $d$-simplex must be of size no greater than $n-1choosek-1$. In 2011, Keevash and Mubayi extended this conjecture by hypothesizing that the same bound would hold for families containing no $d$-simplex-cluster. In this paper, we resolve Keevash and Mubayi's conjecture for all $4led+1lek$ and $nge2k-d+2$, which in turn resolves all remaining cases of the ErdH{o}s-Chv'{a}tal Conjecture except when $n$ is very small (i.e. $n<2k-d+2$).

Recommendations

• Families of sets with intersecting clusters
• Set systems without a strong simplex
• On set systems without a simplex-cluster and the junta method
• Simplex stability
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Set systems without a simplex or a cluster
• Set systems without a 3-simplex
• A homological approach to two problems on finite sets
• Note on set systems without a strong simplex
• The number of congruent simplices in a point set

Cites work

• A new generalization of the Erdős-Ko-Rado theorem
• A simple proof of the Erdős-Chao Ko-Rado theorem
• An Extremal Set-Intersection Theorem
• An intersection theorem for four sets
• Erdős--Ko--Rado for three sets
• Exact solution of some Turán-type problems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Invitation to intersection problems for finite sets
• On Sperner families satisfying an additional condition
• On a problem of Chvatal and Erdoes on hypergraphs containing no generalized simplex
• On set systems without a simplex-cluster and the junta method
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Proof of a conjecture of Erdős on triangles in set-systems
• Set systems with union and intersection constraints
• Set systems without a simplex or a cluster
• The complete intersection theorem for systems of finite sets

Cited in

(10)

• On set systems without a simplex-cluster and the junta method
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Simplex stability
• Set systems without a strong simplex
• Set systems without a simplex or a cluster
• Hypergraphs without non-trivial intersecting subgraphs
• Triangles in intersecting families
• Partitioning ordered hypergraphs
• Note on set systems without a strong simplex
• Families of sets with intersecting clusters

This page was built for publication: New results on simplex-clusters in set systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2236657)