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

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

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

Review text

Let \(\mathcal{F} = \{A_1, \ldots, A_{d+1}\}\) be a family of \(k\)-subsets of an \(n\)-element set such that the intersection of all members is empty. The family is called a \(d\)-simplex if the intersection of any \(d\) members is non-empty. The family is called a \(d\)-cluster if the union of all members is of size \(\leq 2k\). The family is called a \(d\)-simplex-cluster if it is both a \(d\)-simplex and a \(d\)-cluster. The main result of this paper is a solution of the \textit{P. Keevash} and \textit{D. Mubayi}'s conjecture [Combinatorica 30, No. 2, 175--200 (2010; Zbl 1224.05249)] in the range \(4 \leq d+1 \leq k\) and \(n \geq 2k-d+2\). Suppose that the family \(\mathcal{F}\) contains no \(d\)-simplex-cluster. Then it is proved that the size of \(\mathcal{F}\) is at most \(\binom{n-1}{k-1}\). A family attains the maximum size only when it is a star, i.e., there is an element belonging to all members. A consequence of the main result is that the Erdős-Chvátal \(d\)-simplex conjecture holds for all values of \(d\), \(k\) and \(n\) except for very small values of \(n\).

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 a problem of Chvatal and Erdoes on hypergraphs containing no generalized simplex
• On set systems without a simplex-cluster and the junta method
• On Sperner families satisfying an additional condition
• 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

(12)

• A homological approach to two problems on finite sets
• Partitioning ordered hypergraphs
• On set systems without a simplex-cluster and the junta method
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Set systems without a strong simplex
• Simplex stability
• Families of sets with intersecting clusters
• Set systems without a simplex or a cluster
• Hypergraphs without non-trivial intersecting subgraphs
• Triangles in intersecting families
• Some exact and asymptotic results for hypergraph Turán problems in _2-norm
• Note on set systems without a strong simplex

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)