Commutativity-necessary subsemigroups overview

Let $G$ be the commuting graph of a semigroup. Then the following subsets of the commuting graph $G$ are necessarily subsemigroups of any semigroup that has it as its commuting graph.

• Adjacency sets
• Adjacency princpal filters
• Maximal cliques
• The set of all universal vertices
• The intersections of any of these

These concepts are then translated into centralizers, commutative principal filters, maximal commuting cliques, and the center when expressed in algebraic terms rather then graph-theoretic ones. All of these are ensured to be subsets for any semigroup with a given commuting graph. If instead we take a magma, which also has a commuting graph, then none of these subsets are ensured to be closed. Centralizers don't always form submagmas, nor is it the case that monogenic magmas are necessarily commutative. These subsemigroups simply tell us how associativity effects commutativity.

Examples:

Net graph:

The elements 0,1,2 are commutativity-maximal and therefore they are idempotent, furthermore {0,1,2} forms a maximal clique so it is a subsemigroup. Therefore, {0,1,2} forms a subsemilattice of any semigroup with this commuting graph. In this way, we can see how subsemilattices can be inferred from the commuting graph of a semigroup. There are two possible semilattices on three elements that this could be. The sets {0,3},{1,4}, and {2,5} are also maximal cliques and are therefore subsemigroups. Finally, {0,1,2,3},{0,1,2,4}, and {0,1,2,5} are centralizers.

Co-net graph

The sets {0,1,2},{0,1,3},{0,2,4}, and {1,2,5} all form maximal cliques. If we intersect {0,1,2} with any of the other three we get {0,1},{1,2},{0,2} and then if we intersect those we get the commutative principal filters {0},{1},{2} which once again shows that {0,1,2} is a subsemilattice. Except now in this case, we know that the subsemilattice must be the semilattice on a total order of three elements. The three centralizers in this case are {0,1,2,3,4},{0,1,2,3,5}, and {0,1,2,4,5}.

Links

Small graphs

Commutative principal filters

We will now use the commutativity preordering to produce certain subsemigroups of a semigroup. The principal filter of an element in a preorder is the set of all elements greater than or equal to it. The commutative principal filters we will be examining are a special case.

Definition. Let $x$ be an element of a semigroup. Then the commutative principal filter of $x$ consists of all elements of $x$ that are greater than or equal to it in the commutativity preordering $\{ y : \forall a: (xa=ax) \implies (ya=ay) \}$.

We will prove that commutative principal filters are subsemigroups by demonstrating that they are precisely the intersection of all maximal cliques containing an element. Which makes it a subsemigroup by our theorem on the intersection of maximal cliques.

Lemma. Suppose that S is a semigroup, x is an element, and C is the intersection of all maximal cliques containing x. Then every element y of C is commutatively greater than or equal to x.

Let $a$ be an element of S that commutes with x. Then a,x forms a clique but not necessarily a maximal clique. Every clique is a subset of some maximal clique, so there is some maximal clique M that contains a and x, but since y is in the intersection of all maximal cliques it is in every maximal clique including M. Therefore, since y is in M it commutes with a. Therefore, every element a that commutes with x must commute with y, which means that y is commutatively greater than or equal to x.

Lemma. let b be commutatively greater than a, then all the maximal cliques of a contain b

Suppose we have a maximal clique M containing a. By the definition of supercommutativity, we know that b must commute with everything that a does. That means that there is some clique that contains M as well as b. Supposing that M contains b, then we have what we aimed for, if on the other hand it doesn't contain b, we have a greater clique that does which contradicts the condition of maximality. So by contradiction, b is in all the maximal cliques of a.

This demonstrates that the commutative principal filters are equal to the intersection of all maximal cliques containing an element, and that the intersection of all maximal cliques containing an element are the commutative filters. As they correspond in both directions, they are equal.

Lemma. the commutative principal filter and the intersection of all maximal cliques containing an element are equal.

We proved separately that maximal commuting cliques are subsemigroups, and that the intersection of subsemigroups is a subsemigroup, so now we can get to the main point. By the fact that commutative principal filters are the intersection of maximal commuting cliques they are subsemigroup.

