Idempotent commutativity

Divisibility commutativity is one way to generalize the commutativity of semigroups, and idempotent commutativity is another. Condensation theory suggests the class of semigroups for which J is a congruence, is a better class of generalization then divisibility commutativity. This class then includes completely regular semigroups and simple semigroups as well as divisibility commutative ones. In the other direction, idempotent commutativity includes inverse semigroups. The interesting thing about the idempotent commutativity generalization of commutativity, is the amount of implications that we can derive from it about the commuting graph of a semigroup. We cannot say nearly as much as we can about idempotent central semigroups, such as Clifford semigroups, much less the amount we can say about groups. The most obvious thing is that the commuting graphs of idempotent commutative semigroups are connected.

Theorem. let $S$ be a finite idempotent commutative semigroup, then the commuting graph of $S$ is connected.

Proof. each finite semigroup has an idempotent. Therefore, each connected component of $S$ has an idempotent. The idempotents of $S$ are commutative, so they must be connected by edges. Therefore, the commuting graph must be connected. $\square$

This is also true for any monoid or 0-simple semigroup. Connectivity is usually first step before you can say anything else interesting about the commuting graph of a semigroup. A next step is to consider the specific idempotents of a graph. The idempotents of a graph are all singleton principal adjacency filters. In this sense, there are many graphs that strictly idempotent. In order for these graphs to be idempotent commutative, they must be complete.

Theorem. let $S$ be a semigroup with order greater then two and a minimum degree two triangle free commuting graph. Then $S$ is not idempotent commutative.

Proof. (1) Compute the maximal commuting cliques of $S$. By the fact that $S$ is triangle free they are all size two. We have that $S$ is minimum degree two so every element of $S$ is in at least two different size two cliques. Take the intersection of them and you get a singleton subsemigroup containing $x$. By the fact that $\{x\}$ is a subsemigroup, we then have that $x$ is idempotent. It follows that $S$ is a band. (2) Finally, by the fact that $S$ has order greater then two, is a band, and is triangle free we have that $S$ cannot be idemponent commutative. $\square$

As there are no divisibility commutative non-commutative bands, semigroups with graphs of the preceding type cannot be divisibility commutative either. The condition of being idempotent commutative means that a semigroup is anticommutative subsemigroup free, which goes a long way towards generalizing commutativity. In an E-semigroup, the condition of being anticommutative subsemigroup-free is equivalent to idempotent commutativity. If a semigroup cannot be commutative, it goes a long way if it at least doesn't have any anticommutative components.

Example 1. the cyclic graph $C_4$ By the previous theorem any $C_4$ commutativity semigroup $S$ is a band, so none of them are idempotent commutative. In fact all such semigroups are subtotal bands: $Sub(S) = \wp(S)$. They come in two forms: mixed or unmixed. The mixed ones combine left or right zero semigroups, while the unmixed ones don't.

Example 2. the complete bipartite graph $K_{2,3}$. This is again the graph of a band. By analogy with the last case, bands with this commuting graph can be formed by any ordered pair of pure rectangular bands, mixed or unmixed. There are more isomorphism types of bands with this commuting graph though because of the different maximal independent set cardinalities.

Example 3. the cyclic graph $C_n$ for any $n \ge 4$ is always the commuting graph of a band. Cyclic graphs are not complete, so these can never be the commuting graph of an idempotent commutative semigroup.

The previous three examples preceded by determining the incomplete strictly idempotent graphs, but we can actually fully classify all idempotent commutative triangle free graphs.

Theorem. let $S$ be a semigroup with triangle-free commuting graph then:

1. If $S$ is idempotent central then its commuting graph is a star graph.
2. If $S$ is idempotent commutative, then its commuting graph is constructed from at most two star graphs by combining them by a bridge between their central vertices

Proof. (1) let $S$ be idempotent central, then $S$ contains a unique central element. This central element must commute with everything. Let $x,y$ be any two elements not equal to the center element, then if $x,y$ commute with one another they form a triangle with the central element, which would contradict the condition of being triangle free. Therefore, all non-central elements are independent which means that $S$ forms a star graph.

(2) we have that every non-leaf node is idempotent. Suppose there is only one non-leaf node then $S$ clearly forms a star graph as mentioned. On the other hand, if $S$ has two non leaf nodes they are clearly connected. These two leaf nodes can have any number of leaf nodes adjoined to them. If we take the leaf nodes of the two non leaf nodes associated to them we get a star graph. The original graph can them be recovered by adjoining the two star graphs. $\square$

Example 1. the tadpole graph $T_{4,1}$ The vertices {0,1,2,3} form idempotents, but they don't form a clique. Therefore, the tadpole graph $T_{4,1}$ cannot be the commuting graph of an idempotent-commutative semigroup.

Example 2. the path graph $P_5$ The vertices {1,2,3} are all idempotent, but they don't form a clique. Therefore, we again have that $P_5$ cannot be the graph of an idempotent commutative semigroup.

Example 3. the path graph $P_n$ cannot be idempotent commutative for $n \ge 5$.

We have now fully classified the types of triangle-free commuting graphs of idemptotent commutative semigroups. To conclude, I will mention something of the non-triangle-free case. In that case it is harder to find idempotents then to look for non leaf nodes.

Theorem. let $S$ be a semigroup and $x$ be a vertex. Then let $G$ be graph of the centralizer of $x$ minus $x$, or in other words the subgraph of proper neighbours of $x$. Then if $G$ has at least two vertices including an isolated vertex $y$ then it is idempotent.

Proof. by the fact that $y$ has no other neighbours of $x$ in its centralizer, the intersection of the centralizers of $x$ and $y$ is $\{x,y\}$. Then get any other adjacent element of $x$, say $z$ then the centralizer of $z$ intersected with $\{x,y\}$ is $\{x\}$. This implies that $x$ is idempotent. $\square$

Example 1. house graph The vertices {0,1,2,3} have relatively isolated neighbours, and so they are idempotent. It follows that this cannot be the commuting graph of an idempotent commutative semigroup.

Example 2. the doubled square The vertices {0,1,2} are idempotent, but zero is not adjacent to two. Therefore, once again this cannot be idempotent commutative.

This demonstrates that there are many commuting graphs that cannot be graphs of idempotent commutative semigroups, even within the class of connected graphs. This could be used to study the commuting graphs of inverse semigroups, or the set of isomorphism types of semigroups associated to commuting graphs.