Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T03:28:49.037Z Has data issue: false hasContentIssue false
  • English
  • Français

Edge-Isoperimetric Inequalities and Influences

Published online by Cambridge University Press:  01 September 2007

DVIR FALIK  and
ALEX SAMORODNITSKY
DVIR FALIK
Affiliation:
School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel (e-mail: dfalik@cs.huji.ac.il, salex@cs.huji.ac.il)
ALEX SAMORODNITSKY
Affiliation:
School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel (e-mail: dfalik@cs.huji.ac.il, salex@cs.huji.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give a combinatorial proof of the result of Kahn, Kalai and Linial [16], which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least $\Omega\bigl(\frac{\log n}{n}\bigr)$. 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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 5 , September 2007 , pp. 693 - 712
Copyright
Copyright © Cambridge University Press 2007

References

[1]Beckner, W. (1975) Inequalities in Fourier analysis. Annals of Math. 102 159–182.CrossRefGoogle Scholar
[2]Ben-Or, M. and Linial, N. (1989) Collective coin flipping. In Randomness and Computation (Micali, S., ed.), Academic Press, pp. 91–115.Google Scholar
[3]Bezrukov, S. (1994) Isoperimetric problems in discrete spaces. In Extremal Problems for Finite Sets, Vol. 3 of Bolyai Soc. Math. Stud. (Frankl, P., Füredi, Z., Katona, G. and Miklos, D., eds), pp. 59–91.Google Scholar
[4]Bobkov, S. G. and Tetali, P. (2003) Modified logarithmic Sobolev inequalities in discrete settings. In Proc. STOC 2003, pp. 287–296.Google Scholar
[5]Bonami, A. (1970) Etude des coefficients Fourier des fonctions de L p(G). Ann. Inst. Fourier (Grenoble) 20 335–402.CrossRefGoogle Scholar
[6]Diaconis, P. and Saloff-Coste, L. (1996) Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695–750.CrossRefGoogle Scholar
[7]Friedgut, E. (1998) Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 27–36.CrossRefGoogle Scholar
[8]Friedgut, E. and Kalai, G. (1996) Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993–3002.CrossRefGoogle Scholar
[9]Friedgut, E. and Rödl, V. (2001) Proof of a hypercontractive estimate via entropy. Israel J. Math. 125 369–380.Google Scholar
[10]Gross, L. (1975) Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061–1083.CrossRefGoogle Scholar
[11]Harper, L. H. (1964) Optimal assignment of numbers to vertices. J. Soc. Ind. Appl. Math. 12 131–135.CrossRefGoogle Scholar
[12]Harper, L. H. (1966) Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1 385–393.CrossRefGoogle Scholar
[13]Hart, S. (1976) A note on the edges of the n-cube. Discrete Math. 14 157–163.CrossRefGoogle Scholar
[14]Jerrum, M. (2003) Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics, ETH Zürich. Birkhäuser, Basel.CrossRefGoogle Scholar
[15]Jerrum, M. and Sinclair, A. (1996) The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Hochbaum, D., ed.), PWS, pp. 482–520.Google Scholar
[16]Kahn, J., Kalai, G. and Linial, N. (1988) The influence of variables on boolean functions. In FOCS 1988, pp. 68–80.Google Scholar
[17]Kalai, G. Personal communication.Google Scholar
[18]Latala, R. On some inequalities for Gaussian measures. In Proc. International Congress of Mathematicians, Vol. II, pp. 813–822.Google Scholar
[19]Levenshtein, V. I. (1995) Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces. IEEE Trans. Inform. Theory IT-41, pp. 1303–1321.CrossRefGoogle Scholar
[20]van Lint, J. H. (1999) Introduction to Coding Theory, Springer, Berlin.CrossRefGoogle Scholar
[21]Milman, V. D. and Schechtman, G. (1986) Asymptotic Theory of Finite Dimensional Normed Spaces, Springer, New York.Google Scholar
[22]Mossel, E. Personal communication.Google Scholar
[23]Mossel, E., O'Donnell, R. and Oleszkiewicz, K. (2005) Noise stability of functions with low influences: Invariance and optimality. In FOCS 2005, pp. 21–30.Google Scholar
[24]Navon, M. and Samorodnitsky, A. (2005) On Delsarte's linear programming bounds for binary codes. In FOCS 2005, pp. 327–338.Google Scholar
[25]Rossignol, R. (2005) Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab. 34 1707–1725. tt arXiv:math.PR/0511607.Google Scholar
[26]Sarkar, A. Personal communication.Google Scholar
[27]Talagrand, M. (1994) On Russo's approximate 0-1 law. Ann. Probab. 22 1576–1587.CrossRefGoogle Scholar
[28]Talagrand, M. (1995) Concentration of measure and isoperimetric inequalities in product spaces. Publ. Math. Inst. Hautes Etudes Sci. 81 73–203.CrossRefGoogle Scholar
[29]Talagrand, M. (1997) On boundaries and influences. Combinatorica 17 275–285.CrossRefGoogle Scholar
[30]Szegö, G. (1939) Orthogonal Polynomials, AMS.Google Scholar