## Notes of Andrei Zuk’s Cambridge lecture 19-01-2017

Random walks on random symmetric groups

Joint with Harald Helfgott and Akos Seres.

1. Mixing time

Related to expanders: the key word is mixing time.

Every finite simple group can be generated by 2 elements. This follows from the classication (no conceptual reason for that). How efficiently do these two elements generate ? This is what mixing time measures. We shall solve the case of the alternating group, with randomly chosen generators.

Definition 1 Fix a measure ${\mu}$ on ${G=\mathfrak{S}_n}$. After ${m}$ steps of random walk, the distribution of random element is ${\mu^{\star m}}$. Fix a resolution ${\delta=1/e}$. The mixing time is the least ${m}$ such that

$\displaystyle \begin{array}{rcl} \sum_{g\in G}|\mu^{\star m}-\frac{1}{|G|}|<\delta. \end{array}$

Experience shows that mixing time behaves slightly differently from first eigenvalue ${\lambda_1}$: small scale changes in the graph can destroy expansion, whereas mixing time survives. In a sense, mixing time involves all eigenvalues, not just ${\lambda_1}$.

1.1. Expansion

Definable in terms of isoperimetric constants like Cheeger’s constant of a finite graph ${X}$,

$\displaystyle \begin{array}{rcl} h(X)=\min\{\frac{|\partial A}{|A|}\,;\,A\subset X,\,|A|\leq\frac{1}{2}|X|\}. \end{array}$

Recall that a family of finite graphs is an expander if degree is bounded above and Cheeger constant is bounded away from 0.

The discrete Laplace operator is

$\displaystyle \begin{array}{rcl} \Delta f(x)=f(x)-\frac{1}{\mathrm{deg}(x)}\sum_{y\sim x}f(y). \end{array}$

Equivalently, a family of finite graphs is an expander iff degree is bounded above and ${\lambda_1}$ is bounded away from 0.

1.2. Examples: Pinsker’s model

An infinite trivalent tree has ${h(X)=1}$. So regular trees are the best infinite expanders. However, finite trees do poorly.

To get expanders, the first successful source has been random graphs in the permutation model. Fix two copies ${I}$ and ${O}$ of ${\{1,\ldots,n\}}$. Pick permutations ${\pi_1,\ldots,\pi_k\in\mathfrak{S}_n}$. Connect ${i\in I}$ to ${\pi_j(i)}$ in ${O}$. Get a ${k}$-regular graph ${X}$, bipartite, with multiple edges. Different permutations give rise to different vertex-labelled graphs (but possibly many isomorphic graphs).

Theorem 2 (Pinsker) A symptotically almost surely, if ${k\geq 3}$ and permutations are chosen at random, the Cheeger constant of ${X}$ is ${\geq 1/2}$.

1.3. Proof

Introduce a wrong isoperimetric constant ${h'}$, where ${|\partial A|}$, ${A\subset X}$ is replaced with ${|\partial'A|=}$ number of vertices, ${A\subset I}$. Then ${h(X)\geq h'(X)-1}$.

Assume that ${h'(X)\leq 3/2}$. Then there exist ${A\subset I}$ and ${B\subset O}$ such that ${\pi_i(A)}$ misses ${B}$ for all ${i}$. There are at most

$\displaystyle \begin{array}{rcl} \sum_{A\subset I,\,|A|\leq n/2}\sum_{B\subset O,\,3/2|A|}(|B|\cdots|B|(|B|-|A|+1)(n-|A|)!)^k \end{array}$

such bad pairs, and this is ${o((n!)^k)}$.

1.4. Comparison with trees

If finite graph ${X_n}$ is a quotient of ${k}$-regular tree ${T_k}$, then

$\displaystyle \begin{array}{rcl} \limsup \lambda_1(X_n)\leq \lambda_0(T_k)=1-2\frac{\sqrt{k-1}}{k},\quad \limsup h(X_n)\leq h(T_k)=k-2. \end{array}$

Bollobas improved this bound into ${\limsup h(X_n)\leq \frac{1}{2}h(T_k)=\frac{k-2}{2}}$.

The search of graphs achieving the asymptotic bound on ${\lambda_1}$, called Ramanujan graphs, happened to be successful.

Theorem 3 (Margulis) Let ${\Gamma}$ be a group finite property (T), generated by ${S}$. Let ${\Gamma_n}$ be an infinite family of finite quotients of ${\Gamma}$. Then the family ${Cay(\Gamma_n,S)}$ is an expander.

Conversely, if a finite 2-dimensional polyhedron has links ${L}$ which satisfy ${\lambda_1(L)>1/2}$, then its fundamental group has property (T) (Zuk 1996).

2. Selberg’s conjecture

Consider congruence quotients of the hyperbolic plane, and their Riemannian Laplacians.

Theorem 4 (Selberg)

$\displaystyle \begin{array}{rcl} \lambda_1(H^2/\Gamma(n))\geq\frac{3}{16}. \end{array}$

Selberg conjectured that this bound could be improved to ${1/4}$. Also, ${h(H^2)=1}$, and one can wonder wether, asymptotically, congruence quotients have Cheeger constant tending to 1. This is not true.

Theorem 5 (Brooks-Zuk)

$\displaystyle \begin{array}{rcl} \limsup h(H^2/\Gamma(n))\leq 0.46<\frac{3}{16}. \end{array}$

Selberg’s theorem relies on the representation theory of ${SL_2({\mathbb Z}/p{\mathbb Z})}$. For the symmetric group, this use of representation theory has been unsuccessful yet.

3. The symmetric group

The following solves a conjecture by Diaconis.

Theorem 6 (Helfgott-Seress-Zuk) For a random choice of generators of ${\mathfrak{S}_n}$, the mixing time is at most ${n^3\log n}$.

This relies on studying the action of ${\mathfrak{S}_n}$ on ${k}$-tuples of points. For each ${k}$, in analogy with Pinsker, one constructs a random graph with ${2n^k}$ vertices, and shows that this produce expanders. Representation theory of ${\mathfrak{S}_n}$ plays a role.