The subcommutativity preordering

Let G be a graph, then the vertices of the graph G can be preordered by adjacency, so that one element is greater then another if it is adjacent to every element that element is adjacent to. Two elements are adjacency equal if they are adjacent to all the same elements. In the same sense, we can get a preordering of a semigroup from the commuting graph. This forms the subcommutativity preordering, which is immensely useful in studies of commutativity. It tells us when one element is more commutative then another element.

Definition. an element a subcommutes with b if it is the case that $\forall x : (xa=ax) \implies (xb = bx)$.

Semigroups are sufficiently complicated that they have multiple preorderings defined on them. For the sake of clarity and formalism, we will also define the generator preordering on a semigroup. This preorder requires a positive integer for iteration, because a semigroup does not require an identity.

Definition. an element a is a generator of b if it is the case that there exists a positive integer $n$ such that $a^n = b$.

The main theorem that we will be considering today is that this generation preorder is a subpreorder of the commutativity preorder. This means that if b is generated by a, then b commutes with every element that a does.

Theorem. the subcommutativity preordering is a subpreordering of the generator preordering.

Proof. suppose that a generates b, then we know by definition that there exists a positive integer $n$ such that $b = a^n$. We will show that if $c$ commutes with $a$ then it commutes with $a^n$. If $n = 1$ then $a^n = a$ and since $a$ commutes with $c$ we know that $a^n$ commutes with $c$. By induction suppose that it holds for $n = k$ then if we have $a^(k+1)$ it is equal to $a * a^k$ so if we take $(a * a^k) * c$ we know that $a^k$ commutes with $c$ and by associativity we get $a(c*a^k)$ now since $c$ commutes with $a$ by associativity we get $c*(a*a^k)$ which equals $c*a^(k+1)$.

Basically, we can use the base case of commutativity, with the property of associativity iteratively to get commutativity for all generated elements. The importance of this theorem is that although there are multiple preorderings on a semigroup, they are not unrelated to one another. The different preorders can themselves be related to another by preordering. An important result of this, is that generation equality leads to commutativity equality. Generation equality occurs in cyclic subgroups, who have $\varphi(n)$ generators. Each order $n$ element in a subgroup, therefore has $\varphi(n)$ generation and commutativity equal elements.

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8

This implies that non-trivial groups tend to have a lot of commutativity-equal elements. Therefore, it might be useful to take the equality-quotient of the commuting graph when studying the commuting graphs of groups. In fact, all non-binary finite groups have commutativity-equal elements. Even the symmetric group S3 which is the smallest non-commutative group has two elements that are commutativity equal : the two elements of order three. This commutativity-equality is preserved even if the non-binary group is embedded in a larger semigroup, as the parent semigroup preserves generation equality it must preserve commutativity-equality.