Intersecting Families are Essentially Contained in Juntas

DOI10.1017/S0963548308009309zbMath1243.05235OpenAlexW2114506516WikidataQ105585041 ScholiaQ105585041MaRDI QIDQ3557506

Irit Dinur, Ehud Friedgut

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548308009309

zbMATH Keywords

Fourier analysisErdős-Ko-Rado theoremBoolean functionintersecting familiesjuntasintersecting subsets

Mathematics Subject Classification ID

Partitions of sets (05A18) Extremal set theory (05D05) Designs and configurations (05B99)

Related Items (37)

Families with no perfect matchings ⋮ TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM ⋮ A simple removal lemma for large nearly-intersecting families ⋮ On sets of subspaces with two intersection dimensions and a geometrical junta bound ⋮ Diversity of uniform intersecting families ⋮ Vertex isoperimetry and independent set stability for tensor powers of cliques ⋮ Approximation by juntas in the symmetric group, and forbidden intersection problems ⋮ On the stability of the Erdős-Ko-Rado theorem ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ The junta method in extremal hypergraph theory and Chvátal's conjecture ⋮ Forbidden intersections for codes ⋮ Fixed-Parameter Algorithms for the Kneser and Schrijver Problems ⋮ A new short proof of the EKR theorem ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ Towards a proof of the Fourier-entropy conjecture? ⋮ Hedetniemi's conjecture is asymptotically false ⋮ The maximum size of intersecting and union families of sets ⋮ Shadows and intersections: Stability and new proofs ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ Diversity ⋮ On symmetric intersecting families ⋮ Kneser graphs are like Swiss cheese ⋮ On the measure of intersecting families, uniqueness and stability ⋮ Set systems without a simplex or a cluster ⋮ A product version of the Erdős-Ko-Rado theorem ⋮ On set systems without a simplex-cluster and the junta method ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Stability versions of Erdős-Ko-Rado type theorems via isoperimetry ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Simple juntas for shifted families ⋮ Invitation to intersection problems for finite sets ⋮ Removal and Stability for Erdös--Ko--Rado ⋮ Vertex-isoperimetric stability in the hypercube ⋮ The unbalance of set systems ⋮ The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family ⋮ Best possible bounds on the number of distinct differences in intersecting families ⋮ Regular intersecting families

Cites Work

• The complete intersection theorem for systems of finite sets
• Critical hypergraphs and interesting set-pair systems
• Boolean functions with low average sensitivity depend on few coordinates
• Cross-intersecting families of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• An approximate zero-one law
• Some Inequalities Concerning Cross-Intersecting Families

This page was built for publication: Intersecting Families are Essentially Contained in Juntas