Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-14T03:27:01.976Z Has data issue: false hasContentIssue false
  • English
  • Français

An Inequality for Functions on the Hamming Cube

Part of: Extremal combinatorics Combinatorial probability

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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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