Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T02:24:16.833Z Has data issue: false hasContentIssue false
  • English
  • Français

Lipschitz Functions on Expanders are Typically Flat

Published online by Cambridge University Press:  11 June 2013

RON PELED ,
WOJCIECH SAMOTIJ  and
AMIR YEHUDAYOFF
RON PELED
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: peledron@post.tau.ac.il)
WOJCIECH SAMOTIJ
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Trinity College, Cambridge CB2 1TQ, UK (e-mail: ws299@cam.ac.uk)
AMIR YEHUDAYOFF
Affiliation:
Department of Mathematics, Technion–IIT, Haifa, Israel (e-mail: amir.yehudayoff@gmail.com)
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.

This work studies the typical behaviour of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: M-Lipschitz functions (functions which change by at most M along edges) and integer-homomorphisms (functions which change by exactly 1 along edges). We prove that such functions typically exhibit very small fluctuations. For instance, we show that a uniformly chosen M-Lipschitz function takes only M+1 values on most of the graph, with a double exponential decay for the probability of taking other values.

Keywords

Primary 60C0505C15Secondary 05C6082B41

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 4 , July 2013 , pp. 566 - 591
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Benjamini, I., Häggström, O. and Mossel, E. (2000) On random graph homomorphisms into $\mathbb{Z}$. J. Combin. Theory Ser. B 78 86–114.Google Scholar
[2]Benjamini, I. and Schechtman, G. (2000) Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into $\mathbb{Z}$. Random Struct. Alg. 17 20–25.Google Scholar
[3]Benjamini, I., Yadin, A. and Yehudayoff, A. (2007) Random graph-homomorphisms and logarithmic degree. Electron. J. Probab. 12 926–950.Google Scholar
[4]Engbers, J. and Galvin, D. (2012) H-coloring tori. J. Combin. Theory Ser. B 102 1110–1133.Google Scholar
[5]Engbers, J. and Galvin, D. (2012) H-colouring bipartite graphs. J. Combin. Theory Ser. B 102 726–742.Google Scholar
[6]Friedman, J. (2008) A Proof of Alon's Second Eigenvalue Conjecture and Related Problems, Vol. 195 of Mem. Amer. Math. Soc., AMS.Google Scholar
[7]Galvin, D. (2003) On homomorphisms from the Hamming cube to $\mathbb{Z}$. Israel J. Math. 138 189–213.Google Scholar
[8]Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. (NS) 43 439–561.Google Scholar
[9]Kahn, J. (2001) An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10 219–237.CrossRefGoogle Scholar
[10]Kahn, J. (2001) Range of cube-indexed random walk. Israel J. Math. 124 189–201.CrossRefGoogle Scholar
[11]Peled, R. (2010) High-dimensional Lipschitz functions are typically flat. arXiv:1005.4636Google Scholar
[12]Peled, R., Samotij, W. and Yehudayoff, A. Grounded Lipschitz functions on trees are typically flat. Submitted.Google Scholar
[13]Peled, R., Samotij, W. and Yehudayoff, A.H-coloring expander graphs. In preparation.Google Scholar