Fibrations of graphs

A directed graph ${\displaystyle G}$ is given by a set of nodes ${\displaystyle N_{G}}$, by a set of arcs ${\displaystyle A_{G}}$, and by source and target functions ${\displaystyle s_{G}\colon A_{G}\to N_{G}}$ and ${\displaystyle t_{G}\colon A_{G}\to N_{G}}$ that specify the source and the target of each arc. In this article, ${\displaystyle n}$ is denoted for the number of nodes and ${\displaystyle m}$ for the number of arcs.

A graph homomorphism ${\displaystyle \varphi \colon G\to H}$ is given by two functions (ambiguously denoted by the same symbol) ${\displaystyle \varphi \colon N_{G}\to N_{H}}$ and ${\displaystyle \varphi \colon A_{G}\to A_{H}}$, which commute with source and target. That is, ${\displaystyle t_{H}\circ \varphi =\varphi \circ t_{G}}$ and ${\displaystyle s_{H}\circ \varphi =\varphi \circ s_{G}}$. In words, a graph homomorphism maps nodes to nodes and arcs to arcs so to preserve sources and targets.

Each graph ${\displaystyle G}$ generates freely a category ${\displaystyle G^{*}}$ that has the nodes of ${\displaystyle G}$ as objects and the paths of ${\displaystyle G}$ as arrows (composition is concatenation, and the empty paths pointed at each node are the identities). Given a graph homomorphism ${\displaystyle \varphi \colon G\to B}$, the free-category functor gives a functor ${\displaystyle \varphi ^{*}\colon G^{*}\to B^{*}}$. The homomorphism ${\displaystyle \varphi }$ is a graph fibration^[1] when ${\displaystyle \varphi ^{*}}$ is a categorical fibration. The definition of categorical fibration^[2] is credited to Grothendieck.^[3]

An elementary definition of fibration can be easily derived: ${\displaystyle \varphi \colon G\to B}$ is a fibration if and only if for every arc ${\displaystyle a}$ of ${\displaystyle B}$ and every node ${\displaystyle x}$ of ${\displaystyle G}$ such that ${\displaystyle \varphi (x)=t(a)}$ there exists a unique arc ${\displaystyle a^{x}}$ of ${\displaystyle G}$ satisfying ${\displaystyle \varphi (a^{x})=a}$ and ${\displaystyle t(a^{x})=x}$. The graph ${\displaystyle G}$ is the total graph of the fibration, and ${\displaystyle B}$ is its base. The set of nodes of ${\displaystyle G}$ mapped to a node ${\displaystyle x}$ of ${\displaystyle B}$ is called the fibre over ${\displaystyle x}$.^[1]

A homomorphism (node mapping is defined by colors) that is not a fibration. The loop on the grey node lacks a lifting, and the other arc has too many.

A fibration (node mapping is defined by colors). Every arc in the base can be uniquely lifted along the fibre of its target.

The property defining fibrations is called the lifting property: each arc of ${\displaystyle B}$ can be uniquely lifted along the fibre of its target. The figure on the left shows two graphs and a homomorphism specified implicitly by the colours on the nodes. The homomorphism is not a fibration because the loop on the grey node lacks a lifting, and the other arc has too many. By repeating the lifting for all arcs coming into a node ${\displaystyle x}$ of ${\displaystyle B}$, we obtain a local in-isomorphism—a bijection between the in-neighbourhood of ${\displaystyle x}$ and that of every ${\displaystyle y}$ in the fibre of ${\displaystyle x}$.

Dually, an opfibration has the property that each arc of ${\displaystyle B}$ can be uniquely lifted along the fibre of its source.

The connection with categorical fibrations was noted (and, in fact, used as a definition) by Paolo Boldi and Sebastiano Vigna,^[1] but the elementary definition appeared several times in previous literature with different names. However, Grothendieck's definition is the oldest appearance of the idea (albeit in a very general form); the definition was, in turn, inspired by the topological definition of fibration (from which terms such as "fibre", "total graph", and "base" are derived).

