Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
From MaRDI portal
Publication:2279508
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 -intersecting families of -element subsets of (for ), 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 -wise (cross)--intersecting families.
Recommendations
Cites work
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 3489128 (Why is no real title available?)
- scientific article; zbMATH DE number 3221072 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- A multiply intersecting Erdős-Ko-Rado theorem -- the principal case
- A new short proof of a theorem of Ahlswede and Khachatrian
- A note on the edges of the n-cube
- A product version of the Erdős-Ko-Rado theorem
- A survey of Turán problems for expansions
- Almost isoperimetric subsets of the discrete cube
- An Erdős-Ko-Rado theorem for cross t-intersecting families
- An approximate zero-one law
- Assignment of Numbers to Vertices
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- Contributions to the geometry of Hamming spaces
- Cross \(t\)-intersecting integer sequences from weighted Erdős-Ko-Rado
- Erdös–Ko–Rado Theorem—22 Years Later
- Erdős-Ko-Rado theorem with conditions on the maximal degree
- FKN theorem on the biased cube
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Improved bounds for Erdős' matching conjecture
- Intersecting Families are Essentially Contained in Juntas
- Intersection Properties of Systems of Finite Sets
- Intersection theorems for systems of finite sets
- Maximally Connected Arrays on the n-Cube
- On Russo's approximate zero-one law
- On ``stability in the Erdős-Ko-Rado theorem
- On a biased edge isoperimetric inequality for the discrete cube
- On the hardness of approximating minimum vertex cover
- On the measure of intersecting families, uniqueness and stability
- On the stability of the Erdős-Ko-Rado theorem
- Optimal Assignments of Numbers to Vertices
- Pairwise intersections and forbidden configurations
- Probabilities for Intersecting Systems and Random Subsets of Finite Sets
- Proof of an intersection theorem via graph homomorphisms
- SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Set Systems with No Singleton Intersection
- Set systems without a simplex or a cluster
- Shadows and intersections: Stability and new proofs
- Sharp thresholds of graph properties, and the $k$-sat problem
- Stability analysis for \(k\)-wise intersecting families
- Structure and stability of triangle-free set systems
- The complete intersection theorem for systems of finite sets
- The complete nontrivial-intersection theorem for systems of finite sets
- The exact bound in the Erdős-Ko-Rado theorem
- The probabilistic method
- The size of a hypergraph and its matching number
- The structure of large intersecting families
- Thresholds and Expectation Thresholds
- Transference for the Erdős-Ko-Rado theorem
- Triangle-intersecting families of graphs
- Weighted multiply intersecting families
Cited in
(22)- The maximum measure of 3-wise \(t\)-intersecting families
- On set systems without a simplex-cluster and the junta method
- A structure theorem for almost low-degree functions on the slice
- Forbidden intersections for codes
- Degree versions of theorems on intersecting families via stability
- Stability analysis for \(k\)-wise intersecting families
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- 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
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)
