High-dimensional Lipschitz functions are typically flat

DOI10.1214/16-AOP1089MaRDI QIDQ2012241zbMATH OpenFDO

Authors Ron Peled

Publication date 28 July 2017

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

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

zbMATH Keywords

localizationrigidityrandom Lipschitz functionsanti-ferromagnetic Potts modelroughening transitionhomomorphism height functionsodd cutsetsproper 3-coloringsrandom graph homomorphismKotecký conjecture

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)

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.

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
• scientific article; zbMATH DE number 2182808
• 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

Cited in

(26)

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

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)