Lipschitz functions on expanders are typically flat

DOI10.1017/S0963548313000163MaRDI QIDQ2841490zbMATH OpenOpenAlexFDO

Authors Ron Peled, Wojciech Samotij, Amir Yehudayoff

Publication date 26 July 2013

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphsexpander graphsLipschitz functions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial probability (60C05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: This work studies the typical behavior of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: M-Lipschitz functions (functions that change by at most M along edges) and integer-homomorphisms (functions that change by exactly 1 along edges). We prove that such functions typically exhibit very small fluctuations. For instance, we show that a uniformly chosen M-Lipschitz function takes only M+1 values on most of the graph, with a double exponential decay for the probability to take other values.

Review text

The theme of this paper is the study of the typical structure of an \(M\)-Lipschitz function of a graph. A function on the vertex set of a graph \(G\) is called \(M\)-Lipschitz if the (absolute value of the) difference between values of the function on pairs of vertices that form an edge is bounded by \(M\). The authors consider the set of all \(M\)-Lipschitz functions on a connected regular graph \(G\) that is assumed to satisfy certain expansion properties. In this case, it can be shown that most of the vertices have their value in a certain interval of length \(M\). The main result of the paper states that for every vertex \(v\) of \(G\) the probability that the value of a random \(M\)-Lipschitz function on \(v\) is far from this interval by \((t-1)M\) is exponentially small in the size of the ball of radius \(t\) around \(v\). They also show a similar result in the case where \(G\) is bipartite. However, here it can be shown that such a function is almost constant on one of the parts. They show that the probability that the value of \(f(v)\) is away from this number by \(t\) is exponentially small in the size of the ball of radius \(t\) around \(v\).

Recommendations

• High-dimensional Lipschitz functions are typically flat
• Lipschitz property of harmonic function on graphs
• Grounded Lipschitz functions on trees are typically flat
• On the oscillation rigidity of a Lipschitz function on a high-dimensional flat torus
• Average range of Lipschitz functions on trees

Cites work

• H-coloring tori
• \(H\)-colouring bipartite graphs
• Expander graphs and their applications
• scientific article; zbMATH DE number 1495913 (Why is no real title available?)
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• Random graph-homomorphisms and logarithmic degree
• Range of cube-indexed random walk

Cited in

(14)

• Rigidity of 3-colorings of the discrete torus
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• High-dimensional Lipschitz functions are typically flat
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
• Uniform Lipschitz functions on the triangular lattice have logarithmic variations
• Delocalization of two-dimensional random surfaces with hard-core constraints
• On the oscillation rigidity of a Lipschitz function on a high-dimensional flat torus
• Homomorphisms from the torus
• Height function localisation on trees
• Lipschitz functions on weak expanders
• Double dimers on planar hyperbolic graphs via circle packings
• The number of colorings of the middle layers of the Hamming cube
• Homogenization of the variational principle for discrete random maps
• Grounded Lipschitz functions on trees are typically flat

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

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