5
$\begingroup$

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.


Context.

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)\}$.

$\endgroup$
5
$\begingroup$

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?

The usual projections are readily shown to be graph morphisms, and the mediating arrow for any given $h, k$ is $z ↦ (h\, z, k\, z)$, thereby completing the requirements of the construction... Exercise: Work out the details.


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!

Then their pullback [‘intersection’] is the empty graph on 2 vertices $\substack{• \\ (1, 4)} \quad \substack{• \\ (3, 6)}$ ---i.e., the part of C that both A and B sit over.

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your clear answer. I like the idea of pullback as "lax intersection". In the simple graph part of your answer, when you define the pullback, what are $R$ and $S$? Are they $R = E(A)$ and $S = E(B)$? Moreover, in the category of simple graphs, are relations symmetric (and irreflexive if loops are not allowed)? Finally, in the concrete example part, because of a MathJax issue, I don't see very well the definition of the graph $C$. Does it mean that $V(C) = \{7,8,9,10\}$ and $E(C)$ is the symmetric closure of $\{(7,8), (7,9), (8,10), (9,10)\}$? $\endgroup$ – Taroccoesbrocco Jul 28 '20 at 8:04
  • 1
    $\begingroup$ Yup, $S$ and $R$ are the relations you mentioned. No assumptions are made on the relations; if you ask they be symmetric then you're speaking of undirected simple graphs. For $C$, the vertices are as you've written and likewise the edges ---no closure asked for. All the best ^_^ $\endgroup$ – Musa Al-hassy Jul 28 '20 at 11:11
  • 1
    $\begingroup$ Thank you! I guess we had a misunderstanding because a graph is implicitly undirected for me, and implictty directed for you. $\endgroup$ – Taroccoesbrocco Jul 28 '20 at 11:24
5
$\begingroup$

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 $X\xrightarrow{f}Z\xleftarrow{g}Y$ in any category is the equalizer of the parallel pair $X\times Y \rightrightarrows Z$ given $f\circ\text{pr}_X$ and $g\circ\text{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_1\times V_2,E_1\times E_2,r_1\times r_2)$
  • the equalizer of a parallel pair $f,g:G_1\rightrightarrows G_2$ is the maximal subgraph of $G_1$ where $f=g$

Combining these two, we get

  • the pullback of $G_1\xrightarrow{f}G\xleftarrow{g}G_2$ isthe maximal subgraph of $(V_1\times V_2,E_1\times E_2,r_1\times r_2)$ where $f\circ\text{pr}_{G_1}$ and $g\circ\text{pr}_{G_2}$
$\endgroup$
3
  • $\begingroup$ Thank you for your clear answer. Is there a more precise but still informal and intuitive way to express this, other than "the "minimal or maximal compatible multigraph"? Moreover, why do you say that the pullback is "maximal" instead of "minimal"? $\endgroup$ – Taroccoesbrocco Jul 27 '20 at 20:14
  • $\begingroup$ I intuitively think of an equalizer as the "solution set" of a parallel pair, so perhabs the pullback could be thought as a solution set of functions with the same target but different domains. $\endgroup$ – Daniel Plácido Jul 27 '20 at 21:00
  • 1
    $\begingroup$ maximal is because it's the largest subgraph with said property $\endgroup$ – Daniel Plácido Jul 27 '20 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.