Diameter (group theory)

{{short description|Concept in 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 $\backslash left(G,\backslash circ\backslash right)$, and any set of generators {{mvar|S}}. Define $D\_S$ to be the graph diameter of the Cayley graph $\backslash Lambda=\backslash left(G,S\backslash right)$. Then the diameter of $\backslash left(G,\backslash circ\backslash right)$ is the largest value of $D\_S$ taken over all generating sets {{mvar|S}}.

For instance, every finite cyclic group of order {{mvar|s}}, the Cayley graph for a generating set with one generator is an {{mvar|s}}-vertex cycle graph. The diameter of this graph, and of the group, is $\backslash lfloor\; s/2\backslash rfloor$.{{citation

| last1 = Babai | first1 = László | author1-link = László Babai

| last2 = Seress | first2 = Ákos

| doi = 10.1016/S0195-6698(05)80029-0

| issue = 4

| journal = European Journal of Combinatorics

| mr = 1179520

| pages = 231–243

| title = On the diameter of permutation groups

| volume = 13

| year = 1992| arxiv = 1109.3550

}}.

It is conjectured, for all non-abelian finite simple groups {{mvar|G}}, that{{harvtxt|Babai|Seress|1992}}, Conj. 1.7. This conjecture is misquoted by {{harvtxt|Helfgott|Seress|2014}}, who omit the non-abelian qualifier.

:$$

\operatorname{diam}(G) \leqslant \left(\log|G|\right)^{\mathcal{O}(1)}.

Many partial results are known but the full conjecture remains open.{{citation

| last1 = Helfgott | first1 = Harald A. | author1-link = Harald Helfgott

| last2 = Seress | first2 = Ákos

| doi = 10.4007/annals.2014.179.2.4

| issue = 2

| journal = Annals of Mathematics

| mr = 3152942

| pages = 611–658

| series = Second Series

| title = On the diameter of permutation groups

| volume = 179

| year = 2014| arxiv = 1109.3550}}.