Graph Homomorphism

definition example theorem

A graph homomorphism $\alpha :G\to H$ between graphs consists of functions ${\alpha }_V:G(V)\to H(V)$ and ${\alpha }_E:G(E)\to H(E)$ such that

$${\alpha }_V\circ G(\mathrm{src})=H(\mathrm{src})\circ {\alpha }_E\text{and}{\alpha }_V\circ G(\mathrm{tgt})=H(\mathrm{tgt})\circ {\alpha }_E,$$

i.e. it “preserves sources and targets”: an edge $a\to b$ goes to an edge ${\alpha }_V(a)\to {\alpha }_V(b)$. Exactly as a functor sends $A\to B$ to $F(A)\to F(B)$. The two conditions are commutative squares — the naturality squares of a Natural Transformation between $G,H:\mathsf{Gr}\to \mathbf{Set}$.

Sources: Kittenlab Lecture 6 (“Sneak peak: natural transformations”), 7; 7 Sketches §3.3.5, Example 3.63, Exercise 3.64; CTfS Definition 3.3.3.1, Remark 3.3.3.2, Example 3.3.3.3, Exercises 3.3.3.5–3.3.3.6, 4.1.1.14–4.1.1.15, Example 4.3.1.12

Example 3.63/7S Exercise 3.64. $G=1\stackrel{a}{\to }2\stackrel{b}{\to }3$, $H=4\stackrel{c,d}{\to }5\circlearrowleft e$. The unique homomorphism with ${\alpha }_E(a)=d$ has ${\alpha }_E(b)=e$, ${\alpha }_V(1)=4$, ${\alpha }_V(2)={\alpha }_V(3)=5$.

Example (Kittenlab). A three-colouring of $G$ is a homomorphism into the triangle graph $K_3$: adjacent vertices get different colours because $K_3$ has no loops. Catlab’s homomorphisms search solves such constraint problems.

“Arrows are bound to their vertices” (CTfS Remark 3.3.3.2): one cannot send an arrow $1\to 2$ to an arrow $1^{\prime }\to 3^{\prime }$ while sending $2\mapsto 2^{\prime }$. The two squares can equivalently be packaged as one square with $(\mathrm{src},\mathrm{tgt}):E\to V\times V$ and ${\alpha }_V\times {\alpha }_V$ (CTfS Exercise 3.3.3.6). A homomorphism sends paths to paths of the same length; if ${\alpha }_V,{\alpha }_E$ are injective so is the induced map on paths, but surjectivity on vertices and arrows does not imply surjectivity on paths (CTfS Exercise 3.3.3.5). A homomorphism is an isomorphism iff both components are bijections (CTfS Exercises 4.1.1.14–4.1.1.15).

$\mathbf{Grph}$ is the category of graphs and graph homomorphisms; its isomorphisms are relabelings; monos are subgraph inclusions.

JuliaLeanHaskell

Docs: Categories & functors · C-set morphisms · ACSets API · Graphs · Vignette: graphs — Kittenlab Lecture 6

using Catlab
G = @acset Graph begin V = 3; E = 2; src = [1, 2]; tgt = [2, 3] end
H = @acset Graph begin V = 2; E = 3; src = [1, 1, 2]; tgt = [2, 2, 2] end
α = ACSetTransformation(G, H; V = [1, 2, 2], E = [2, 3])
is_natural(α)                                    # true
# three-colourings of the 5-cycle
K3 = complete_graph(Graph, 3)                    # (with both edge directions)
length(homomorphisms(cycle_graph(Graph, 5), K3)) # 30

#check Prefunctor            -- V ⥤q W: obj and map, i.e. a graph homomorphism of quivers
#check SimpleGraph.Hom       -- homomorphisms of simple graphs

-- check the two naturality squares on finite graphs
isGraphHom :: (Eq v') => Graph v e -> Graph v' e' -> (v -> v') -> (e -> e') -> Bool
isGraphHom g h fv fe = and [ fv (src g e) == src h (fe e) && fv (tgt g e) == tgt h (fe e) | e <- edges g ]