Stability for vertex isoperimetry in the cube
From MaRDI portal
Publication:2200919
DOI10.1016/J.JCTB.2020.04.009zbMATH Open1448.05199arXiv1807.09618OpenAlexW3028030803MaRDI QIDQ2200919FDOQ2200919
Authors: Eoin Long, Peter Keevash 
Publication date: 24 September 2020
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1807.09618
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
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Extremal set theory (05D05)
Cites Work
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Boolean functions with low average sensitivity depend on few coordinates
- 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?)
- On the stability of the Erdős-Ko-Rado theorem
- A generalization of a theorem of Kruskal
- Families of finite sets with minimum shadows
- A short proof for a theorem of Harper about Hamming-spheres
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal numberings and isoperimetric problems on graphs
- Compressions and isoperimetric inequalities
- Erdős-Ko-Rado from Kruskal-Katona
- Almost isoperimetric subsets of the discrete cube
- Erdős-Ko-Rado theorem with conditions on the maximal degree
- Shadows and intersections: Stability and new proofs
- On the measure of intersecting families, uniqueness and stability
- Improved bounds for Erdős' matching conjecture
- A simple proof of the Kruskal-Katona theorem
- A stability result for the cube edge isoperimetric inequality
- Minimum shadows in uniform hypergraphs and a generalization of the Takagi function
- Approximation of biased Boolean functions of small total influence by DNFs
- On ``stability in the Erdős-Ko-Rado theorem
- Removal and stability for Erdős-Ko-Rado
- Families with no s pairwise disjoint sets
- A lower bound on the size of a complex generated by an antichain
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- KKL, Kruskal-Katona, and Monotone Nets
- Regular bipartite graphs and intersecting families
- On the structure of subsets of the discrete cube with small edge boundary
- Diversity
- Vertex-isoperimetric stability in the hypercube
- Uniqueness in Harper's vertex-isoperimetric theorem
Cited In (13)
- Minimising the total number of subsets and supersets
- Edge isoperimetric inequalities for powers of the hypercube
- 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)
