What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements? - MathOverflow

What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

2011-04-12T18:35:49Z

It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0, 1, \ldots, 20$. (Some of the entries of the table are approximations, but they're good enough for the purposes of this question.)

In particular, the median number of moves needed is 18, and in fact about 70 percent of all positions require eighteen moves.

This seems a bit counterintuitive to me -- I'd expect the median to be around half the maximum number of moves needed. Consider for example generating $S_n$, the symmetric group on $n$ elements, from the adjacent transpositions $(k, k+1)$ for $k = 1, 2, \ldots, n-1$. The number of such transpositions needed to get from the identity permutation to any permutation $\sigma$ using adjacent transpositions is the number of inversions of that permutation -- that is, the number of pairs $(i,j)$ such that $i < j$ and $\sigma(i) > \sigma(j)$. The maximum number of inversions of a permutation in $S_n$ is ${n \choose 2}$. The mean is ${1 \over 2} {n \choose 2}$; this is also the median if it's a whole number; and the distribution is symmetric around ${1 \over 2} {n \choose 2}$. Another similar case is $(Z/2Z)^n$ generated by the generators of the factors -- the diameter is $n$, the typical distance between elements is $n/2$.

My question: which of these situations is, in some sense, "more typical"? More formally, what's known about the relationship between the diameter of the Cayley graph of a group and the typical distance between two vertices? And is there a third case, where the median or mean distance between two random elements is less than half the diameter? Here I'm looking for something like the distribution of Erdos numbers as given by Grossman -- the maximum Erdos number is 15 but the median is only 5 -- although of course there is the complication here that the collaboration graph is very far from being vertex-transitive.

Answer by Douglas Zare for What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

2011-04-13T00:06:28Z

I can answer one of those questions: The diameter is at most twice the median distance by the pigeonhole principle.

Let $m$ be the median. Let $S$ be the set of products of up to $m$ generators. For any $g\in G$, let $S^{-1} g = \{s^{-1}g | s\in S\}.$

By the definition of median, $|S| >= |G|/2$ with equality only if $m$ is a half-integer. If $|S| > |G|/2$ then for any $g\in G$, $S \cap S^{-1}g$ is nonempty, which lets us write $g$ as a product of two elements of $S$. If $|S| = |G|/2$ then every element of $S$ is a product of at most $m-1/2$ generators. For any $g\in G$, either $S \cap S^{-1}g$ is nonempty or $S \cup S^{-1}g = G$, so any $h\in G$ which requires $m+1/2$ generators must be in $S^{-1}g$, which means $g$ can be written as $h$ times an element of $S$, a product of at most $(m+1/2)+(m-1/2) = 2m$ generators.

Answer by Ben Webster for What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

2011-04-13T00:37:21Z

Your facts about $S_n$ are actually all facts about Coxeter groups with the generating set given by simple reflections: the distribution is symmetric around the mean, which is half the diameter. It even has a unique local maximum (assuming you allow the floor and roof of the mean to be "one maximum" even if they're different). In the Weyl group case, you can think of this as Hard Lefschetz for the flag variety.

I think perhaps the lesson here is that Coxeter groups a not a good representative of "groups in general."

Answer by JSE for What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

2011-04-13T01:26:04Z

Your question about the median is equivalent to: if the diamaeter of a group in some set of generators is d, how long does it take to generate half the group? The answer, as you've observed, depends a lot on what the group is and how the generators look. A case lots of people are currently thinking about is that where G is a finite group of Lie type; in this case, the Cayley graph (we now know, thanks to work of Helfgott, Pyber-Szabo, Breuillard-Green-Tao, Golsefidy-Varju, etc.) is an expander; since "most random graphs are expanders," this might be thought of as a reasonably generic case.

Now I am remembering a talk I saw Breuillard give about this so forgive any inaccuracy; but I believe the size of the set of words of length n grows exponentially in n for n up to some multiple of log G (so the number of words is |G|^c for some c < 1) then there's a transitional phase, but then once you've covered c|G| of the words in the group you finish up very quickly. These correspond to the "early period," "middle period," "late period" in this post of Terry's, though in the post he's talking about the closely related random walk rathen than the volume balls. In other words, the number of steps necessary to cover half the group is probably very close to the diameter in these cases.

Answer by Denis Chaperon de Lauzières for What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

2011-04-13T05:37:20Z

To expand on JSE's answer a bit: for simple finite groups of Lie type, the Gowers "quasirandom groups" argument with the additional trick of Nikolov-Pyber shows that once one has generated $|G|^{1-\delta}$ elements, three times that many steps give the whole group, for some $\delta>0$ which depends only on the Lie rank of the group (I think it is $1/9$ or so for $SL_2$). I've just written this up for my representation theory class

http://www.math.ethz.ch/~kowalski/representation-theory-notes.pdf

(section 4.7.1).

Such ideas are also already present in the work of Helfgott on growth in $SL_2$ -- part (b) of his "Key proposition" -- but the sharp constant $3$ was not; the crucial group-theoretic idea in the argument of Gowers is the use of the large size of a non-trivial representation of the group.