An isoperimetric inequality for the Hamming cube and some consequences

DOI10.1090/PROC/15105MaRDI QIDQ5117318zbMATHOpenAlexFDO

Authors Jinyoung Park, J. Kahn

Publication date 20 August 2020

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

maximal independent setsstability resultsseparating the cube

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Our basic result, an isoperimetric inequality for Hamming cube $Q_n$, can be written: [ int h_A^�eta dmu ge 2 mu(A)(1-mu(A)). ] Here $mu$ is uniform measure on $V={0,1}^n$ ($=V(Q_n)$); $$; and, for $SsubseteqV$ and $xinV$, [ h_S(x) = �egin{cases} d_{V setminus S}(x) &mbox{ if } x in S, 0 &mbox{ if } x otin S end{cases} ] (where $d_T(x)$ is the number of neighbors of $x$ in $T$). This implies inequalities involving mixtures of edge and vertex boundaries, with related stability results, and suggests some more general possibilities. One application, a stability result for the set of edges connecting two disjoint subsets of $V$ of size roughly $|V|/2$, is a key step in showing that the number of maximal independent sets in $Q_n$ is $(1+o(1))2nex{p}_2[2^{n-2}]$. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work.

Recommendations

• On boundaries and influences
• On a biased edge isoperimetric inequality for the discrete cube
• An inequality for functions on the Hamming cube
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• Note on the number of balanced independent sets in the Hamming cube

Cites work

• scientific article; zbMATH DE number 3503316 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Almost isoperimetric subsets of the discrete cube
• Assignment of Numbers to Vertices
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Counting maximal antichains and independent sets
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• On Russo's approximate zero-one law
• On the structure of subsets of the discrete cube with small edge boundary
• Optimal numberings and isoperimetric problems on graphs
• The number of 4-colorings of the Hamming cube

Cited in

(18)

• Note on the number of balanced independent sets in the Hamming cube
• An approximate vertex-isoperimetric inequality for \(r\)-sets
• A note on balanced independent sets in the cube
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• The edge-diametric theorem in Hamming spaces
• The number of maximal independent sets in the Hamming cube
• Edge-isoperimetric inequalities and ball-noise stability: linear programming and probabilistic approaches
• Vertex-isoperimetric stability in the hypercube
• A stability result for the cube edge isoperimetric inequality
• Hamming cube and martingales
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• The exact isoperimetric inequality for ternary and quaternary cubes
• Stability for vertex isoperimetry in the cube
• Poincaré inequality 3/2 on the Hamming cube
• Stability for maximal independent sets
• Edge isoperimetric inequalities for powers of the hypercube
• An inequality for functions on the Hamming cube
• Incidence problems in harmonic analysis, geometric measure theory, and ergodic theory. Abstracts from the workshop held June 4--9, 2023

This page was built for publication: An isoperimetric inequality for the Hamming cube and some consequences

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