In the area of

abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...

known as

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...

, the diameter of a finite group is a measure of its complexity. Consider a finite group

\left(G,\circ\right)

, and any set of generators . Define

D_S

to be the

graph diameter In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path dis ...

of the

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

\Lambda=\left(G,S\right)

. Then the diameter of

\left(G,\circ\right)

is the largest value of

D_S

taken over all generating sets . For instance, every finite

cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...

of order , the Cayley graph for a generating set with one generator is an -vertex

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

. The diameter of this graph, and of the group, is

\lfloor s/2\rfloor

. It is conjectured, for all non-abelian finite

simple group SIMPLE Group Limited is a conglomeration of separately run companies that each has its core area in International Consulting. The core business areas are Legal Services, Fiduciary Activities, Banking Intermediation and Corporate Service. The d ...

s , that :

\operatorname(G) \leqslant \left(\log, G, \right)^.

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

References

Finite groups Measures of complexity {{group-theory-stub