***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Jinyoung Park (NYU)

Thursday 18th April, 3:00 in Fine Hall 224.

Title: Lipschitz functions on expanders

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.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)