Universal total graphs and minimum bases

Two important concepts about fibrations are the universal total graph at ${\displaystyle x}$—the unique largest in-tree fibred over ${\displaystyle G}$ whose root is mapped to ${\displaystyle x}$ (AKA the view at, in-tree at, or unfolding from ${\displaystyle x}$)—and the minimum base (AKA coarsest equitable partition or Weisfeiler–Leman canonical form)—the smallest graph over which ${\displaystyle G}$ can be fibred. They are strictly linked, as the universal total graphs of the minimum base are all distinct but, as a set, they are equal to the universal total graphs of ${\displaystyle G}$. The minimum fibration base is fibration prime, that is, it cannot be fibred nontrivially and epimorphically.^[1]

The universal total graph and the minimum base are almost ubiquitous concepts—even in situations where there is no explicit notion of fibration. Typical examples are the unfolding of a nondeterministic automaton (appearing, e.g., in concurrency theory), and the minimisation of a sofic system (a particular kind of finite-state automaton—see below).

It is immediate to prove by lifting that an (op)fibration with strongly connected base is epimorphic (i.e., both the node and arc components are surjective). Because of this fact, in some context (op)fibrations have been directly defined as epimorphisms; however, there is no need for such a restriction, as most of the relevant results can be proved without this additional condition. In symbolic dynamics, for instance, it is often assumed that all nodes have strictly positive indegree and outdegree: again, the theory of graph (op)fibrations can be developed without such assumptions.

Several properties of factor maps proved in the context of symbolic dynamics have interesting categorical counterparts. For instance, Masakazu Nasu proved that if the functor ${\displaystyle \varphi ^{*}\colon G^{*}\to B^{*}}$ has bounded fibres (in dynamicspeak, it must be uniformly finite-to-one) the characteristic polynomial of ${\displaystyle B}$ divides that of ${\displaystyle G}$ and the maximum eigenvalue is the same.^[4]

A graph homomorphism that is both a fibration and an opfibration is a covering. In this case, the whole neighbourhood of ${\displaystyle x}$ and that of every ${\displaystyle y}$ in the fibre of ${\displaystyle x}$ are in bijection.^[1]

The connection with the more standard, topological notion of graph covering on undirected graphs is immediate once undirected graphs are represented as directed graphs endowed with an involution ${\displaystyle \beta }$ satisfying ${\displaystyle \beta \circ t=s}$ (which implies ${\displaystyle \beta \circ s=t}$). The involution identifies arcs in opposite directions, and each orbit of the involution is identified with an undirected arc. Now a covering (as defined above) preserving involutions is exactly a topological graph covering.^[1]

Indeed, using the definition of covering given above solves the rather subtle issues determined by the presence of loops: for instance, a symmetric graph with one node and two loops has the bidirectional line as universal symmetric covering, but the universal symmetric covering projection is different depending on whether the symmetry is the identity or not; moreover, when only one loop is present the universal symmetric covering reduces to a single bidirectional segment, which accounts for the "loops counted once vs. loops counted twice" dilemma in the definitions found in the literature. Some elaboration on this topic can be found in Boldi and Vigna.^[1]

Note that the combinatorial notion of cover of a graph, in fact, is even older, as it is equivalent to Reidemeister's locally bijective homomorphisms (in German: “Isomorphismus von Streckenkomplex ${\displaystyle {\mathfrak {C}}}$ zu Streckenkomplex ${\displaystyle {\mathfrak {C}}^{*}}$”).^[5][6] Incidentally, Reidemeister defines undirected graphs using an involution as above.

