Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
Summary: Erdő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,\dots,n\}\) (for \(k < n/(t+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 Erdős matching conjecture, the Ellis-Filmus-Friedgut proof of the Simonovits-Sós conjecture, and various EKR-type results on \(r\)-wise (cross-)\(t\)-intersecting families.
- 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 approximate zero-one law
- An Erdős-Ko-Rado theorem for cross t-intersecting families
- 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
- 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?)
- 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
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Maximally Connected Arrays on the n-Cube
- On ``stability in the Erdős-Ko-Rado theorem
- On a biased edge isoperimetric inequality for the discrete cube
- On Russo's approximate zero-one law
- 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
- Set Systems with No Singleton Intersection
- Set systems without a simplex or a cluster
- SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
- Shadows and intersections: Stability and new proofs
- Sharp thresholds of graph properties, and the k-sat problem
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- 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
- On a biased edge isoperimetric inequality for the discrete cube
- On symmetric intersecting families
- On set systems without a simplex-cluster and the junta method
- On Ramsey numbers for arbitrary sequences of graphs
- Sharp bounds for the chromatic number of random Kneser graphs
- Stability for vertex isoperimetry in the cube
- A structure theorem for almost low-degree functions on the slice
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
- Degree versions of theorems on intersecting families via stability
- The maximum measure of 3-wise t-intersecting families
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- A note on large H-intersecting families
- Nearly perfect matchings in uniform hypergraphs
- Hypergraph removal lemmas via robust sharp threshold theorems
- On the union of intersecting families
- Stability analysis for \(k\)-wise intersecting families
- \(K_4\)-intersecting families of graphs
- Forbidden intersections for codes
- Strong stability of 3-wise t-intersecting families
- Stability of Erd\H{o}s-Ko-Rado Theorems in Circle Geometries
- Intersecting families with covering number 3
- Testing intersecting and union-closed families
- Stability of large rainbow intersecting families with product measure
- Invitation to intersection problems for finite sets
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)
