# Graphs and C-sets III: Reflexive graphs and C-set homomorphisms

c-sets
graphs
Reflexive graphs are graphs where every vertex has a distinguished self-loop. While this may seem inconsequential, reflexive graphs have interestingly different properties than ordinary graphs owing to their different morphisms. We will see that reflexive graphs are more geometrical than graphs and also review the general notion of homomorphism between C-sets.
Author

Evan Patterson

Published

April 19, 2021

Continuing our tour of the many flavors of graphs and their manifestation as \mathsf{C}-sets, we discuss reflexive graphs, a seemingly minor variant of graphs that nonetheless has some interesting and distinctive features. A reflexive graph is a graph where every vertex has a distinguished self-loop, like this: At first glance, the self-loops may seem an inconsequential addition. It is even customary to omit them from drawings, making reflexive graphs more or less interchangeable with graphs as objects. However, the morphisms of reflexive graphs differ significantly from those of graphs and as a result the category of reflexive graphs behaves differently than the category of graphs. We will see that reflexive graphs are more “geometric” than graphs in various ways. For example, if graphs G and H discretize continuous spaces X and Y, then product G \times H will discretize the product space X \times Y only if the graphs are reflexive.

The story of reflexive graphs will give us opportunity to discuss morphisms of \mathsf{C}-sets generally, which we have not yet done in this series. To understand this post, it will be helpful to have read Part I. It is not necessary to read Part II, which goes in a different direction.

## Reflexive graphs

A reflexive graph is a graph G together with a function G(\operatorname{refl}): G(V) \to G(E) that assigns to each vertex v a self-loop at v. In other words, a reflexive graph is a \mathsf{Sch}(\mathsf{RGraph})-set, where \mathsf{Sch}(\mathsf{RGraph}), the schema for reflexive graphs, is the category generated by subject to the equations of the commutative diagram: In Catlab, the schema for reflexive graphs is:

@present SchReflexiveGraph <: SchGraph begin
refl::Hom(V,E)

compose(refl, src) == id(V)
compose(refl, tgt) == id(V)
end

Similarly, a symmetric reflexive graph is a symmetric graph G together with a function G(\operatorname{refl}): G(V) \to G(E) that assigns to each vertex v a self-loop at v, which is fixed under the edge involution. Both reflexive graphs and symmetric reflexive graphs are included in the Catlab module for graphs (Catlab.Graphs).

## Morphisms of \mathsf{C}-sets

The key difference between graphs and reflexive graphs is between their morphisms, so let us review the notion of \mathsf{C}-set homomorphism.

Given a small category \mathsf{C}, a homomorphism, or simply a morphism, of \mathsf{C}-sets X and Y is a natural transformation \alpha: X \Rightarrow Y between the functors X, Y: \mathsf{C} \to \mathsf{Set}. Thus, a homomorphism \alpha: X \to Y consists of a function \alpha_c: X(c) \to Y(c) for each object c \in \mathsf{C}, such that for every morphism f: c \to d in \mathsf{C}, the naturality square commutes. The functions (\alpha_c)_{c \in \mathsf{C}} are called the components of the transformation.

The \mathsf{C}-sets and \mathsf{C}-set homomorphisms then form a category, suggestively denoted \mathsf{C}-\mathsf{Set}, where homomorphisms are composed componentwise and the identity homomorphism has each component the identity function. A homomorphism \alpha of \mathsf{C}-sets is an isomorphism if it has an inverse in \mathsf{C}-\mathsf{Set}, which turns out to be equivalent to each component \alpha_c being an invertible function (Awodey 2010, Lemma 7.11).

## Morphisms of graphs and reflexive graphs

The schema for graphs has only two objects, V and E, and two morphisms, \operatorname{src} and \operatorname{tgt}, so a graph homomorphism \alpha: G \to H consists of a vertex map \alpha_V: G(V) \to H(V) and an edge map \alpha_E: G(E) \to H(E) that preserves the source and target vertices:

When H is a simple directed graph (has at most one directed edge between any two vertices), the edge map is completely determined by the vertex map and we recover the usual notion of simple graph homomorphism. In general, though, the edge map is a nonredundant part of the data of a graph homomorphism.

A reflexive graph homomorphism is a graph homomorphism that preserves the morphism \operatorname{refl}: V \to E, hence sends reflexive loops to reflexive loops. But there is no requirement that only reflexive loops be sent to reflexive loops. This has the effect of allowing reflexive graph homomorphisms to “collapse” edges onto vertices, which is not allowed in graph homomorphisms unless the target graph happens to have self-loops “by accident.” On the other hand, there is no appreciable difference between isomorphisms of graphs and isomorphisms of reflexive graphs since the latter can only send reflexive loops to reflexive loops.