The community working on spectra of graphs (i.e., the study of the eigenvalues of the adjacency matrices of graphs) defined in the sixties the concept of graph (front) divisor (in German, "Teiler"). A graph ${\displaystyle D}$ is a front divisor of ${\displaystyle G}$ if it is possible to build a map ${\displaystyle f\colon N_{G}\to N_{D}}$ so that the number of links going from a node ${\displaystyle x}$ of ${\displaystyle G}$ to all nodes in ${\displaystyle f^{-1}(z)}$ is equal to the number of links going from ${\displaystyle f(x)}$ to ${\displaystyle z}$. The raison d'être of divisors is that if ${\displaystyle D}$ is a divisor of ${\displaystyle G}$ the characteristic polynomial of ${\displaystyle D}$ divides that of ${\displaystyle G}$; this happens because every eigenvector ${\displaystyle \mathbf {x} }$ of ${\displaystyle D}$ can be turned into an eigenvector ${\displaystyle \mathbf {y} }$ of ${\displaystyle G}$ for the same eigenvalue by choosing ${\displaystyle y_{i}=x_{f(i)}}$.^[7]

It is immediate that the existence of an opfibration from ${\displaystyle G}$ to ${\displaystyle D}$ exhibits ${\displaystyle D}$ as a front divisor of ${\displaystyle G}$ (the same holds for rear divisors and fibrations). However, (op)fibrations have a richer structure, as they comprise also a map on the arcs. One could say that (op)fibrations are to divisors as functions are to partitions of the integers. Indeed, many results about graph divisors extend immediately to (op)fibrations (for instance, every group acting on a graph induces a fibration and an opfibration).^[7]

Note that lacking a direct definition of (op)fibration, the connection with graph homomorphism was observed in a different way by Horst Sachs: if ${\displaystyle G}$ covers ${\displaystyle B}$ (in the classical undirected sense) then the characteristic polynomial of ${\displaystyle B}$ divides that of ${\displaystyle G}$.^[8]

Several people in the 1960s and 1970s developed algorithms for graph isomorphism or tests for graph isomorphism starting from the construction of the minimum base of the graph (or the minimum opfibration base). The oldest known explicit mention of the procedure appears in Stephen H. Unger's program for graph isomorphism, where it is called the Extend method.^[13] Immediately after, the same idea appeared in chemistry (and probably elsewhere).^[14] Building on Unger's work, a further refinement was proposed (always starting from a minimum base) by Corneil and Gotlieb.^[15] The technique is sometimes called color refinement.

Cardon and Crochemore^[16] proposed a very efficient computation of the minimum base by exploiting some ideas from Hopcroft's minimal-automaton algorithm.^[17] They claim an ${\displaystyle O(m\log n)}$ time bound, albeit the actual bound is ${\displaystyle O((m+n)\log n)}$.^[18]

Independently from this computer-science related line of development, Boris Weisfeiler and Andrei Leman proposed a reduction of a graph to a canonical form that is just the minimum base.^[19] The name seems to imply that isomorphism between graphs could be decided using isomorphism between minimum bases, and indeed Conjectures 1 and 2 in the paper would lead to that conclusion, but this is not the case (the Weisfeiler–Leman canonical form and its extensions have become recently very popular in the literature about graph neural networks).

In a further independent development, mathematicians have been studying the concept of equitable partition, that is, a partition of the node set that satisfies a requirement equivalent to that of front divisors: the number of vertices of part ${\displaystyle C}$ adjacent to a vertex ${\displaystyle x}$ must depend only on the part of ${\displaystyle x}$. The concept has been introduced by Allen J. Schwenk.^[20] The fact that equitable partitions and divisors were actually the same concept, however, went apparently unnoticed for some time, as well as the connection with graph isomorphism and the Weisfeiler–Leman canonical form.

Brendan McKay used coarsest equitable partitions as a starting point for his graph-isomorphism program nauty (actually, nauty is much more, as it can compute automorphism groups and canonical labellings). The coarsest equitable partition gives exactly the fibres of the minimum base, and McKay describes in his Ph.D. thesis (1975) a partitioning algorithm that is just slightly less efficient (${\displaystyle O(n^{2}\log n)}$) than that of Cardon and Crochemore.^[21]

Both algorithms refine the current partition using a subset of parts; the main difference is in the way this subset of parts is handled—Cardon and Crochemore use the subset to compute directly a refinement in one shot, whereas McKay puts the parts in the subset in a queue and uses them one at a time to build a refinement. The former process lends itself to a tighter analysis, giving a better bound, but the latter may in principle converge more quickly to the result. The two approaches were merged in a coloured version proposed by Boldi, Lonati, Santini and Vigna, working in time ${\displaystyle O(n\log n+m\log(n+m+c)\log n)}$, where ${\displaystyle c}$ is the number of colours.^[9] The latter algorithm is oriented towards very large graphs and requires no data structure—just ${\displaystyle n}$ vectors containing overall ${\displaystyle m}$ integers and six vectors of ${\displaystyle n}$ integers each.

Note that fractional isomorphism of two graphs implies that they have the same minimum base. The two properties are equivalent if the two graphs have the same number of vertices, as the condition is required by the definition of fractional isomorphism.

If a graph is used to represent the structure of a network exchanging messages, and the processors of the network execute the same algorithm starting from the same initial state, the existence of a fibration ${\displaystyle \varphi \colon G\to H}$ implies that, whatever algorithm is used, there are executions in which the behaviour of the nodes in ${\displaystyle G}$ is fibrewise constant (i.e., all processors in the same fibre are always in the same state). Besides providing easy impossibility results, further study provided the effective solution of the distributed computation problem: given a set of networks, a set of communication primitives and a problem (expressed as a relation between inputs and outputs), is there an algorithm solving the problem on all the given networks? Using fibrations it is possible to provide a characterisation that is effective when the set of networks and the problem are finite: that is, there is an algorithm that outputs either a distributed algorithm for the problem, or an impossibility result.^[22] Analogous strong results were proved for a class of self-stabilizing systems.^[23]

The usage of graph homomorphisms to prove impossibility results is not new and started with Dana Angluin's seminal paper, in which it is shown that the existence of a covering projection from a network to a smaller network implies impossibility of election in an interleaved model with bidirectional communication.^[24] The application of graph-theoretical ideas developed in a number of papers (most notably those by Yamashita and Kameda), but it was the application of fibrations that made it possible to prove effective results for a very wide range of models (and, for the first time, for unidirectional communication models).^[22]

The application to distributed systems required some new results: most notably, Nancy Norris' proof that two universal coverings of the same finite graphs are isomorphic if and only if they are isomorphic up to level ${\displaystyle n-1}$,^[25] which was easily extended to universal total graphs by Boldi and Vigna, and the even tighter result that ${\displaystyle n+D}$ levels (where ${\displaystyle D}$ is the diameter) of any universal total graph of a strongly connected fibration-prime graph uniquely identify the latter.^[1]

The researchers working in distributed systems were not aware of the body of knowledge gathered by the community working on symbolic dynamics (see below), so some results were reproved from scratch. Analogously, the known limits on the computational power of graph neural networks based on the Weisfeiler–Leman canonical form are an immediate consequence of analogous impossibility results on distributed systems, but the community working on GNNs was not aware of the connection.^[26] Velarde, Parra, Boldi, and Makse analyze this connection in great detail.^[27]

More generally, fibrations can be used to study the symmetries and the synchronization properties of different kinds of dynamical systems.^[28][29] They have been used in particular to study synchronization patterns in biology.^[30][31][32]

Working on the spectra of trees, Híc, Nedela and Pavlíková previously defined the notion of semicovering projection (in the terminology above, opfibration), and applied it to the symmetric representation of undirected trees.^[33] In particular, they notice the relation with divisors and propose a functional voltage representation. The representation has been reintroduced independently by Boldi and Vigna^[1] and extended to a categorical equivalence between the category of fibrations over ${\displaystyle B}$ and the category of presheaves on ${\displaystyle B^{*}}$. Híc, Nedela and Pavlíková also prove several theorems about the interplay between the automorphism group and front divisors. Some of the results apply only to trees, however (e.g., the minimum base turns out to be the quotient by the automorphism group, which is not true in general).^[33]

The community working on symbolic dynamics and coding has used (op)fibrations in several ways for a long time under the name of (right) left coverings. The encyclopedic book by Lind and Marcus collects the large amount of knowledge gathered in the field.^[34] Some results proved by Boldi and Vigna^[1] in a categorical setting appear here, albeit usually with some additional hypothesis.

A sofic shift is a shift formed by the bi-infinite paths of an arc-labelled graph (the graphs considered are usually strongly connected). From an automaton-theoretic viewpoint, it is an automaton all whose states are initial and final. Right-resolving presentations of a sofic shift correspond to deterministic automata, and the Fischer cover of a right-resolving sofic shift is the smallest such presentation—the minimum deterministic automaton (recognising the same language). Because all states are initial and final, the minimum deterministic automaton is exactly the minimum opfibration base (a dual correspondence relates left-resolving presentations and covers with fibrations). Note that since the involved graphs are deterministic, the theory is radically simplified—universal total graphs are not needed, because the language recognised starting at a node ${\displaystyle x}$ is sufficient to identify nodes with the same universal total graph (the point of the Fischer cover is precisely that the language recognised starting at any two nodes is different—in fibrationspeak, primality). The original definition was restricted to strongly connected graphs, but has been extended by Wolfgang Krieger to general graphs.^[35] Again, these differences are immaterial in the development of fibration theory, as it uses general graphs (in fact, not even necessarily finite).

All algorithms developed for graph partitioning and isomorphism can be used to compute the Fischer/Krieger covers in a very efficient way.

Roy L. Adler and Brian Marcus define (right-) left-resolving maps between shifts of finite type.^[36] The definition is given in terms of the 0-1 matrices that induce the shifts, and if we interpret them as graphs we obtain in nuce the definition of an (op)fibration. There are a number of additional hypotheses on the matrices, however, and the definition is not given for general graphs (the matrices are 0–1, so there are no parallel arcs).

Shortly thereafter, Masakazu Nasu defined (backward-) regular graph homomorphisms,^[37] which are exactly (fibrations) opfibrations; Nasu refers to them as equivalent to the right/left-resolving maps defined by Adler and Marcus, but actually his graphs are more general (albeit finite), and the definition he gives is exactly that of unique lifting along a fibre.

Finally, the definition of (right) left covering given by Lind and Marcus^[34] is identical to that of (op)fibration.

R. F. Williams introduced the notions of subdivision and amalgamation matrices, which can be used as a substitute of left/right-coverings.^[38] Williams introduced also the notions of state splitting and state merging, which when applied to a graph ${\displaystyle G}$ roughly correspond to building a graph fibred over ${\displaystyle G}$ or a graph over which ${\displaystyle G}$ can be fibred, respectively.

There is a very elegant characterization of categorical discrete (op)fibrations that can be easily carried over to the case of graphs: a homomorphism ${\displaystyle \varphi \colon G\to B}$ is a fibration if and only if the following square

is a pullback (dually, ${\displaystyle \varphi }$ is an opfibration if and only if the analogous square with ${\displaystyle t}$ replaced by ${\displaystyle s}$ is a pullback).^[1] Note that the square is simply half of the commutativity conditions of a graph homomorphism. This characterization makes it obvious that (symmetric) (op)fibrations are closed by composition, that is, there is a subcategory of the category of (symmetric) graphs that contains all graphs and (symmetric) (op)fibrations between them.

Some theorems about categorical (op)fibrations can be extended or translated into theorems about graph (op)fibrations. Most importantly, there is a categorical equivalence between presheaves over ${\displaystyle G^{*}}$ and the category of fibrations into ${\displaystyle G}$. The equivalence extends to the case of fibrations the notion of voltage assignment.^[39] The representation of a fibration as a presheaf over ${\displaystyle G^{*}}$ gives, for each arc of ${\displaystyle G}$, a function (the restriction) that describes how arcs are lifted; the function is a bijection in the case of coverings, and corresponds essentially to a coordinate-free voltage assignment.^[1]

Pullbacks of (op)fibrations are (op)fibrations. From this result (and using the classification of coverings of bouquets) it is easy to show that finite regular directed graphs of the same degree have a finite common cover.^[1]