Consider the random Cayley graph of a finite group G with respect to k generators chosen uniformly at random. This draws a Cayley graph uniformly amongst all degree-k Cayley graphs of G. A conjecture of Aldous and Diaconis (1985) from the '80s asserts, for k ≫ log |G|, the following:

• the random walk on this (random) graph exhibits cutoff with high probability (whp); • the cutoff time depends only on k and |G| asymptotically (up to smaller order terms).

The cutoff time should not depend (strongly) on the choice of generators. In other words, "cutoff is universal for the random walk on the random Cayley graph". Restricted to Abelian groups, this was verified in the '90s; the cutoff time T(k, |G|) was found explicitly. In fact, T(k, |G|) was shown to be an upper bound on mixing for arbitrary groups.

First we extend the conjecture to 1 ≪ k ≲ log |G|. Write d(G) for the minimal size of a generating set of G. We establish cutoff (for the random walk on) all Abelian group under the condition k - d(G) ≫ 1, verifying the occurrence of cutoff part of the Aldous--Diaconis conjecture. This condition is almost optimal to guarantee that the group if generated whp. For the cutoff time to depend only on k and |G|, not the algebraic structure of G, we show that d(G) ≪ log |G| and k - d(G) ≍ k ≫ 1 is sufficient. However, the result does not hold if k ≍ log |G| ≍ d(G); there are even regimes with 1 ≪ k ≪ log |G| for which it does not hold if we allow 1 ≪ k - d(G) ≪ k.

Next we consider the (non-Abelian) Heisenberg group H := H_{p,d} of d x d matrices with entries in Z_p, with p prime and d ≥ 3 not diverging too quickly. We establish cutoff for any k ≫ 1 with log k ≪ log |H|. Except for k growing super-polynomially in |G| (ie log k ≫ log log |G|), this is the first example where cutoff has been established for any non-Abelian group. Further, even restricting to k ≫ log |G|, the ctuoff time cannot be written as a function of only k and |G|; rather, one needs |H^{ab}|, the size of the Abelianisation, also. In fact, taking d → ∞ sufficiently slowly, the mixing time is of smaller order (not just a constant smaller) than T(k, |H|), the universal upper bound. When k ≳ log |H^{ab}|, we can remove the primality assumption on p.

Our next sequence of results still regards mixing, but this time determines upper bounds which hold for large classes of groups, rather than establishing cutoff. From a nilpotent group G, we construct an Abelian group G' (from the lower central series of G) of the same size. We show that the mixing time for G is at least as fast (asymptotically) as that for G' whp.

Wilson (1997) conjectured that, amongst all groups of size at most 2^d, the group Z_2^d gives rise to the slowest mixing time. When restricted to Abelian groups, we deduce thsi from the explicit description of the mixing time which we obtain. As a corollary of the above nilpotent-to-Abelian comparison, this is extended from the Abelian to the nilpotent set-up.

The spirit of the Aldous--Diaconis conjecture is that certain properties of the random Cayley graph should depend very weakly on the choice of generators. We apply this principle to geometric aspects of the graph. Primarily we study typical distance: draw U ~ Unif(G) and consider dist(id, U), where id ∈ G is the identity and dist is the graph distance.

We show that the typical distance concentrates whp for Abelian groups. We establish this for all Abelian group when either 1 ≪ k ≪ log |G| / log log log |G| and k - d(G) ≍ k or k ≫ log |G|; for k in the interim regime or smaller 1 - d(G)/k, we need additional conditions. Further, the concentration value depends only on k and |G| in the former cases. We study typical distance for Heisenberg groups, proving analogous results. Again, the value depends on |H^{ab}| as well as k and |H|.

For k ≳ log |G|, we can extend the typical distance results to show that the diameter of the graph agrees asymptotically with the typical distance whp. (For H_{p,d}, we need d ≍ 1 for this.)

Finally, we find the order of the spectral gap when the underlying group is Abelian: it is |G|^{2/k} whp when 1 ≪ k ≲ log |G| and k - d(G) ≍ k. This extends, in the Abelian set-up, a celebrated result of Alon and Roichman (1994) which states that for any group the random Cayley graph is an expander, ie has spectral gap order 1, whp when k - log_2 |G| ≍ k.