User:MathsHistorian/sandbox

In mathematics, the commuting graph of a semigroup, or in particular of a group, is an undirected graph in which the vertices are elements of the semigroup and there is an edge betweeen any pair of elements that commute (that is, there is an edge between vertices x and y if and only if xy=yx in the semigroup).

Depending on the author, the vertex set may comprise every element of the semigroup, or only the non-central elements (since the central elements — those elements of a semigroup that commute with every other element — would always form a complete subgraph, every vertex of which would be adjacent to every vertex of the whole commuting graph). They have been used to study groups and semigroups by seeking relationships between the combinatorial structure of the commuting graph and the algebraic structure of the group or semigroup. If the central elements are excluded, the commuting graph is usually only defined for non-commutative groups and semigroups.

For the purposes of this article, the vertices of the commuting graph are the non-central elements unless otherwise noted.

History

The concept of a commuting graph was first introduced for groups in 1955 [BF55], although the term ‘commuting graph’ was not coined until 1983 [Ber83]). They played a implicit role in Fischer's discovery of the sporadic groups now known as the Fischer groups.

The study of the commuting graphs of semigroups other than groups was initiated in 2011. [AKK11]

Properties

Connectedness and diameters

It is possible for a commuting graph to be non-connected and thus not to have a finite diameter).

For a finite set $X$, the commuting graph of the symmetric group ${\mathcal {S}}(X)$ is connected if and only if $|X|$ $|X|-1$ are non-prime commuting graph of the alternating group ${\mathcal {A}}(X)$ is connected if and only if $|X|$, $|X|-1$, and $|X|-2$ are non-prime. When connected, the commuting graphs of ${\mathcal {S}}(X)$ and ${\mathcal {A}}(X)$ have diameter at most 5 [IJ08]

The commuting graph of the symmetric inverse semigroup ${\mathcal {I}}(X)$ is not connected if and only if $|X|$ is an odd prime. When $|X|$ is not an odd prime, it has diameter 4 or 5, and is known to have diameter 4 when $|X|$ is even and diameter 5 when $|X|$ is a power of an odd prime. [ABK15]

For every natural number n, there is a finite group whose commuting graph is connected and has diameter equal to n. [Cut22]

If a finite group has trivial center and its commuting graph is connected, then its diameter is at most 10. [MP13]

The commuting graph of a completely simple semigroups is never connected except when it is a group, and the connected components are the commuting graphs including central elements of its maximal subgroups (which, by the Rees–Suschewitz theorem, are isomorphic). [Pau25]

Simple groups

Non-abelian finite simple groups are uniquely characterized by their commuting graphs, in the sense that if G is a non-abelian finite simple group and H is a group, and the commuting graphs of G and the commuting graph of H are isomorphic (as graphs), then G and H are isomorphic (as groups).