High-dimensional Lipschitz functions are typically flat

DOI10.1214/16-AOP1089zbMATH Open1377.82021arXiv1005.4636MaRDI QIDQ2012241FDOQ2012241

Ron Peled

Publication date: 28 July 2017

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: A homomorphism height function on the $d$-dimensional torus $mathbb{Z}_n^d$ is a function taking integer values on the vertices of the torus with consecutive integers assigned to adjacent vertices. A Lipschitz height function is defined similarly but may also take equal values on adjacent vertices. In each model, we consider the uniform distribution over such functions, subject to boundary conditions. We prove that in high dimensions, with zero boundary values, a typical function is very flat, having bounded variance at any fixed vertex and taking at most $C(logn{)}^{1/d}$ values with high probability. Our results extend to any dimension $dge2$, if $mathbb{Z}_n^d$ is replaced by an enhanced version of it, the torus $mathbb{Z}_n^{d}imesmathbb{Z}_2^{d_0}$ for some fixed $d_0$. This establishes one side of a conjectured roughening transition in $2$ dimensions. The full transition is established for a class of tori with non-equal side lengths. We also find that when $d$ is taken to infinity while $n$ remains fixed, a typical function takes at most $r$ values with high probability, where $r=5$ for the homomorphism model and $r=4$ for the Lipschitz model. Suitable generalizations are obtained when $n$ grows with $d$. Our results apply also to the related model of uniform 3-coloring and establish, for certain boundary conditions, that a uniformly sampled proper 3-coloring of $mathbb{Z}_n^d$ will be nearly constant on either the even or odd sub-lattice. Our proofs are based on a combinatorial transformation and on a careful analysis of the properties of a class of cutsets which we term odd cutsets. For the Lipschitz model, our results rely also on a bijection of Yadin. This work generalizes results of Galvin and Kahn, refutes a conjecture of Benjamini, Yadin and Yehudayoff and answers a question of Benjamini, H"aggstr"om and Mossel.

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

zbMATH Keywords

localizationrigidityrandom Lipschitz functionsanti-ferromagnetic Potts modelroughening transitionhomomorphism height functions[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Koteck%EF%BF%BD%EF%BF%BD+conjecture&go=Go Koteck�� conjecture]odd cutsetsproper 3-coloringsrandom graph homomorphism

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Combinatorial probability (60C05) Asymptotic enumeration (05A16) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Cited In (20)

• Homomorphisms from the torus
• Four-cycle free graphs, height functions, the pivot property and entropy minimality
• Height function localisation on trees
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$
• Uniform Lipschitz functions on the triangular lattice have logarithmic variations
• \(H\)-coloring tori
• Entropy-driven phase transition in low-temperature antiferromagnetic Potts models
• Delocalization of two-dimensional random surfaces with hard-core constraints
• Rigidity of 3-colorings of the discrete torus
• Superconcentration for minimal surfaces in first passage percolation and disordered Ising ferromagnets
• Entropic repulsion in \(|\nabla \phi |^p\) surfaces: a large deviation bound for all \(p\geq 1\)
• On independence and entropy for high-dimensional isotropic subshifts
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
• Proper -colorings of are Bernoulli
• Harmonic pinnacles in the discrete Gaussian model
• The Growth Constant of Odd Cutsets in High Dimensions
• Logarithmic variance for the height function of square-ice
• On the transition between the disordered and antiferroelectric phases of the 6-vertex model

   Recommendations

• Lipschitz functions on expanders are typically flat 👍 👎
• Nearly flat almost monotone measures are big pieces of Lipschitz graphs 👍 👎
• Essentially smooth Lipschitz functions 👍 👎
• Lipschitz functions 👍 👎
• Title not available (Why is that?) 👍 👎
• On the Oscillation Rigidity of a Lipschitz Function on a High-Dimensional Flat Torus 👍 👎
• Lipschitz functions with prescribed blowups at many points 👍 👎
• Grounded Lipschitz functions on trees are typically flat 👍 👎
• High-Dimensional $$p$$-Norms 👍 👎
• Lipschitz functions and Ekeland's theorem 👍 👎

This page was built for publication: High-dimensional Lipschitz functions are typically flat

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