- 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$
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:
No comments:
Post a Comment