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

DOI10.1016/J.JCTA.2019.105139zbMATH Open1428.05306arXiv1804.01026OpenAlexW2977312316WikidataQ127179677 ScholiaQ127179677MaRDI QIDQ2010639FDOQ2010639

Authors: Noam Lifshitz 

Publication date: 27 November 2019

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

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.

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

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

zbMATH Keywords

extremal combinatoricsset systemsjunta method

Mathematics Subject Classification ID

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

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Boolean functions with low average sensitivity depend on few coordinates
• Intersection theorems for systems of finite sets
• Title not available (Why is that?)
• Exact solution of some Turán-type problems
• On the distribution of the Fourier spectrum of Boolean functions
• Intersecting Families are Essentially Contained in Juntas
• 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 approximate zero-one law
• 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
• 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
• On the fourier tails of bounded functions over the discrete cube
• Kneser graphs are like Swiss cheese

Cited In (9)

• Unavoidable subhypergraphs: \(\mathbf a\)-clusters
• New results on simplex-clusters in set systems
• Simplex stability
• Set systems without a strong simplex
• Set systems without a simplex or a cluster
• Hypergraphs without non-trivial intersecting subgraphs
• Set systems without a 3-simplex
• Note on set systems without a strong simplex
• Families of sets with intersecting 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)