### Grounded Lipschitz functions on trees are typically flat

**Ron Peled**

*(Tel Aviv University)*

**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.