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.

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

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?

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.

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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

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