On set systems without a simplex-cluster and the junta method

DOI10.1016/J.JCTA.2019.105139MaRDI QIDQ2010639zbMATH OpenOpenAlexWikidataFDO

Authors Noam Lifshitz

Publication date 27 November 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

extremal combinatoricsset systemsjunta method

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: A family $A_0,ldots,A_d$ of $k$-element subsets of $[n]=1,2,ldots,n$ is called a simplex-cluster if $A_{0}capcdotscap{A}_d=varnothing$, $|A_{0}cupcdotscup{A}_d|le2k$, and the intersection of any $d$ of the sets in $A_0,ldots,A_d$ is nonempty. In 2006, Keevash and Mubayi conjectured that for any $d+1leklefracdd+1n$, the largest family of $k$-element subsets of $[n]$ that does not contain a simplex-cluster is the family of all $k$-subsets that contain a given element. We prove the conjecture for all $kgezetan$ for an arbitrarily small $zeta>0$, provided that $nge{n}_0(zeta,d)$. We call a family $A_0,ldots,A_d$ of $k$-element subsets of $[n]$ a $(d,k,s)$-cluster if $A_{0}capcdotscap{A}_d=varnothing$ and $|A_{0}cupcdotscup{A}_d|les$. We also show that for any $zetanleklefracdd+1n$ the largest family of $k$-element subsets of $[n]$ that does not contain a $(d,k,(fracd+1d+zeta)k)$-cluster is again the family of all $k$-subsets that contain a given element, provided that $nge{n}_0(zeta,d)$. Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.

Recommendations

• New results on simplex-clusters in set systems
• Set systems without a simplex or a cluster
• Families of sets with intersecting clusters
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Set systems without a strong simplex

Cites work

• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• A new generalization of the Erdős-Ko-Rado theorem
• An Extremal Set-Intersection Theorem
• An approximate zero-one law
• An intersection theorem for four sets
• Boolean functions with low average sensitivity depend on few coordinates
• Erdős--Ko--Rado for three sets
• Exact solution of some Turán-type problems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting Families are Essentially Contained in Juntas
• Intersection theorems for systems of finite sets
• Invitation to intersection problems for finite sets
• Kneser graphs are like Swiss cheese
• On Sperner families satisfying an additional condition
• On the Fourier tails of bounded functions over the discrete cube
• On the distribution of the Fourier spectrum of Boolean functions
• 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
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• The junta method in extremal hypergraph theory and Chvátal's conjecture
• Unavoidable subhypergraphs: \(\mathbf a\)-clusters

Cited in

(14)

• Unavoidable subhypergraphs: \(\mathbf a\)-clusters
• Simple juntas for shifted families
• New results on simplex-clusters in set systems
• 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
• The junta method in extremal hypergraph theory and Chvátal's conjecture
• Hypergraphs without non-trivial intersecting subgraphs
• Set systems without a 3-simplex
• Note on set systems without a strong simplex
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Families of sets with intersecting clusters
• Unavoidable subhypergraphs: \(\mathbf a\)-clusters

This page was built for publication: On set systems without a simplex-cluster and the junta method

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