** The diameter of permutation groups **

The diameter of the Rubik’s cube graph (it is a Cayley graph) is 20.

Define the diameter of a finite group as the maximal diameter of all its Cayley graphs.

**conjecture (Babai 1992)**. There exists a such that for every finite simple nonabelian group ,

Known for

- Helfgott: ,
- Dinai, Varju:
- Pyber-Szabo, Breuillard-Green-Tao: groups of Lie type of bounded rank.

There remains permutation groups.

**Theorem 1 (Helfgott-Seress)** * *

*
** *

The same estimate follows for all transitive subgroups of .

**1. Product theorems **

These are usually more important than diameter bounds that follow from them.

**Theorem 2** * There exists a polynomial such that for all finite simple groups of Lie type and rank , and generating systems , *

*
** *

This fails for (Pyber-Spiga).

Alternative techniques, like algebraic geometry of varieties (Larsen-Pink), or escape from subvarieties (Mozes-Oh) do not apply directly either.

**2. A weak product theorem for **

This provides a simpler proof of Helfgott-Seress’ diameter bound. This is work in progress.

**Theorem 3** * There exists such that, for all symmetric generating systems , *

*
** where gives a slightly worst diameter bound than Helfgott-Seress. *

** 2.1. Dimensional estimate **

Find a special subset (analogue of 1-dimensional variety) such that for every blob, at least one among boundedly many conjugates has long intersections with the blob.

Special turns out to be: which has no long orbits.

** 2.2. Prefixes and suffixes **

Better than set growing under multiplication, one should think in terms of sets growing under a group action, restricted to subsets.

Also we play with subset analogues of statements in group theory:

- orbit versus stabilizer,
- lifting and reduction from quotients,
- large subgroups of .

Some aspect of probabilistic method is used: outcomes of short random walks.

The key feature of is that it acts on a very small set. This makes it possible to apply work of Babai and of Pyber on 2-transitive actions.

**3. Moral **

The action by conjugation is a important than the translation action. For , action on -tuples helps.

**4. Questions **

Which generating sets maximize diameter? For , random choices give much smaller diameters ( instead of a power of ). This might be sharp, I do not know.

### Like this:

Like Loading...

*Related*

## 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
http://www.math.ens.fr/metric2011/