Graph theory on subsets

A common theme in the study of commuting graphs and their centralizers is the theory of adjacency relations between subsets of graphs. There are a number of different possible definitions of adjacency between subsets: but for the purposes of algebraic graph theory and the graph theoretic algebra we are interested in only two:

• Weak adjacency: $A \sim B \Leftrightarrow \exists a \in A, b \in B : a \sim b$
• Strongy adjacency: $A \sim B \Leftrightarrow \forall a \in A, b \in B : a \sim b$

The weak adjacency relationship is used to define quotients in the category of graphs: let $P$ be a partition of $G$ then the relation of weak adjacency on $\frac{G}{P}$ makes the projection $\pi : G \to \frac{G}{P}$ into a graph homomorphism. The relationship of strong adjacency is the key to the theory of centralizers: the centralizer of a set is the largest set is strogly adjacent to.

These relations amongst subsets have an alternate category realisation: let $E \subseteq V^2$ be the symmetric set of ordered pairs of a graph and $\chi : V^2 \to 2$ its subobject classifier. Then use the image functor on the subobject classifier to form a function on subsets of $V^2$: \[ Im(\chi): \wp(V^2) \to \wp(2) \] Then the relationship between two vertex subsets of a graph can be determined by the image of the subobject classifier on the direct product $S \times T$ of two subsets. Two subsets are strongly adjacent if $\chi(S \times T)$ is $\{1\}$ and they are weakly adjacent if $\chi(S \times T)$ is $\{1\}$ or $\{0,1\}$, so the basic relations between subsets of a graph can be formed this way.

The distance between two subsets $S$ and $T$ of $G$ can be defined to be the minimal distance between any pairs of elements in $S$ and $T$, although this doesn't form a metric. We can also define the boundary of a set $S$ to be all elements not in $S$ and adjacent to a member of $S$, and exterior elements are ones not in $S$ or its boundary. Most aspects of graph theory can be generalized to sets in a number of different ways.

It is also customary to generalize operations in abstract algebra from elements to sets. This leads to the various quantales of sets of commutative rings, categories, semigroups, and so on. A case in point is the quantale of morphisms of a category. In graph theory, we can now engage in an analogous process of generalisation to subsets.

Proposition (relation between algebra and graph theory on subsets). Let $A$ be a semigroup and let $S,T$ be subsets of $A$ then if $S$ and $T$ commute with respect to strong adjacency then \[ ST = TS \] As sets are the most basic objects in mathematics, it is fitting that the various operations in algebra and graph theory should be generalized from elements to sets.

See also:
Commuting graphs of subsemigroup lattices: