The ACO Seminar (2024–2025)

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 sufficiently good "expander" graphs 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, using a combination of Sapozhenko's graph container methods and entropy methods. In this talk, I aim to discuss our result and some context, some elements of the proof, and some open problems. This is joint work with Lina Li and Jinyoung Park.