Graph Homomorphisms

Module for representing and interacting with graph homomorphisms.

A graph homomorphism φ : G → H is a map on vertices (and edges) that respects the graph structure. This module provides:

• GraphHomomorphism — a graph homomorphism specified by a vertex map.
• fiber_vertices — vertices of the source graph that map to a given target vertex.
• fiber_edges — edges within a single fiber (both endpoints in the same fiber).
• cross_edges — edges whose endpoints lie in different fibers.
• compose — composition of two graph homomorphisms.
• graph_pushout — categorical pushout of a span of graph homomorphisms.

For the action of a graph homomorphism on a cellular sheaf (pushforward), see the Pushforwards module.

GraphHomomorphism

A graph homomorphism φ : G → H specified by a vertex map.

Fields

• vertex_map :: Vector{Int} — vertex_map[i] is the image of source vertex i in the target graph.
• n_target :: Int — number of vertices in the target graph (inferred from the maximum of vertex_map if not provided explicitly).

GraphHomomorphism(vertex_map)

Construct a GraphHomomorphism from a vertex map vector, inferring the number of target vertices from the maximum entry.

compose(f::GraphHomomorphism, g::GraphHomomorphism) -> GraphHomomorphism

Compute the composition g ∘ f (apply f first, then g).

cross_edges(hom::GraphHomomorphism, g::AbstractGraph) -> Vector{Tuple{E,Int,Int}} where E

Return all cross edges of g — edges whose endpoints lie in different fibers.

Each entry is (edge, src_target_vertex, dst_target_vertex) where edge has the concrete edge type produced by edges(g), and src_target_vertex, dst_target_vertex are the images of the edge's source and destination vertices.

fiber_edges(hom::GraphHomomorphism, g::AbstractGraph, tv::Int) -> Vector{Tuple{Int,Int}}

Return all edges of g that are fiber edges of tv: both endpoints map to tv.

fiber_vertices(hom::GraphHomomorphism, tv::Int) -> Vector{Int}

Return the source vertices whose image under hom is tv.

graph_pushout(φ::GraphHomomorphism, ψ::GraphHomomorphism,
              G::SimpleGraph, H::SimpleGraph, nK::Int)
    -> (SimpleGraph, GraphHomomorphism, GraphHomomorphism)

Compute the pushout Q = G ⊔_K H of the span G <--φ-- K --ψ--> H.

nK is the number of vertices in K (i.e. length(φ.vertex_map)).

Returns (Q, jG, jH) where jG : G → Q and jH : H → Q are the canonical graph homomorphisms satisfying jG ∘ φ == jH ∘ ψ (as vertex maps).