Grounded Lipschitz functions on trees are typically flat

DOI10.1214/ECP.V18-2796MaRDI QIDQ743023zbMATH OpenFDO

Authors Ron Peled, Wojciech Samotij, Amir Yehudayoff

Publication date 22 September 2014

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.3035

zbMATH Keywords

rooted treesrandom Lipschitz functions

Mathematics Subject Classification ID

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

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

Recommendations

• Lipschitz functions on expanders are typically flat
• Multiplication operators between the Lipschitz space and the space of bounded functions on a tree
• Average range of Lipschitz functions on trees
• High-dimensional Lipschitz functions are typically flat
• LIPSCHITZ MAPS ON TREES

Cited in

(9)

• Homomorphisms from the torus
• Height function localisation on trees
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• High-dimensional Lipschitz functions are typically flat
• Uniform Lipschitz functions on the triangular lattice have logarithmic variations
• Lipschitz functions on expanders are typically flat
• Delocalization of two-dimensional random surfaces with hard-core constraints
• Rigidity of 3-colorings of the discrete torus
• Average range of Lipschitz functions on trees

This page was built for publication: Grounded Lipschitz functions on trees are typically flat

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743023)