Graph theoretic algebra

The techniques of algebraic graph theory (AGT): like the categories of graphs, lattices of cores, graph automorphisms, and graph related matrices are well known. The techniques of graph theoretic algebra (GTA) are comparatively less well known. The most important of these are the fibers of binary operations.

Fibers of binary operations:
Let $f : X^2 \to X$ be a binary operation and $x \in X$. Then the fiber $f{-1}(x)$ is a binary relation and so $(X, f^{-1}(X))$ forms a directed graph. In graph theoretic algebra, we will study the properties of binary operations by these fiber graphs.

• A binary operation is called right cancellative, provided that each fiber is a single-valued binary relation. It is left cancellative if each fiber is inverse single-valued.
• A binary operation is cancellative if each fiber is a one to one binary relation.
• A magma is a quasigroup if each fiber is left total, right total, and one to one.
• A binary operation is commutative if each fiber is symmetric.
• A binary operation is anticommutative if each fiber is antisymmetric.
• A semigroup is a null semigroup iff it has a single fiber which is a complete relation.
• The fibers of a right zero semigroup are constant single valued binary relations, and the fibers of a left zero semigroup are inverse constant single valued binary operations.
• The fibers of a band all have a unique loop edge.

In addition to the classification of binary operations by their fiber graphs, we can also speak of the fibers of special elements of a binary operation. In general, the two special types of elements that are most common in binary operations are zero elements and one elements.

• The fiber of zero is the zero divisor graph of the binary operation, formed by all ordered pairs (a,b) that satisfy the condition ab = 0.
• The fiber of one is all inverse pairs. In the case of a monoid, this has the condition that $(b,a),(c,a) \in f^{-1}(1)$ implies that $b = c$ so that the fiber of the identity in a monoid is ordered triple free.

The condition that the fiber of one is symmetric is known as Dedekind finiteness in non commutative algebra. In every finite monoid, the fiber of the identity is symmetric but this need not be the case in general so invertibility commutativity is also a finiteness condition.

If an operation is commutative, its fibers can be considered to be symmetric graphs. Aside from loops, the fibers of a cancellative commutative operation are a triangle free cluster. Likewise, aside from loops the fibers of a finite total order semilattice are star graphs. A tree has cocluster fibers, and so on. This produces an infinite range of graphs associated to binary operations to study.

Commuting graphs:
The commuting graph of a binary operation is a measure of the symmetry of the fibers of the operation. Let $sc$ be the operation which takes any binary relation to its symmetric component and $Com(f)$ be the symmetric commuting graph with $(a,b) \in Com(f) when ab = ba$. Then the commuting graph is the union of the symmetric components of the fibers of the binary operation $f$: \[ Com(f) = \bigcup_{x \in X} : sc(f^{-1}(x)) \] The characterization of the commuting graph as the union of the symmetric components of the fibers of the binary operation is a perfect example of how it is merely a mesaure of the symmetry of the fibers of the binary operation. The commuting graph is also an equivalence subrelation of the kernel of $f$ in the lattice $Part(X^2)$.

Peripheral topics
The basic organizing principle of graph-theoretic algebra is the realisation that the inverse images of a binary operation are binary relations, and so directed graphs. Inverse images are such a simple concept applicable to any function, that this makes for a perfect organizing principle for graph theoretic algebra.

There are a number of other directions you could take like action preorders, green's relations, closure graphs, comparability graphs of action preorders, power graphs, enhanced power graphs, etc but these would take us too far afield from the basic concept of the fibers inherent to a binary operation. The enhanced power graph is a subgraph of the commuting graph, so some of these concepts can be related back to the core of the subject.

References:
[1] Zero-divisor graphs

[2] Dedekind finiteness