Stability versions of Erdős-Ko-Rado type theorems via isoperimetry

DOI10.4171/JEMS/915zbMATH Open1429.05198arXiv1604.02160MaRDI QIDQ2279508FDOQ2279508

Authors: David Ellis, Nathan Keller, Noam Lifshitz 

Publication date: 12 December 2019

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: ErdH{o}s-Ko-Rado (EKR) type theorems yield upper bounds on the sizes of families of sets, subject to various intersection requirements on the sets in the family. Stability versions of such theorems assert that if the size of a family is close to the maximum possible size, then the family itself must be close (in some appropriate sense) to a maximum-sized family. In this paper, we present an approach to obtaining stability versions of EKR-type theorems, via isoperimetric inequalities for subsets of the hypercube. Our approach is rather general, and allows the leveraging of a wide variety of exact EKR-type results into strong stability versions of these results, without going into the proofs of the original results. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on $t$-intersecting families of $k$-element subsets of $1,2,ldots.n$ (for $k<fracnt+1$), and to show that, somewhat surprisingly, all these results hold when the intersection requirement is replaced by a much weaker requirement. Other examples include stability versions of Frankl's recent result on the ErdH{o}s matching conjecture, the Ellis-Filmus-Friedgut proof of the Simonovits-S'{o}s conjecture, and various EKR-type results on $r$-wise (cross)-$t$-intersecting families.

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

Recommendations

• Stability analysis for \(k\)-wise intersecting families
• On the stability of some Erdős-Ko-Rado type results
• Stability for vertex isoperimetry in the cube
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• On a biased edge isoperimetric inequality for the discrete cube

zbMATH Keywords

isoperimetrydiscrete Fourier analysiscross-intersecting familiesAhlswede-Khachatrian theoremstability versionErdős-Ko-Rado theoremErdős matching conjecture

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• A note on the edges of the n-cube
• Contributions to the geometry of Hamming spaces
• The complete nontrivial-intersection theorem for systems of finite sets
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• The complete intersection theorem for systems of finite sets
• On the hardness of approximating minimum vertex cover
• On Russo's approximate zero-one law
• The probabilistic method
• Transference for the Erdős-Ko-Rado theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intersection theorems for systems of finite sets
• Title not available (Why is that?)
• The exact bound in the Erdős-Ko-Rado theorem
• On the stability of the Erdős-Ko-Rado theorem
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Erdös–Ko–Rado Theorem—22 Years Later
• Almost isoperimetric subsets of the discrete cube
• Sharp thresholds of graph properties, and the $k$-sat problem
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Thresholds and Expectation Thresholds
• Intersecting Families are Essentially Contained in Juntas
• Set systems without a simplex or a cluster
• Pairwise intersections and forbidden configurations
• Shadows and intersections: Stability and new proofs
• On the measure of intersecting families, uniqueness and stability
• Assignment of Numbers to Vertices
• The size of a hypergraph and its matching number
• A product version of the Erdős-Ko-Rado theorem
• Improved bounds for Erdős' matching conjecture
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Intersection Properties of Systems of Finite Sets
• Set Systems with No Singleton Intersection
• An approximate zero-one law
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Cross \(t\)-intersecting integer sequences from weighted Erdős-Ko-Rado
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• Weighted multiply intersecting families
• Triangle-intersecting families of graphs
• On ``stability in the Erdős-Ko-Rado theorem
• The structure of large intersecting families
• Structure and stability of triangle-free set systems
• A multiply intersecting Erdős-Ko-Rado theorem -- the principal case
• Stability analysis for \(k\)-wise intersecting families
• Probabilities for Intersecting Systems and Random Subsets of Finite Sets
• Proof of an intersection theorem via graph homomorphisms
• A survey of Turán problems for expansions
• On a biased edge isoperimetric inequality for the discrete cube
• FKN theorem on the biased cube
• A new short proof of a theorem of Ahlswede and Khachatrian

Cited In (22)

• On set systems without a simplex-cluster and the junta method
• Forbidden intersections for codes
• A structure theorem for almost low-degree functions on the slice
• Degree versions of theorems on intersecting families via stability
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Stability analysis for \(k\)-wise intersecting families
• Nearly perfect matchings in uniform hypergraphs
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Stability for vertex isoperimetry in the cube
• Sharp bounds for the chromatic number of random Kneser graphs
• On symmetric intersecting families
• \(K_4\)-intersecting families of graphs
• A note on large \(H\)-intersecting families
• Stability of Erd\H{o}s-Ko-Rado Theorems in Circle Geometries
• On the union of intersecting families
• On Ramsey numbers for arbitrary sequences of graphs
• Hypergraph removal lemmas via robust sharp threshold theorems
• Strong stability of 3-wise \(t\)-intersecting families
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Invitation to intersection problems for finite sets
• On a biased edge isoperimetric inequality for the discrete cube
• The maximum measure of 3-wise \(t\)-intersecting families

This page was built for publication: Stability versions of Erdős-Ko-Rado type theorems via isoperimetry

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