- Series
- Graph Theory Seminar
- Time
- Tuesday, November 4, 2025 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Lina Li – University of Mississippi – https://sites.google.com/view/linali
- Organizer
- Xiying Du and Rose McCarty
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.