The following computational example illustrates this contrast. For any finitely presented category \mathsf{C}, the functions homomorphism and homomorphisms in Catlab find one or all homomorphsims between two \mathsf{C}-sets.1 For example, the graphs

Code
using Catlab.Graphs, Catlab.CategoricalAlgebra

g = path_graph(Graph, 3) and

Code
h = Graph(3)
h are not homomorphic:

Code
isempty(homomorphisms(g, h))
true

There are seven different homomorphisms between the corresponding reflexive graphs, whose vertex maps are shown in the table below. The rows are homomorphisms \alpha, the columns are vertices v of G, and the cells are the assigned vertices \alpha_V(v) of H.

Code
using DataFrames

g = path_graph(ReflexiveGraph, 3)
h = ReflexiveGraph(3)

αs = homomorphisms(g, h)
df = rename!(DataFrame(Tuple(α[:V]) for α in αs), ["v\$i" for i in 1:nv(g)])
7×3 DataFrame
α │ v1  v2  v3
───┼────────────
1 │  1   1   1
2 │  1   1   3
3 │  1   3   3
4 │  2   2   2
5 │  2   2   3
6 │  2   3   3
7 │  3   3   3

A reflexive graph homomorphism G \to H can always collapse the entirety of G onto a single vertex of H, which accounts for three of the homomorphisms. Of the remaining four, two homomorphisms collapse vertices 1 and 2 of G and the other two collapse vertices 2 and 3. Although reflexive graph homomorphism is clearly weaker than graph homomorphism, it should also be clear that reflexive graph homomorphism imposes significant constraints, as there are 3^3 = 27 different functions G(V) \to H(V) but only 7 extend to homomorphisms.

