by Jade Master
In my last two posts I defined two different perspectives on R-graph decompositions: dependent and fibrational. In this post, I will present a statement of their equivalence. There are many possible equivalences between dependent R-graph decompositions and fibrational ones depending on your context and goals. I am interested more in doing graph theory than category theory, therefore I will choose a statement of equivalence which is relevant to graph algorithms. Before getting into this let's recall the definitions of dependent and structured graph decompositions:
More explanation and examples of the following definitions may be found in my first blog post on this subject.
Definition: For a category R, an R-graph is a function $ G : X \times X \to R$.
For example, let B be the Booleans, i.e. the category with objects 0 and 1 with a unique morphism between them. A B-graph is then a directed graph without multiple edges.
Definition: A R-graph morphism with source $ G: X \times X \to R$ and target $ H: Y \times Y \to R$ is a function $ f: X \to Y$ along with an R-morphism
$ f_{x,y} : G(x,y) \to H(f(x),f(y)) $
for each pair $ x,y \in X$.
In the following definition, $ G_{\mathsf{Set}}$ is the free $ \mathsf{Set}$-graph on an R-graph as defined in my last post. This free $ \mathsf{Set}$-graph is weighted by a 1-element set for every nonzero weight and is weighted by the empty set otherwise. Another definition that we'll need for the following definition is of the $ \mathsf{Set}$-graph $ \mathsf{RMat}$ of all sets and R-matrices. You may find this definition in the previous post.
Definition: An R-graph decomposition is a morphism of $ \mathsf{Set}$-graphs
$ D : G_{\mathsf{Set}} \to \mathsf{RMat}$
for a B-graph G.
A dependent R-graph decomposition is a graph with vertices annotated by sets (called bags) and edges annotated by matrices (called adhesions). These annotations form the data of a morphism of $ \mathsf{Set}$-weighted graphs as defined above. The definition of a fibrational R-graph decomposition is much simpler.
Definition: A fibrational R-graph decomposition is an R-graph morphism
$ f : H \to G_R$
A fibrational R-graph decomposition has a total graph H and shape graph G. Unlike in the dependent perspective, the bags and adhesions are not readily available. However, these bags and adhesions may be constructed via the following construction:
Definition: For a fibrational R-graph decomposition $ f: H \to G_R$, there is a dependent R-graph decomposition $ f^{-1} : G_{\mathsf{Set}} \to \mathsf{RMat}$ which sends a vertex x of G to the preimage $ f^{-1}(x)$ and for an edge $ e:x \to y$ of $ G_{\mathsf{Set}}$ there is an R-matrix
$ f^{-1}(e) : f^{-1}(x) \times f^{-1}(y) \to R$
defined by $ f^{-1}(e)(a,b)= H(a,b)$.
In words, $ f^{-1}$ is a dependent R-graph decomposition whose bags are given by the inverse image of f and whose adhesion matrices are given by the corresponding weights of the total graph H.
I claim that the above construction is an isomorphism between fibrational and dependent R-graph decompositions. Before proving this, we must define the domain and codomain of this isomorphism. When defining these sets of fibrational and dependent R-graph decompositions, we will fix the vertices of the shape graph as well as the bags sitting above it.
Definition: A partition of a set A by a set X is a function $ P: A \to X$. A fibrational R-graph decomposition agrees with P if its underlying function is given by P. A dependent R-graph decomposition agrees with P if its shape graph has vertices given by X and its bags are equal to $ P^{-1}(x)$. Let $ \mathsf{fib}(P)$ be the set of fibrational R-graph decompositions which agree with P, and let $ \mathsf{dep}(P)$ be the set of dependent R-graph decompositions which agree with P.
Theorem: The construction $ (-)^{-1}$ defined above is an isomorphism of sets
$ (-)^{-1} \mathsf{fib}(P) \cong \mathsf{dep}(P)$
Proof: We just need to supply an inverse mapping. This inverse mapping is a variant of the infamous Grothendieck construction.
Lemma: For a dependent R-graph decomposition $ D: G_{\mathsf{Set}} \to \mathsf{RMat}$, its total graph is the R-graph $ \int D$ whose vertices are elements of the set
$ \bigcup_{x \in Vert(G)} D(x)$
and for vertices $ a \in D(x)$ and $ b \in D(y)$, their weight is given by
$ \int G(a,b) = D(x,y)(a,b)$
Furthermore, $ \int D$ has a natural R-graph morphism $ p: \int D \to G_R$ which sends each vertex to the vertex it sits over (i.e.\ if $ a \in D(x)$ then $ p(a)=x$). p is an R-graph morphism making it into a fibrational graph decomposition.
It remains to show that $ (-)^{-1}$ and $ \int$ are inverse operations. For a dependent decomposition D, $ (\int D)^{-1}$ has the same shape graph as D because G is unchanged by both operations. On edges, $ (\int D)^{-1}$ sends a nonempty edge from x to y to an R-matrix
$ q : \int D ^{-1} (x) = D(x) \times \int D^{-1} (y) = D(y) \to R$
given by $ q(a,b) = \int D(a,b) = D(x,y)(a,b)$. So this matrix f agrees with $ D(x,y)$.
Conversely, suppose we have a fibrational R-graph decomposition $ f : H \to G_R$, then $ \int f^{-1}$ has the same shape graph G as f. For vertices a and b with $ f(a)=x$ and $ f(b)=y$, $ \int f^{-1} (a,b) = f^{-1}(x,y)(a,b) = H(a,b)$. This proves that the two operations are inverses $ \blacksquare$.
It may seem odd that I have chosen an extremely strict version of the Grothendieck construction which fixes a partition. This Grothendieck construction is so strict that we have an isomorphism of sets rather than an equivalence of categories. In the next blog post, I will show that we have more than just an isomorphism of sets, but actually an isomorphism of semirings where the semiring structure is given by suitable adaptations of the usual matrix sum and product of matrices. This isomorphism of semirings will be crucial for defining a class of compositional matrix algorithms and, as you'll see in the next installment, it won't be possible unless we fix a partition set first.