2024/08/27 by Robert A. Krueger, Krueger, Robert A., Lina Li +3 · 2 citations
Mathematics · Economics, Econometrics and Finance · #Mathematical and Theoretical Analysis #Stochastic processes and financial applications #advanced mathematical theories
paper · pdf · doi:10.48550/arxiv.2408.14702
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.