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.