Pullback in the category of graphs

Mathematics Asked by Taroccoesbrocco on October 27, 2020

Consider the category of (undirected) multigraphs (possibly with loops) and multigraph homomorphisms.
What are pullbacks in such a category? Is there an informal, colloquial and intuitive way to describe them?

According to the definition of pullback, given the multigraphs $G_1 = (V_1, E_1, r_1)$, $G_2 = (V_2, E_2, r_2)$ and $G$ and two multigraph morphisms $h_1 colon G_1 to G$ and $h_2 colon G_2 to G$, the pullback of $h_1$ and $h_2$ exists and (I guess) should be a multigraph $G’$ whose vertices are couples $(v_1,v_2) in V_1 times V_2$ and whose edges are couples $(e_1, e_2) in E_1 times E_2$ such that their components are identified via $h_1$ and $h_2$, i.e. $h_{1_V}(v_1) = h_{2_V}(v_2)$ and $h_{1_E}(e_1) = h_{2_E}(e_2)$.

But what does it mean intuitively? What does $G’$ look like? It seems to me that $G’$ sounds like the "minimal" multigraph "compatible" with $h_1$ and $h_2$, but I am not sure this informal explanation makes sense.

I guess I can find more information in the reference suggested in the accepted answer of this question, but I cannot access it.


An (undirected) multigraph (possibly with loops) is a triple $G = (V,E,r)$ where $V$ is the set of vertices, $E$ is the set of edges, and $r colon E to { {v,w} mid v,w in V}$ associates every edge with its two endpoints (possibly they coincide).

Given two multigraphs $G = (V, E, r)$ and $G’ = (V’, E’, r’)$, a multigraph homomorphism $h colon G to G’$ is a couple $h = (h_V colon V to V’, h_E colon E to E’)$ of functions that "preserve edges", i.e. such that if $r(e) = {v,w}$ then $r'(h_E(e)) = {h_V(v), h_V(w)}$.

2 Answers

Simple Graphs

By way of example, suppose we consider the category of simple graphs; i.e., objects are sets along with binary relations and arrows are functions preserving relationships.

Let us write $V(X)$ for the (vertex) set of an object $X$, and $E(X)$ for its binary (edge-adjacency) relation.

Then, the pullback of $f : A → C ← B : g$ is the graph $A times_C B$ with set $V(A times_C B) = {(a, b) | f, a = g, b} = V(A) times_{V(C)} V(B)$ and its relation is $E(A times_C B) = E(A) times E(B)$ where relation multiplication means $(a, a′) ;(R × S); (b, b′) quad≡quad a ,R, a′ ;∧; b,S,b′$.

What are the remaining pieces of the pullback construction?

Pullbacks form intersections of subobjects

That is, the pullback [above] is obtained by forming the ‘intersection’ [loosely, as discussed below] of vertices, and keeping whatever edges that are in the intersection.

In general, if we think of $f : A → C ← B : g$ as identifying when two elements are the ‘same’ ---i.e., “a and b are similar when the f-feature of $a$ is the same as the g-feature of $b$”--- then the pullback yields the ‘intersection’ upto this similarity relationship. For a honest-to-goodness equivalence relationship, one considers ‘equalisers’

Moreover, say a graph $X$ is ‘complete’ when $E(X) ≅ V(X) times V(X)$, then it can be quickly shown that if $A$ and $B$ are complete graphs then so is their pullback; thus the category of complete simple graphs also has pullbacks.

Concrete Example

Consider the following graphs: $A = •_1 → •_2 → •₃$ and $B = •₄ → •₅ → •₆$ and $C = •₇ →_→ substack{•₈ \ •₉} →_→ •₁₀$ ---here $C$ has two arrows from 7, one to 8 and one to 9, which each have an arrow to 10; drawing is hard!

Let $f = {1 ↦ 7, 2 ↦ 8, 3 ↦ 10}, g = {4 ↦ 7, 5 ↦ 9, 6 ↦ 10}$; ---i.e., $A$ sits on the top part of $C$ while $B$ sits on the bottom part.

Exercise: Form their pullback!

Notice that $A, B, C$ are all connected whereas their pullback is not; as such, the category of connected simple graphs doesn't have pullbacks.

Correct answer by Musa Al-hassy on October 27, 2020

Your intuition that the pullback "sounds like the "minimal" (actually maximal) compatible multigraph is true, and in fact is true in many more cases.

This is because the pullback of $Xxrightarrow{f}Zxleftarrow{g}Y$ in any category is the equalizer of the parallel pair $Xtimes Y rightrightarrows Z$ given $fcirctext{pr}_X$ and $gcirctext{pr}_Y$.

Specializing to your case of multigraphs:

  • the product of $G_1 = (V_1,E_1,r_1)$ and $G_2 = (V_2,E_2,r_2)$ is $(V_1times V_2,E_1times E_2,r_1times r_2)$
  • the equalizer of a parallel pair $f,g:G_1rightrightarrows G_2$ is the maximal subgraph of $G_1$ where $f=g$

Combining these two, we get

  • the pullback of $G_1xrightarrow{f}Gxleftarrow{g}G_2$ isthe maximal subgraph of $(V_1times V_2,E_1times E_2,r_1times r_2)$ where $fcirctext{pr}_{G_1}$ and $gcirctext{pr}_{G_2}$

Answered by Daniel Plácido on October 27, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP