Vertex-isoperimetric stability in the hypercube

DOI10.1016/J.JCTA.2019.105186MaRDI QIDQ2299635zbMATH OpenOpenAlexWikidataFDO

Authors Michał Przykucki, Alexander Roberts

Publication date 21 February 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Harper's theoremstabilityvertex isoperimetry

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: Harper's Theorem states that, in a hypercube, among all sets of a given fixed size the Hamming balls have minimal closed neighbourhoods. In this paper we prove a stability-like result for Harper's Theorem: if the closed neighbourhood of a set is close to minimal in the hypercube, then the set must be very close to a Hamming ball around some vertex.

Recommendations

• Stability for vertex isoperimetry in the cube
• Uniqueness in Harper's vertex-isoperimetric theorem
• An isoperimetric inequality for the Hamming cube and some consequences
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• A stability result for the cube edge isoperimetric inequality

Cites work

• A note on the edges of the n-cube
• Almost isoperimetric subsets of the discrete cube
• Boolean functions with low average sensitivity depend on few coordinates
• 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 3298603 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Intersecting Families are Essentially Contained in Juntas
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Maximally Connected Arrays on the n-Cube
• On ``stability in the Erdős-Ko-Rado theorem
• On the stability of the Erdős-Ko-Rado theorem
• On the structure of subsets of the discrete cube with small edge boundary
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• Shotgun reconstruction in the hypercube
• Stability for vertex isoperimetry in the cube

Cited in

(8)

• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• Edge isoperimetric inequalities for powers of the hypercube
• Stability for vertex isoperimetry in the cube
• Hypercontractivity for global functions and sharp thresholds
• Isoperimetric stability in lattices
• Shotgun reconstruction in the hypercube
• Minimising the total number of subsets and supersets
• Isoperimetric stability in lattices (extended abstract)

This page was built for publication: Vertex-isoperimetric stability in the hypercube

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