When graphs are viewed as presentations of metric spaces, reflexive graph homomorphisms fit better with the metric geometry than graph homomorphisms. Any graph or reflexive graph G generates a Lawvere metric space2 X=G(V) where the distance between two points x and x' is the length of the shortest path from x to x' in G. Perhaps the most natural notion of morphism between metric spaces are the nonexpansive maps: a map f:X \to Y between Lawvere metric spaces X and Y is nonexpansive if d_Y(f(x),f(x')) \leq d_X(x,x') for all x, x' \in X. Every graph or reflexive graph homomorphism restricts to a nonexpansive map on the induced metric spaces. However, a nonexpansive map generally only extends to a homomorphism in the case of reflexive graphs . In other words, the functor \mathsf{RGraph}\to \mathsf{Met} is full but the functor \mathsf{Graph}\to \mathsf{Met} is not.

## Cartesian products of graphs and reflexive graphs

In a category of \mathsf{C}-sets, the cartesian product or categorical product is computed by taking the cartesian product of sets “pointwise” with respect to the objects of \mathsf{C}. Specifically, the binary product X \times Y of \mathsf{C}-sets X and Y has elements (X \times Y)(c) = X(c) \times Y(c) for every c \in \mathsf{C}. It is defined on morphisms f: c \to d of \mathsf{C} by

(X \times Y)(f) = X(f) \times Y(f): X(c) \times Y(c) \to X(d) \times Y(d).

In particular, the product of graphs G and H, possibly reflexive or symmetric, has vertex set G(V) \times H(V) and edge set G(E) \times H(E).

Let’s look at the product of the path graph with itself in four different categories. In the category of graphs, this product is:

Code
n = 5
path = path_graph(Graph, n)
path2 = ob(product(path, path)) In the category of reflexive graphs, it is:

Code
path = path_graph(ReflexiveGraph, n)
path2 = ob(product(path, path)) Note that the reflexive loops are omitted from the drawing. Although it is somewhat obscured by the drawings, the disconnected paths in the graph product correspond to the vertical paths in the reflexive graph product. The remaining edges in the latter product come from pairs (e,e') where at least one of e and e' are reflexive loops.

In the category of symmetric graphs, the product of a path graph with itself looks like:

Code
path = path_graph(SymmetricGraph, n)
path2 = ob(product(path, path)) Restricted to simple undirected graphs, graph theorists call this the direct product or tensor product. The reader should consider why this example has two connected components. (It is related to the fact that the path graph is bipartite.3) Finally, in the category of symmetric reflexive graphs, the product is:

Code
path = path_graph(SymmetricReflexiveGraph, n)
path2 = ob(product(path, path)) Graph theorists call this the strong product. The two components in the previous drawing should be imagined superimposed on this one, comprising the horizontal and vertical paths.

Graphs and reflexive graphs also differ with respect to their generalized elements. In a category with a terminal object 1, a generalized element of an object X is a morphism 1 \to X. Note that terminal objects are the nullary case of cartesian products. In a category of \mathsf{C}-sets, the terminal object 1 has 1(c) = \{*\} equal to a singleton set for every c \in \mathsf{C}. In particular, the terminal graph is a self-loop. This means that a graph with no self-loops has no generalized elements:

Code
I = ob(terminal(Graph))
g = path_graph(Graph, 5)
isempty(homomorphisms(I, g))
true

On the other hand, the generalized elements of a reflexive graph correspond exactly to its vertices, as one might expect.

Code
I = ob(terminal(ReflexiveGraph))
g = path_graph(ReflexiveGraph, 5)

αs = homomorphisms(I, g)
df = DataFrame((v1=α[:V](1),) for α in αs)
5×1 DataFrame
α │ v1
───┼────
1 │  1
2 │  2
3 │  3
4 │  4
5 │  5

Thus, reflexive graphs have a more geometric notion of “point” than graphs.

## The box product of reflexive graphs

None of the four products considered above correspond to what graph theorists have traditionally considered the standard product of graphs. That would be the box product.4 From the categorical viewpoint, the box product is a bit curious and and its generalization to categories is affectionately called by category theorists the funny tensor product.

Given a reflexive graph G, let G_0 be the discrete graph on the vertices of G, whose only edges are the reflexive loops. The box product of reflexive graphs G and H, denoted G\,\square\,H, is defined as the pushout in \mathsf{RGraph}: Pushouts in a category generalize unions of sets. It is beyond the scope of this post to precisely describe pushouts of \mathsf{C}-sets, but Catlab can compute them, so we can at least implement the box product and verify that it gives the desired result on path graphs.

Code
using Catlab.Theories

function box_product(g::T, h::T) where T <: ACSet
g₀, h₀ = T(nv(g)), T(nv(h))
incl_g = CSetTransformation((V=vertices(g), E=refl(g)), g₀, g)
incl_h = CSetTransformation((V=vertices(h), E=refl(h)), h₀, h)
proj_g₀, proj_h₀ = product(g₀, h₀)
ob(pushout(pair(proj_g₀ ⋅ incl_g, proj_h₀),
pair(proj_g₀, proj_h₀ ⋅ incl_h)))
end

path = path_graph(ReflexiveGraph, n)
path2 = box_product(path, path) In the category of symmetric reflexive graphs, the box product of path graphs looks like:

Code
path = path_graph(SymmetricReflexiveGraph, n)
path2 = box_product(path, path) Restricting the box product of symmetric reflexive graphs to a monoidal product of simple undirected graphs, we recover the box product as understood by graph theorists.

## Conclusion

A fundamental principle of modern mathematics, and especially of category theory, is that mathematical objects should be studied through their morphisms. This principle has been exemplified by the contrast between graphs and reflexive graphs, which appear similar as objects but form importantly different categories. As we have seen, reflexive graphs are closer to metric spaces and conform better with geometric intuition than graphs. For further reading, a topos-theoretic perspective is offered by Lawvere, who argues that the topos of reflexive graphs satisfies some axioms making it a “topos of spaces” but the topos of graphs does not . Of course, in settings far removed from geometry, ordinary graphs may be preferred for their simplicity.

## References

Awodey, Steve. 2010. Category Theory. 2nd ed. Oxford Logic Guides. London, England: Oxford University Press.
Hammack, Richard, Wilfried Imrich, and Sandi Klavžar. 2011. Handbook of Product Graphs. CRC Press. https://doi.org/10.1201/b10959.
Hell, Pavol, and Jaroslav Nesetril. 2004. Graphs and Homomorphisms. Oxford University Press. https://doi.org/10.1093/acprof:oso/9780198528173.001.0001.
Lawvere, F. William. 1973. “Metric Spaces, Generalized Logic, and Closed Categories.” Rendiconti Del Seminario Matematico e Fisico Di Milano 43 (1): 135–66. https://doi.org/10.1007/bf02924844.
———. 1986. “Categories of Spaces May Not Be Generalized Spaces as Exemplified by Directed Graphs.” In. http://tac.mta.ca/tac/reprints/articles/9/tr9abs.html.

## Footnotes

1. The homomorphism finding procedure in Catlab uses backtracking search, which, despite being fairly simple, is still much faster than brute-force search. A future post will discuss the general correspondence between finding \mathsf{C}-set homomorphisms and solving constraint satisfaction problems.↩︎

2. A Lawvere metric space is like a metric space except that the metric need not be finite, symmetric, or separate points . The Lawvere metric generated by a graph will not be symmetric unless the graph is symmetric and will not be finite unless the graph is strongly connected.↩︎

3. In fact, the tensor product of two connected, bipartite, undirected graphs always has exactly two connected components (Hammack, Imrich, and Klavžar 2011, Theorem 5.9).↩︎

4. Some graph theorists call the box product the “cartesian product,” but this terminology should be avoided because it is not the categorical product in the category of simple undirected graphs or, as far as I know, in any category of graph-like objects.↩︎