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

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.


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
Full Text: DOI arXiv