When: Sunday, May 14,
10am
Where: Schreiber 309
Speaker: Doron Puder,
Tel Aviv University
Title:
Spectral Gaps of Cayley Graphs and Schreier Graphs of the Symmetric Group
Aldous' spectral gap conjecture, proved in 2009 by Caputo, Liggett and Richthammer, states the
following a priori very surprising fact: the spectral gap of a random walk on a finite graph is equal
to the spectral gap of the interchange process on the same graph. This is equivalent to that for
every set of transposition $A$ in the symmetric group $S_n$, the spectral gap of the Cayley graph
$Cay(S_n, A)$ is identical to that of the Schreier graph depicting the action of $S_n$ on
$\{1,..,n\}$ w.r.t. $A$. Can this remarkable result be generalized to other generating sets? I will
discuss possible
generalizations and explain what we know about them.
This is based on joint works with Ori Parzanchevski and with Gil Alon and Gadi Kozma.