An isoperimetric inequality for the Hamming cube and some consequences

DOI10.1090/PROC/15105MaRDI QIDQ5117318zbMATH OpenOpenAlexFDO

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 setsseparating the cubestability results

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

• 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
• scientific article; zbMATH DE number 3503316 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• 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

(20)

• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• The exact isoperimetric inequality for ternary and quaternary cubes
• On boundaries and influences
• Hamming cube and martingales
• A stability result for the cube edge isoperimetric inequality
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• Edge-isoperimetric inequalities and ball-noise stability: linear programming and probabilistic approaches
• Edge isoperimetric inequalities for powers of the hypercube
• Note on the number of balanced independent sets in the Hamming cube
• Poincaré inequality 3/2 on the Hamming cube
• Stability for vertex isoperimetry in the cube
• Vertex-isoperimetric stability in the hypercube
• Stability for maximal independent sets
• The number of maximal independent sets in the Hamming cube
• A note on balanced independent sets in the cube
• An approximate vertex-isoperimetric inequality for r-sets
• 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
• Sharp isoperimetric inequalities on the Hamming cube near the critical exponent
• The edge-diametric theorem in Hamming spaces

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)