Commuting graphs of subsemigroup lattices

Let $S$ be a semigroup. Then the commuting graph on $S$ has an underlying set consisting of the elements of $S$, however, we often want to work with subalgebras rather then individual elements. We can address this by creating a commuting graph on $Sub(S)$.

Definition. Let $Sub(S)$ be the lattice of subsemigroups of a semigroup $S$. Then the commuting graph $G$ on $Sub(S)$ has subsemigroups as vertices and the following binary family of sets as an edge set: \[ \{\{A,B\} : \forall x \in A, y \in B : xy = yx\} \] This means that $Sub(S)$ is simultaneously a lattice and a graph. Recall that graphs are naturally preordered by adjacency: one vertex is greater then another if it is adjacent to more elements then it. These two preorders have the following interesting relationship:

Theorem 1. Let $S$ be a semigroup and $G$ the commuting graph on $Sub(S)$. If $A,B \in Sub(S)$ and $A \subseteq B$ then $Adj_G(b) \subseteq Adj_G(a)$

Proof. Let $X$ be any given subsemigroup that commutes with $B$ then we have that $\forall x \in X, y \in B : xy=yx$. We have that $A \subseteq B$ which means that $\forall x: x \in A \implies x \in B$. Therefore, suppose $x \in X$ and $y \in A$ then we have $x \in X, y \in B$ and by our original supposition this means that $xy = yx$. $\square$

It follows that the inclusion and commutativity preorderings are inversely related. A related question is when it is that inclusion-comparable subsemigroups commute.

Centers of semigroups:
Recall that the center of a semigroup is the subsemigroup of elements that commute with everything. This forms an idempotent decreasing action on the lattice of subsemigroups $Sub(S)$. It is not monotone, because larger semigroups can have smaller centers. \[ Center : Sub(S) \to Sub(S) \] The image of the $Center$ consists of all commutative subsemigroups. Therefore it is a map from the subsemigroup lattice $Sub(S)$ to its lower set of commutative subsemigroups. We can now address the question of when two inclusion-comparable subsemigroups commute with one another. A pair of semigroups $A \subseteq B$ commute if and only if $A \subseteq Center(B)$.

Theorem 2. Let $S$ be a semigroup and let $A,B \in Sub(S)$ such that $A \subseteq B$ then $A,B$ commute iff $A \subseteq Center(B)$.

Proof. Let $B$ be a subsemigroup then we will show that $Center(B)$ commutes with $B$. Let $c \in Center(B)$ and $b \in B$. Then by the definition of the center $cb = bc$. It follows that $Center(B)$ and $B$ commute, now by theorem 1 if we have $A \subseteq Center(B)$ then $A$ and $B$ commute.

Conversely, suppose that $A \subseteq B$ and $A$ commutes with $B$ this means that $\forall x \in A, y \in B$ we have $xy=yx$. The center of $B$ is equivalent to $\{z \in B : \forall y \in B : zy=yz \}$. By the fact that $A \subseteq B$ we have that every element $x$ of $A$ is in $B$ and by the fact that $A$ and $B$ commute we have $\forall y \in B : xy=yx$. It follows that $x \in Center(B)$. By the fact that every element of $A$ is in the center of $B$ we have $A \subseteq Center(B)$. $\square$

Monogenic subsemigroups:
There is a natural mapping from any semigroup to its lattice of subsemigroups $g : S \to Sub(S)$ defined by mapping any element to the monogenic subsemigroup it generates. \[ g : S \to Sub(S) \] \[ g(x) = cl_{Sub(S)}(\{x\}) \] The kernel of this map is the generator equality relation of the semigroup and its image is the subalgebra system consisting of all monogenic subsemigroups.

Theorem. Let $S$ be a semigroup then $x,y$ commute iff $g(x),g(y)$ commute.

Proof. If $g(x)$ and $g(y)$ commute then we have that $x,y$ commute because $x \in g(x)$ and $y \in g(x)$. Conversely, suppose that $xy = yx$ and consider any element $x^n$ in $g(x)$ and $y^n$ in $g(y)$. Then we will show that $x^ny^n = y^nx^n$. The base case is that $x^ny^n = yx^n y^{n-1}$. Then for any $m$ less then $n$ we have that $y^mx^ny^{n-m} = y^{m+1}x^n y^{n-m-1}$. $\square$

As the commutativity of elements is determined entirely be the monogenic subsemigroups that they generate, it follows that generator equality is a subrelation of adjacency equality. This has been proved before, but it never hurts to restate a corollary.

Corollary. generator equality is a subrelation of adjacency equality

If we have that $G$ is the commuting graph on elements and $G'$ is the commuting graph on subsemigroups then $g : G \to G'$ is a morphism in the category of graphs from $G$ to $G'$ and so we have a second corollary.

Corollary. $g : S \to Sub(S)$ is a graph homomorphism from the commuting graph of elements to the commuting graph of the subsemigroup lattice

It follows that the commutativity graph of the subalgebra system consisting of all monogenic subsemigroups of a semigroup is the commuting graph of the semigroup condensed by generator equality. It doesn't necessarily have to be the overall condensation of the commuting graph because two elements can be commutativity equal even if they don't generate each other. However, the condensation of the commuting graph on elements and the condensation of the commuting graph on monogenic subsemigroups do coincide.

Direct product decompositions:
Let $A,B,C$ be a family of monoids with identity elements $1_A, 1_B, 1_C$. Let $A \times B \times C$ be the direct product of all of these monoids then we can form submonoids $A' : \{(x,1_B,1_C)\}$, $B' : \{(1_A,x,1_C)\}$, $C' : \{(1_A,1_B,x)\}$. The family of submonoids $\{A',B',C'\}$ forms a commuting clique. This can be generalized to direct products of any size. This is the quintessential example of subsemigroup commutativity.

Definition. let $S$ be a monoid and let $a,b$ be elements of the monoid $S$ then $a$ and $b$ are independent provided that there are monoids $M_1,M_2$ and a direct product decomposition $S = M_1 \times M_2$ with submonoids $M_1' = \{(x,1_B)\}$ and $M_2' = \{(1_A,x)\}$ such that $x \in M_1$ and $y \in M_2$.

It is not hard to see that independent elements commute, because they are part of commuting pairs of submonoids in a direct product decomposition. The point of this definition is to formalize independence (in the sense of direct products) of elements of a semigroup. Often times commuting elements are seemingly independent in the sense that they effect different things, but that is not always the case, and this distinguishes when that is the case. In general, we see that the components of a direct product decomposition commute.

This is one final case worth mentioning. Recall that meet-minimal normal subgroups commute and if they are also join-maximal they form a direct product decomposition of the group. This is an important special case of the commutativity of submonoids in a direct product decomposition, and it demonstrates the utility of commutativity of subgroups in group theory.