Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
Typical 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 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.