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

anti-ferromagnetic Potts modelhomomorphism height functionsKotecký conjecturelocalizationodd cutsetsproper 3-coloringsrandom graph homomorphismrandom Lipschitz functionsrigidityroughening transition

Mathematics Subject Classification ID

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

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.

Review text

A homomorphism height function on the \(d\)-dimensional torus \(\mathbb{Z}^d_n\) is a function on the vertices of the torus taking integer values and is constrained to have adjacent vertices which take adjacent integer values. A Lipschitz height function is defined similarly but may also take equal values on adjacent vertices. For each of these models the author considers the uniform distribution over all such functions with predetermined values at some fixed vertices. The main result is that in high dimensions and with zero boundary values, the obtained random function is typically very flat, having bounded variance at any fixed vertex and taking at most \(C({\log}n)^{1/d}\) values with high probability.

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

(29)

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

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)