Lipschitz functions on expanders

Jinyoung Park, NYU
Fine Hall 224

We will discuss the typical behavior of M-Lipschitz functions on d-regular expander graphs, where an M-Lipschitz function means any two adjacent vertices admit integer values differ by at most M. While it is easy to see that the maximum possible height of an M-Lipschitz function on an n-vertex expander graph is about C(M,d)*log n, it was shown by Peled, Samotij, and Yehudayoff (2012) that a uniformly chosen random M-Lipschitz function has height at most C'(M,d)*loglog n with high probability, showing that the typical height of an M-Lipschitz function is much smaller than the extreme case.

Peled-Samotij-Yehudayoff's result holds under the condition that, roughly, subsets of the expander graph expand by the rate of about M*log(dM). We will show that the same result holds under a much weaker condition assuming that d is large enough. This is joint work with Robert Krueger and Lina Li.