Discrete Applied Mathematics Seminar by Lina Li: Lipschitz Functions on Weak Expanders

Speaker: Lina Li, assistant professor of mathematics, University of Mississippi

Title: Lipschitz Functions on Weak Expanders

Abstract:

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 approach combines Sapozhenko’s graph container method with entropy techniques from information theory.

This is joint work with Krueger and Park.

Discrete Applied Math Seminar