Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T20:21:49.620Z Has data issue: false hasContentIssue false
  • English
  • Français

An Inequality for Functions on the Hamming Cube

Part of: Combinatorial probability Extremal combinatorics

Published online by Cambridge University Press:  29 March 2017

ALEX SAMORODNITSKY
ALEX SAMORODNITSKY*
Affiliation:
School of Engineering and Computer Science, The Hebrew University of Jerusalem, Jerusalem 91904, Israel (e-mail: 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 prove an inequality for functions on the discrete cube {0, 1}n 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.

MSC classification

Primary: 05D05: Extremal set theory
Secondary: 60C05: Combinatorial probability
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 3 , May 2017 , pp. 468 - 480
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Barthe, F. (2002) Log-concave and spherical models in isoperimetry. Geom. Funct. Anal. 12 32–55.Google Scholar
[2] Bezrukov, S. (1994) Isoperimetric problems in discrete spaces. In Extremal Problems for Finite Sets (Frankl, P., Füredi, Z., Katona, G. and Miklos, D., eds), Vol. 3 of Bolyai Society Mathematical Studies, pp. 59–91.Google Scholar
[3] Bollobas, B. (1986) Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press.Google Scholar
[4] Ellis, D. (2011) Almost isoperimetric subsets of the discrete cube. Combin. Probab. Comput. 20 363–380.Google Scholar
[5] Falik, D. and Samorodnitsky, A. (2007) Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 693–712.Google Scholar
[6] Goldreich, O., Goldwasser, S., Lehman, E., Ron, D. and Samorodnitsky, A. (2000) Testing monotonicity. Combinatorica 20 301–337.CrossRefGoogle Scholar
[7] Gross, L. (1975) Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061–1083.Google Scholar
[8] Harper, L. H. (1966) Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1 385–393.Google Scholar
[9] Jerrum, M. (2003) Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics, ETH Zürich, Birkhäuser.Google Scholar
[10] Keevash, P. (2008) Shadows and intersections: Stability and new proofs. Adv. Math. 218 1685–1703.Google Scholar
[11] Montenegro, R. and Tetali, P. (2005) Mathematical Aspects of Mixing Times in Markov Chains , Vol. 1:3 of Foundations and Trends in Theoretical Computer Science, Now Publishers Inc.Google Scholar
[12] Ros, A. (2001) The isoperimetric problem. http://www.ugr.es/~aros/isoper.htm Google Scholar