Theorem. commutative principal filters are subsemigroups.

This has an immediate corollary, which is useful in studies of commuting graphs. Given a commuting graph of some semigroup, we know that the commutativity-maximal elements are idempotent. This can also be infered by the fact that the commutativity preordering is a superpreordering of the generator preorder, but in either direction it is true.

Theorem. commutativity maximal elements of semigroups are idempotent

Maximal elements in a preorder have no other elements greater than or equal to them, therefore they have a singleton principal filter which leads to a singleton subsemigroup. A singleton subsemigroup contains only a single idempotent element. An immediate result of this is that every semigroup with a commuting graph equal to the cyclic graph C4 is a band. Actually, there only two such semigroups produced by ordered combination of anticommutative bands on two elements that are either isomorphic or anti-isomorphic to one another. The same principle applies to the cyclic graph C5, the complete bipartite graph K2,3, and any other connected triangle-free graph that contains no leaf vertices.

Intersections of maximal commuting cliques

Previously, we demonstrated that maximal commuting cliques of a semigroup form subsemigroups. Therefore, given a commuting graph without knowing what semigroup it is associated with we can get that the maximal commuting cilques of the graph are subsemigroups, but there is more. We can also get the intersections of all maximal cliques, because the intersection of subsemigroups is a semigroup. The proof of this will be briefly stated.

Theorem. the set intersection of subsemigroups is a semigroup

Proof. let S be a semigroup, A,B be subsemigroups, and C be their intersection. Then if x and y are in C, since subsemigroups are closed xy is in A and xy is in B, so xy is in C. Therefore C is a subsemigroup.

With that aside, we can prove that the intersection of any set of maximal commuting cliques forms a subsemigroup.

Corollary. the intersection of any set of maximal commuting cliques forms a subsemigroup.

This corollary is useful in any semigroup whose commuting graph is not P3-free. In the P3-commuting semigroups: A2+identity,A2+zero,and T3 the intersection of the two maximal cliques forms an idempotent singleton. This forms a special case, the center, which is the intersection of all maximal cliques. That the center is the intersection of all maximal cliques can be proven using only graph theory.

Theorem. let G be a graph, then the intersection of all maximal cliques of G is the set of all elements that are adjacent to everything.

Proof. Let $x$ be an element of every maximal clique. Suppose that $y$ then is any element of $G$ not necessarily equal to $x$. Then $y$ is in at least one clique with the simplest case being the commuting clique just containing $y$. If there is a greater clique that contains $y$, which is a maximal clique that also contains $x$ by hypothesis, then since $x$ and $y$ are both in a common clique they are both adjacent.

This proves that the center of a semigroup is a subsemigroup, using only basic graph theory and theorems already proven about semigroups, their maximal cliques, and their intersections. While the center is the simplest case, we will see that there are many more subsemigroups that can be produced by the intersections of maximal commuting cliques.

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.

Maximal commuting cliques

One of the basic problems in semigroup theory is the relationship between subalgebras and commutativity. We will address this question by first considering commuting cliques of a semigroup. A commuting clique is a set of elements, each of which commutes with each other. In other words, a clique in the commuting graph of the semigroup. We will show that semigroup closure maps commuting cliques to commuting cliques.

Theorem. Let $S$ be a semigroup and let $C$ be a commuting clique of the semigroup. Then let $a,b$ be elements of $C$. The product $ab$ commutes with every element of $C$.

Proof. Let $c$ be any element of $C$. We will show that $(ab)c$ = $c(ab)$. By associativity we know that $(ab)c$ equals $a(bc)$. Then by the fact that $b,c$ are both elements of $C$ we know that they commute so $a(bc) = a(cb)$. By associativity we know that $a(cb)$ equals $(ac)b$. By the fact that $ac$ are both elements of $C$ we know this equals $(ca)b$ now finally by associativity this equals $c(ab)$. Applied iteratively this implies that semigroup closure maps commuting cliques to commuting cliques.

