Stability for vertex isoperimetry in the cube
From MaRDI portal
Publication:2200919
Abstract: We prove a stability version of Harper's cube vertex isoperimetric inequality, showing that subsets of the cube with vertex boundary close to the minimum possible are close to (generalised) Hamming balls. Furthermore, we obtain a local stability result for ball-like sets that gives a sharp estimate for the vertex boundary in terms of the distance from a ball, and so our stability result is essentially tight (modulo a non-monotonicity phenomenon). We also give similar results for the Kruskal--Katona Theorem and applications to new stability versions of some other results in Extremal Combinatorics.
Recommendations
- Vertex-isoperimetric stability in the hypercube
- A stability result for the cube edge isoperimetric inequality
- On a biased edge isoperimetric inequality for the discrete cube
- On the structure of subsets of the discrete cube with small edge boundary
- An isoperimetric inequality for the Hamming cube and some consequences
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 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 3221072 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- A generalization of a theorem of Kruskal
- A lower bound on the size of a complex generated by an antichain
- A short proof for a theorem of Harper about Hamming-spheres
- A simple proof of the Kruskal-Katona theorem
- A stability result for the cube edge isoperimetric inequality
- Almost isoperimetric subsets of the discrete cube
- Approximation of biased Boolean functions of small total influence by DNFs
- Boolean functions with low average sensitivity depend on few coordinates
- Compressions and isoperimetric inequalities
- Diversity
- Erdős-Ko-Rado from Kruskal-Katona
- Erdős-Ko-Rado theorem with conditions on the maximal degree
- Families of finite sets with minimum shadows
- Families with no s pairwise disjoint sets
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Improved bounds for Erdős' matching conjecture
- Intersection theorems for systems of finite sets
- KKL, Kruskal-Katona, and Monotone Nets
- Minimum shadows in uniform hypergraphs and a generalization of the Takagi function
- On ``stability in the Erdős-Ko-Rado theorem
- On the measure of intersecting families, uniqueness and stability
- On the stability of the Erdős-Ko-Rado theorem
- On the structure of subsets of the discrete cube with small edge boundary
- Optimal numberings and isoperimetric problems on graphs
- Regular bipartite graphs and intersecting families
- Removal and stability for Erdős-Ko-Rado
- Shadows and intersections: Stability and new proofs
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- Uniqueness in Harper's vertex-isoperimetric theorem
- Vertex-isoperimetric stability in the hypercube
Cited in
(13)- Edge isoperimetric inequalities for powers of the hypercube
- Minimising the total number of subsets and supersets
- Vertex-isoperimetric stability in the hypercube
- Hypercontractivity for global functions and sharp thresholds
- On the structure of subsets of the discrete cube with small edge boundary
- A stability result for the cube edge isoperimetric inequality
- Shotgun reconstruction in the hypercube
- Stability of optimal spherical codes
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- The exact isoperimetric inequality for ternary and quaternary cubes
- An isoperimetric inequality for Hamming balls and local expansion in hypercubes
- Isoperimetric stability in lattices
- Uniqueness in Harper's vertex-isoperimetric theorem
This page was built for publication: Stability for vertex isoperimetry in the cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200919)
