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

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:

\alpha_E \operatorname{⨟}H(\operatorname{src}) = G(\operatorname{src}) \operatorname{⨟}\alpha_V \qquad\text{and}\qquad \alpha_E \operatorname{⨟}H(\operatorname{tgt}) = G(\operatorname{tgt}) \operatorname{⨟}\alpha_V.

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.¹ For example, the graphs

using Catlab.Graphs, Catlab.CategoricalAlgebra

g = path_graph(Graph, 3)

and

h = Graph(3)
add_edges!(h, [1,2], [3,3])
h

are not homomorphic:

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.

using DataFrames

g = path_graph(ReflexiveGraph, 3)
h = ReflexiveGraph(3)
add_edges!(h, [1,2], [3,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 space² 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 (Hell and Nesetril 2004, 64). 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:

n = 5
path = path_graph(Graph, n)
path2 = ob(product(path, path))

In the category of reflexive graphs, it is:

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:

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.³) Finally, in the category of symmetric reflexive graphs, the product is:

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:

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.

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.⁴ 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.

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:

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 (Lawvere 1986). Of course, in settings far removed from geometry, ordinary graphs may be preferred for their simplicity.