Grounded Lipschitz functions on trees are typically flat. (English) Zbl 1298.05306

Peled, Ron; Samotij, Wojciech; Yehudayoff, Amir

Electron. Commun. Probab. 18, Paper No. 55, 9 p. (2013).

Summary: 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.

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
05C60	Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
60C05	Combinatorial probability
82B41	Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics

Keywords:

random Lipschitz functions; rooted trees