Subscribe to Events

Speaker: Jinyoung Park (NYU)

Title: Lipschitz functions on expanders 

Abstract:  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*log n, where C depends (only) on d and the expansion of the given graph, it was shown by Peled, Samotij, and Yehudayoff (2012) that a uniformly chosen random M-Lipschitz function has height at most C'*M*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, any "not-so-large" vertex sets expand by 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.