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 on . After steps of random walk, the distribution of random element is . Fix a resolution . The mixing time is the least such that
Experience shows that mixing time behaves slightly differently from first eigenvalue : small scale changes in the graph can destroy expansion, whereas mixing time survives. In a sense, mixing time involves all eigenvalues, not just .
Definable in terms of isoperimetric constants like Cheeger’s constant of a finite graph ,
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
Equivalently, a family of finite graphs is an expander iff degree is bounded above and is bounded away from 0.
1.2. Examples: Pinsker’s model
An infinite trivalent tree has . 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 and of . Pick permutations . Connect to in . Get a -regular graph , 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 and permutations are chosen at random, the Cheeger constant of is .
Introduce a wrong isoperimetric constant , where , is replaced with number of vertices, . Then .
Assume that . Then there exist and such that misses for all . There are at most
such bad pairs, and this is .
1.4. Comparison with trees
If finite graph is a quotient of -regular tree , then
Bollobas improved this bound into .
The search of graphs achieving the asymptotic bound on , called Ramanujan graphs, happened to be successful.
1.5. Link with Kazhdan’s property
Theorem 3 (Margulis) Let be a group finite property (T), generated by . Let be an infinite family of finite quotients of . Then the family is an expander.
Conversely, if a finite 2-dimensional polyhedron has links which satisfy , 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)
Selberg conjectured that this bound could be improved to . Also, , and one can wonder wether, asymptotically, congruence quotients have Cheeger constant tending to 1. This is not true.
Theorem 5 (Brooks-Zuk)
Selberg’s theorem relies on the representation theory of . 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 , the mixing time is at most .
This relies on studying the action of on -tuples of points. For each , in analogy with Pinsker, one constructs a random graph with vertices, and shows that this produce expanders. Representation theory of plays a role.