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.

1.5. Link with Kazhdan’s property

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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in seminar and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s