Grounded Lipschitz functions on trees are typically flat
Wojciech Samotij (Tel Aviv University)
Amir Yehudayoff (Technion-IIT)
Abstract
A grounded $M$-Lipschitz function on a rooted $d$-ary tree is an integer valued map on the vertices that changes by at most $M$ along edges and attains the value zero on the leaves. We study the behavior of such functions, specifically, their typical value at the root $v_0$ of the tree. We prove that the probability that the value of a uniformly chosen random function at $v_0$ is more than $M+t$ is doubly-exponentially small in $t$. We also show a similar bound for continuous (real-valued) grounded Lipschitz functions.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-9
Publication Date: July 6, 2013
DOI: 10.1214/ECP.v18-2796
References
- Benjamini, Itai; Häggström, Olle; Mossel, Elchanan. On random graph homomorphisms into ${\bf Z}$. J. Combin. Theory Ser. B 78 (2000), no. 1, 86--114. MR1737627
- Benjamini, Itai; Yadin, Ariel; Yehudayoff, Amir. Random graph-homomorphisms and logarithmic degree. Electron. J. Probab. 12 (2007), no. 32, 926--950. MR2324796
- Brascamp, Herm Jan; Lieb, Elliot H.; Lebowitz, Joel L. The statistical mechanics of anharmonic lattices. Proceedings of the 40th Session of the International Statistical Institute (Warsaw, 1975), Vol. 1. Invited papers. Bull. Inst. Internat. Statist. 46 (1975), no. 1, 393--404 (1976). MR0676341
- Galvin, David. On homomorphisms from the Hamming cube to ${\bf Z}$. Israel J. Math. 138 (2003), 189--213. MR2031957
- Kahn, J. Range of cube-indexed random walk. Israel J. Math. 124 (2001), 189--201. MR1856513
- R. Peled, phHigh-dimensional Lipschitz functions are typically flat, ARXIV1005.4636v1.
- R. Peled, W. Samotij, and A. Yehudayoff, phH-coloring expander graphs, in preparation.
- bysame, phLipschitz functions on expanders are typically flat, to appear in Combin. Probab. Comput.
- Velenik, Yvan. Localization and delocalization of random interfaces. Probab. Surv. 3 (2006), 112--169. MR2216964
This work is licensed under a Creative Commons Attribution 3.0 License.