Corollary. the maximal commuting cliques of a semigroup form a subalgebra system

This follows from the fact that semigroup closure maps commuting cliques to commuting cliques. Suppose that $M$ is a maximal commuting clique, then by the fact that closure operations are extensive, the closure of $M$ must be greater then or equal to $M$ and by the fact that commuting cliques are mapped to commuting cliques, it must be mapped to a commuting clique greater then or equal to $M$. But $M$ is a maximal commuting clique by definition, so it must be mapped to itself. Therefore its closure must be equal to itself, so it must be a subsemigroup.

This theorem immediately gives us a whole class of subalgebras that can be infered immediately from the commuting graph of the semigroup, without having to consider the semigroup itself. The maximal commuting cliques form a subalgebra system, that is to say a subset of Sub(A), they also form a set system. This set system forms a maximal cliques family, and the underlying graph is the commuting graph. Therefore, in the other direction, the subalgebra system consisting of all maximal commuting cliques fully determines the commuting graph.

Corollary. The maximal commuting cliques of a semigroup form a maximal cliques family and the underlying graph of this family is the commuting graph.

This follows directly from the definition of maximal clique families. We can now add the maximal commuting cliques to our list of subalgebra systems that form interesting set systems. The maximal subgroups for example are a pairwise disjoint set system. In general, most different types of set systems emerge at one point or another from subalgebras.

Lattices of subalgebras

Certain algebraic structures like semilattices have partial orders naturally defined on their elements, while a great many others like groups do not. In fact, groups do not have any natural ordering established on their elements at all. This means that to relate order theory to group theory, a different setting is required other then the elements. This is provided by sets, which are naturally partial ordered by inclusion. The condition of being closed under the operations of the algebraic structure provides for a set of sets of elements which forms a lattice called Sub(A).

Definition. let A be an algebraic structure with a set of n-ary operations defined on A then the set of subsets of the ground set of A that are closed under all the operations of A forms a lattice of sets called Sub(A).

The set of n-ary operations on A is the primary determinant of what Sub(A) will be. Groups have signature (0,1,2) consisting of an identity, inverse, and the group operation and semigroups have signature (2) consisting only of the semigroup operation. Groups as semigroups have strictly more operations but then semigroups but they have fewer subalgebras. This leads to the first deduction of universal algebra, which is that the set of operations of A is inversely proportional to the size of Sub(A).

The torsion-free additive group $(\mathbb{Z},+)$ can take at least three forms depending upon the signature. It can simply a group, a group-as-a-monoid, or a group-as-a-semigroup. Even though they are all defined by the same operation, it is ontologically important to distinguish between them in order to determine Sub(A). The positive integers $\mathbb{Z}+$ form a subsemigroup, the non-negative integers $\mathbb{N}$ form a submonoid, and the even integers $2\mathbb{Z}$ form a subgroup. In this case, the lattice of subsemigroups has strictly more elements then the lattice of submonoids, which in turn has strictly more elements then the lattice of subgroups.

It is not enough to consider the lattice of subalgebras Sub(A). When considering a partial order, one always needs to consider suborders. A set of subalgebras $S \subseteq A$ forms a subalgebra system. Chains of subalgebras are one type of subalgebra system. For example, solvability in groups is determined by a bounds-maintaing subnormal quotient-abelian chain of subgroups. Radical extensions in fields are determined by chains of field extensions such that consecutive filed extensions are formed by simple radicals. This leads to the definition of a subalgebra system.

Definition. let A be an algebraic structure. Then a set $S \subseteq Sub(A)$ of subalgebras of A is a subalgebra system.

Subalgebra systems are also set systems. Suppose, that S is a finite semigroup, then the set of maximal subgroups of S forms a pairwise disjoint sperner family by Green's theorem. The maximal proper subsemigroups of a finite semigroup form a sperner family, which is not necessarily disjoint. Sub(A) itself forms a Moore family as a set system. The closure operation associated with the Moore family can be used to define other sets that are not necessarily subalgebras like minimal generating sets, in the same manner typically done in set theory. Examples of subalgebra systems abound in abstract algebra.