An isoperimetric inequality for Hamming balls and local expansion in hypercubes

DOI10.37236/9860MaRDI QIDQ2073309zbMATH OpenOpenAlexFDO

Authors Zilin Jiang, Amir Yehudayoff

Publication date 1 February 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(n\)-dimensional Hamming balllocal expansion

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: We prove a vertex isoperimetric inequality for the $n$-dimensional Hamming ball $mathcal{B}_n(R)$ of radius $R$. The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to $mathcal{B}_n(R)$ in size. A key step in the proof is a local expansion phenomenon in hypercubes.

Review text

Summary: We prove a vertex isoperimetric inequality for the \(n\)-dimensional Hamming ball \(\mathcal{B}_n(R)\) of radius \(R\). The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to \(\mathcal{B}_n(R)\) in size. A key step in the proof is a local expansion phenomenon in hypercubes.

Recommendations

• An isoperimetric inequality for the Hamming cube and some consequences
• Vertex-isoperimetric stability in the hypercube
• Stability for vertex isoperimetry in the cube
• On an isoperimetric problem for Hamming graphs
• An inequality for functions on the Hamming cube

Cites work

• A sum-product estimate in finite fields, and applications
• An approximate vertex-isoperimetric inequality for r-sets
• Extremal properties of half-spaces for spherically invariant measures
• 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 2103158 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Invitation to discrete mathematics
• Optimal numberings and isoperimetric problems on graphs
• The Brunn-Minkowski inequality in Gauss space

Cited in

(5)

• Edge isoperimetric inequalities for powers of the hypercube
• Poincaré inequality 3/2 on the Hamming cube
• Vertex-isoperimetric stability in the hypercube
• An isoperimetric inequality for the Hamming cube and some consequences
• Randomly twisted hypercubes: between structure and randomness

This page was built for publication: An isoperimetric inequality for Hamming balls and local expansion in hypercubes

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