Title: Expanders with respect to random regular graphs
Speaker: Manor Mendel, Open University of Israel & IAS
Date: Tuesday, March 12, 2013 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
A finite regular graph G=(V,E) has a spectral gap if and only if the following inequality holds true: For any mapping f:V-->H of the vertices into Hilbert space, the average over all pairs u,v in V of ||f(u)-f(v)||^2 is at most the average over the edges of the same quantity, times the reciprocal of the normalized spectral gap --- 1/(1- lambda_2(G)). Motivated in part by applications to coarse embeddability problems, it is common practice in metric geometry to consider this inequality with Hilbert space replaced by other metric spaces. However, it was unknown whether all sequences of expander graphs are equivalent in this respect. In this talk we will show that the answer to this question is negative by constructing a 3-regular expander sequence that satisfies with high probability the above inequality with respect to the shortest path metric of a random 3 regular graph. The construction uses several tools, including the zigzag product, Aleksandrov spaces of non-positive curvature, nonlinear functional analysis, and random graph theory.
Joint work with Assaf Naor
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math