In mathematics, a fibration of graphs, or graph fibration, is a homomorphism of directed graphs that satisfies a unique lifting property analogous to that of a fibration in topology.
Intuitively, the target (base) graph is "covered" by the source (total) graph in such a way that each arc of the base can be uniquely lifted to any node in the fibre of its target. The concept (or some of its byproducts) has been independently discovered in several areas, including spectral graph theory, distributed computing, symbolic dynamics, graph neural networks, and category theory, under different names such as graph divisor, left or right covering, left or right-resolving map, equitable partition, color refinement, and Weisfeiler–Leman canonical form.
Preliminaries A directed graph is given by a set of nodes , by a set of arcs , and by source and target functions and that specify the source and the target of each arc. In this article, is denoted for the number of nodes and for the number of arcs.
A graph homomorphism is given by two functions (ambiguously denoted by the same symbol) and , which commute with source and target. That is, and . In words, a graph homomorphism maps nodes to nodes and arcs to arcs so to preserve sources and targets.
Categorical definition Each graph generates freely a category that has the nodes of as objects and the paths of as arrows (composition is concatenation, and the empty paths pointed at each node are the identities). Given a graph homomorphism , the free-category functor gives a functor . The homomorphism is a graph fibration when is a categorical fibration. The definition of categorical fibration is credited to Grothendieck.
Elementary definition
An elementary definition of fibration can be easily derived: is a fibration if and only if for every arc of and every node of such that there exists a unique arc of satisfying and . The graph is the total graph of the fibration, and is its base. The set of nodes of mapped to a node of is called the fibre over .
The property defining fibrations is called the lifting property: each arc of 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 of , we obtain a local in-isomorphism—a bijection between the in-neighbourhood of and that of every in the fibre of .
Dually, an opfibration has the property that each arc of 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, 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 —the unique largest in-tree fibred over whose root is mapped to (AKA the view at, in-tree at, or unfolding from )—and the minimum base (AKA coarsest equitable partition or Weisfeiler–Leman canonical form)—the smallest graph over which 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 . The minimum fibration base is fibration prime, that is, it cannot be fibred nontrivially and epimorphically.
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 has bounded fibres (in dynamicspeak, it must be uniformly finite-to-one) the characteristic polynomial of divides that of and the maximum eigenvalue is the same.
Connections with topological graph theory
A graph homomorphism that is both a fibration and an opfibration is a covering. In this case, the whole neighbourhood of and that of every in the fibre of are in bijection.
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 satisfying (which implies ). 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.
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.
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 zu Streckenkomplex ”). Incidentally, Reidemeister defines undirected graphs using an involution as above.
Divisors and spectrum
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 is a front divisor of if it is possible to build a map so that the number of links going from a node of to all nodes in is equal to the number of links going from to . The raison d'être of divisors is that if is a divisor of the characteristic polynomial of divides that of ; this happens because every eigenvector of can be turned into an eigenvector of for the same eigenvalue by choosing .
It is immediate that the existence of an opfibration from to exhibits as a front divisor of (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).
Note that lacking a direct definition of (op)fibration, the connection with graph homomorphism was observed in a different way by Horst Sachs: if covers (in the classical undirected sense) then the characteristic polynomial of divides that of .
Lifting and lowering of eigenvectors
Given a fibration and a vector indexed by , define the (right) lifting of along , denoted , by (essentially, we copy the components of along each fibre). If is an eigenvector of , then is an eigenvector of for the same eigenvalue (as in the case of divisors), as .
Symmetrically, if is a vector indexed by , define the (left) lowering of along , denoted , by adding up the values of along each fibre. If is an eigenvector of and is not zero, then is an eigenvector of for the same eigenvalue.
These results induce a number of relationships between the eigenvalues and eigenvectors of two graphs related by a fibration (dual results exist for opfibrations). Note however that the abovementioned results by Nasu<ref name="nasu1982" /> show that divisibility of characteristic polynomials is provable under weaker conditions, as if is an (op)fibration has bounded fibres, but there are graph homomorphisms inducing free functors with bounded fibres that are not a composition of (op)fibrations, as shown by Bruce Kitchens in his Ph.D. thesis and reported by Kitchens, Marcus, and Trow.
Lifting and lowering of damped spectral rankings Using a slight extension of the same argument, given a weight-preserving fibration between weighted graphs, one can prove thatfor every for which the summations converge. The two expressions define a damped spectral ranking on and , respectively, with damping factor and preference vectors and . For example, if is weighted stochatically, as in definition of PageRank, one can compute PageRank on , instead of , which might result in a simpler computation. This technique has been used to prove that edge additions in undirected graphs might result in a reduction in PageRank (and other spectral rakings) for one of the endpoints.
Equitable partitions and graph isomorphism
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 method.<ref name="unger"></ref> Immediately after, the same idea appeared in chemistry (and probably elsewhere). Building on Unger's work, a further refinement was proposed (always starting from a minimum base) by Corneil and Gotlieb.<ref name="corneil"></ref> The technique is sometimes called color refinement.
Cardon and Crochemore proposed a very efficient computation of the minimum base by exploiting some ideas from Hopcroft's minimal-automaton algorithm. They claim an time bound, albeit the actual bound is .The very generic name of Cardon and Crochemore's paper ("Partitioning a graph", without any reference to graph isomorphism or color refinement) is probably responsible for the lack of adoption of the algorithm outside of computer science: as a result, the algorithm has been republished several times.
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. 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 adjacent to a vertex must depend only on the part of . The concept has been introduced by