Lipschitz functions on weak expanders

Given a connected finite graph G, an integer-valued function f on $V(G)$ is called M-Lipschitz if the value of f changes by at most M along the edges of G. In 2013, Peled, Samotij, and Yehudayoff showed that random M-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming M is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger M, (partially) answering questions of Peled et al. Our techniques involve a combination of Sapozhenko's graph container methods and entropy methods from information theory.