Grounded Lipschitz functions on trees are typically flat

2013/05/14 by Ron Peled, Peled, Ron, Wojciech Samotij +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1305.3035

openalex publication_date 2013/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 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₀ of the tree. We prove that the probability that the value of a uniformly chosen random function at v₀ is more than M+t is doubly-exponentially small in t. We also show a similar bound for continuous (real-valued) grounded Lipschitz functions.

Cited by

• Asymptotic enumeration via graph containers and entropy

Related

• On the local convergence of integer-valued Lipschitz functions on regular trees
• Absolutely minimal Lipschitz extension of tree-valued mappings
• Lipschitz functions on weak expanders
• Lipschitz Functions on Sparse Graphs
• Geometry of Lipschitz percolation