An inequality for functions on the Hamming cube

DOI10.1017/S0963548316000432MaRDI QIDQ5366955zbMATH OpenOpenAlexFDO

Authors Alex Samorodnitsky

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

edge-isoperimetric inequality for sets

Mathematics Subject Classification ID

Random walks on graphs (05C81) Extremal set theory (05D05) Combinatorial probability (60C05)

Abstract: We prove an inequality for functions on the discrete cube extending the edge-isoperimetric inequality for sets. This inequality turns out to be equivalent to the following claim about random walks on the cube: Subcubes maximize 'mean first exit time' among all subsets of the cube of the same cardinality.

Recommendations

• An isoperimetric inequality for the Hamming cube and some consequences
• Hamming cube and martingales
• scientific article; zbMATH DE number 1574610
• Poincaré inequality 3/2 on the Hamming cube
• On boundaries and influences

Cites work

• Almost isoperimetric subsets of the discrete cube
• Edge-Isoperimetric Inequalities and Influences
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• scientific article; zbMATH DE number 1749246 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Log-concave and spherical models in isoperimetry
• Logarithmic Sobolev Inequalities
• Mathematical aspects of mixing times in Markov chains.
• Optimal numberings and isoperimetric problems on graphs
• Shadows and intersections: Stability and new proofs
• Testing monotonicity

Cited in

(8)

• Hamming cube and martingales
• On a biased edge isoperimetric inequality for the discrete cube
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• Poincaré inequality 3/2 on the Hamming cube
• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• An isoperimetric inequality for the Hamming cube and some consequences
• Range of cube-indexed random walk
• Asymmetry of 2-step transit probabilities in 2-coloured regular graphs

This page was built for publication: An inequality for functions on the Hamming cube

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