Diameter (group theory)
In the area of abstract algebra known as group theory, the diameter of a finite group is a measure of its complexity. Consider a finite group [math]\displaystyle{ \left(G,\circ\right) }[/math], and any set of generators S. Define [math]\displaystyle{ D_S }[/math] to be the graph diameter of the Cayley graph [math]\displaystyle{ \Lambda=\left(G,S\right) }[/math]. Then the diameter of [math]\displaystyle{ \left(G,\circ\right) }[/math] is the largest value of [math]\displaystyle{ D_S }[/math] taken over all generating sets S.
For instance, every finite cyclic group of order s, the Cayley graph for a generating set with one generator is an s-vertex cycle graph. The diameter of this graph, and of the group, is [math]\displaystyle{ \lfloor s/2\rfloor }[/math].[1]
It is conjectured, for all non-abelian finite simple groups G, that[2]
- [math]\displaystyle{ \operatorname{diam}(G) \leqslant \left(\log|G|\right)^{\mathcal{O}(1)}. }[/math]
Many partial results are known but the full conjecture remains open.[3]
References
- ↑ "On the diameter of permutation groups", European Journal of Combinatorics 13 (4): 231–243, 1992, doi:10.1016/S0195-6698(05)80029-0.
- ↑ (Babai Seress), Conj. 1.7. This conjecture is misquoted by (Helfgott Seress), who omit the non-abelian qualifier.
- ↑ "On the diameter of permutation groups", Annals of Mathematics, Second Series 179 (2): 611–658, 2014, doi:10.4007/annals.2014.179.2.4.
 |  |
