New results on simplex-clusters in set systems

DOI10.1007/S00493-020-4441-1zbMATH Open1499.05603arXiv2001.01812OpenAlexW3109061622MaRDI QIDQ2236657FDOQ2236657

Authors: Gabriel Currier 

Publication date: 25 October 2021

Published in: Combinatorica (Search for Journal in Brave)

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$).

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

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

zbMATH Keywords

extremal combinatorics\(d\)-cluster\(d\)-simlex\(d\)-simplex-cluster[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Chv%EF%BF%BD%EF%BF%BDtal+%5C%28d%5C%29-simplex+conjecture&go=Go Erd��s-Chv��tal \(d\)-simplex conjecture]

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• Exact solution of some Turán-type problems
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Set systems without a simplex or a cluster
• Proof of a conjecture of Erdős on triangles in set-systems
• A new generalization of the Erdős-Ko-Rado theorem
• On Sperner families satisfying an additional condition
• An intersection theorem for four sets
• An Extremal Set-Intersection Theorem
• Invitation to intersection problems for finite sets
• Set systems with union and intersection constraints
• Erdős--Ko--Rado for three sets
• 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

Cited In (10)

• 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 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)