Combinatorics on words by commuting graphs

Every cograph is associated with a laminar tree family, which determines the cograph up to complementation. This can be extended to any graph $G$, by hierarchically decomposing the graph by disjoint union and graph join operations.

Commuting graphs determine the extent to which ordering is relevant to algebraic operations. We will use the hierarchical decomposition of commuting graphs to partially order the words of a semigroup by commutativity.

Example 1. the dart graph is associated with the following laminar tree family Example 2. $p_3$ join $p_4$ is associated with the following laminar tree family The distinguishing property of this second laminar tree family decomposition is that it doesn't entirely terminate in singleton sets. This is because $P_3$ join $P_4$ is not a cograph, as it includes $P_4$ as an induced subgraph. In general the hierarchical decomposition by graph joins and disjoint unions terminates in either singletons or graphs with a $P_4$ component.

Parsing words:

Unordered decomposition:
Let $G$ be a connected graph, with non connected complement. Then $G$ is the graph join of connected components $C_1,...C_n$. These connected components form a set partition $C$ of the vertex set of $G$. Let $W$ be a word of the vertices of $G$.

Then we can decompose the word $W$ by $C$. Let $C_i$ be a connected component in $C$ then it consists of a set of values of $G$ and therefore $W$. We can form a susbesquence of $W$ by taking the filter of $W$ with respect to the set of elements in $C_i$. So map $C$ and for each component take the filter of $W$ by $C_i$ to get a set of subwords all of which commute with one another.

This decomposes the word into a set of subwords all of which commute with one another, and which therefore for all intents and purposes can be considered to be unordered. This can be turned into a multiset by taking any of the subwords and determining repetitions.

Ordered decomposition:
Let $G$ be a disconnected graph, then we can form a partition $C$ of the vertex set of $G$ by its connectivity. Then let $W$ be a word expressed in terms of the vertices of $G$.

We can partition $W$ by $C$ by indices. Let $W$ be any word input to $C$ then take the first element it belongs to some class $C_i$. So then we can get the maximal prefix subword $S$ of $C$ of elements all who belong to $C_i$, by looping through elements from the start until we get an element not in $C_i$. Remove the prefix subword and turn it into a component, and continue this recursively for the remaining word.

This decomposes a word into a list of consecutive subwords. This are all still ordered, but the relevance of this ordered decomposition is we can now use unordered decomposition on all the individual connected components produced by this process. By continuing the two approaches we can get a hierarchical decomposition of words.

The parsing algorithm:
Recall that a cograph is hierachically decomposed by the graph join and disjoint union operations, producing a laminar tree family. We can apply this to words in order to get a tree decomposition of a word by a commuting graph into ordered and unordered components.

Algorithm: let $G$ be a graph and $W$ a word then form a hierarchical decomposition by the following recursive process:

1. First, take the subgraph of $G$ with respect to the values of the word $W$, to ensure that we are only dealing with the minimum commuting graph necessary.
2. Check if $G$ is connected. If it is disconnected, take the ordered decomposition of $W$ with respect to its connected components. This forms a partition of $W$ into consecutive subwords. Recursively compute the hierarchical decomposition of each connected component $C_i$ and then form an ordered component containing each of them
3. If $G$ is connected, check if the complement graph $G^C$ is connected. If it is disconnected, $G$ is the graph join of components $C_1, ... C_n$. Then compute the hierarchical decomposition of each of these connected components. Form an unordered component of each of them.
4. Finally, if both $G$ and $G^C$ are connected, then we can terminate this process and return back the original word. It cannot be decomposed further.

This parsing algorithm should allow us to form a hierachical tree decomposition of a word by commuting graphs. The result is a partially ordered word that has both unordered and ordered components determined by commutativity.

Example 1. let $G$ be the dart graph of example 1. Let $W$ be $abcdebcedcbeea$. Then we can form a partially ordered word of the form:

{a,a [{[c,d],b},{e},{b,c},{e},{b,[d,c]},{e,e}]}

Example 2. let $G$ be the dart graph of example. Let $W$ be $cdceacdce$. Then the subgraph containing these words is actually a star graph, and all we can do is pull out the central element:

{a,[c,d,c,e,c,d,c,e]}$

Example 3. let $G$ be the graph of example 2. Let $W$ be the word $aaededdae$ then the subgraph containing $W$ is a clique so this can be decomposed into a multiset:

{a,a,a,d,d,d,e,e,e}

Example 4. let $G$ be the graph of example 2. Let $W$ be the word $abcdef$ then this can be decomposed into a partially ordered word of the form:

{a,[b,c,{d,[e,f]}]}

Data structures:

The hierarchical decomposition of a word by a commuting graph produces a partially ordered word expressed as a tree of ordered and unordered components. This gives rise to a special class of data structure, which is like a collection by internally represented by a tree.

This might be implemented a collection of three Java classes like: PartiallyOrderedWord,UnorderedComponent, and OrderedComponent where the later two are protected classes dealing with the ordered and unordered parts of the partially ordered word. Outwardly, the partially ordered word data type would be appear as a collection, for example a Clojure wrapper over it might implemented seqable.

Common interfaces can be defined for lists, multisets, and partially ordered words. In fact, these partially ordered words subsume the other two as special cases. Lists emerge from empty commuting graphs and multisets emerge from complete commuting graphs. In any case, this produces a richer collection of data structures dealing with words in abstract algebra.