Lipschitz functions on expanders are typically flat (Q2841490)

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\).