Edge-isoperimetric inequalities and influences

2005/12/29 by Falik, D., Samorodnitsky, A. · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0512636

Abstract

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega((log n)/(n)). The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants. We also state some conjectures about optimal constants and discuss their possible implications

Cited by

• Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube
• Enhanced noise sensitivity, 2D directed polymers and Stochastic Heat Flow

Related

• Sharp isoperimetric inequalities on the Hamming cube near the critical exponent
• On a biased edge isoperimetric inequality for the discrete cube
• A stability result for the cube edge isoperimetric inequality
• An isoperimetric inequality for the Hamming cube and some consequences
• Low-degree Boolean functions on S_n, with an application to isoperimetry