An isoperimetric inequality for the Hamming cube and some consequences

DOI10.1090/PROC/15105zbMATH Open1446.05088arXiv1909.04274OpenAlexW3013548102MaRDI QIDQ5117318FDOQ5117318

Authors: Jinyoung Park, J. Kahn 

Publication date: 20 August 2020

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

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.

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

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

zbMATH Keywords

maximal independent setsstability resultsseparating the cube

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

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

Cited In (18)

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

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)