{{more citations needed|date=March 2026}}
In [[mathematics]], a '''fibration of graphs''', or '''graph fibration''', is a [[Graph homomorphism|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 network]]s, and [[category theory]], under different names such as '''[[Fibrations of graphs#Divisors and spectrum|graph divisor]]''', '''[[Fibrations of graphs#Symbolic dynamics and one-sided coverings|left or right covering]]''', '''[[Fibrations of graphs#Symbolic dynamics and one-sided coverings|left or right-resolving map]]''', '''[[Fibrations of graphs#Equitable partitions and graph isomorphism|equitable partition]]''', '''[[Colour refinement algorithm|color refinement]]''', and [[Weisfeiler Leman graph isomorphism test|'''Weisfeiler–Leman canonical form''']].
== Preliminaries == A [[directed graph]] <math>G</math> is given by a set of nodes <math>N_G</math>, by a set of arcs <math>A_G</math>, and by source and target functions <math>s_G \colon A_G \to N_G</math> and <math>t_G \colon A_G \to N_G</math> that specify the source and the target of each arc. In this article, <math>n</math> is denoted for the number of nodes and <math>m</math> for the number of arcs.
A [[graph homomorphism]] <math>\varphi \colon G \to H</math> is given by two functions (ambiguously denoted by the same symbol) <math>\varphi \colon N_G \to N_H</math> and <math>\varphi \colon A_G \to A_H</math>, which [[commutative diagram|commute]] with source and target. That is, <math>t_H \circ \varphi = \varphi \circ t_G</math> and <math>s_H \circ \varphi = \varphi \circ s_G</math>. In words, a graph homomorphism maps nodes to nodes and arcs to arcs so to preserve sources and targets.
== Categorical definition == Each graph <math>G</math> generates freely a [[free category|category]] <math>G^*</math> that has the nodes of <math>G</math> as objects and the [[path (graph theory)|paths]] of <math>G</math> as arrows (composition is concatenation, and the empty paths pointed at each node are the identities). Given a graph homomorphism <math>\varphi \colon G \to B</math>, the free-category [[functor]] gives a functor <math>\varphi^* \colon G^* \to B^*</math>. The homomorphism <math>\varphi</math> is a ''graph fibration'''''<ref name="boldivigna">{{cite journal |last1=Boldi |first1=Paolo |last2=Vigna |first2=Sebastiano |title=Fibrations of Graphs |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=243 |pages=21–66 |year=2002 |issue=1–3 |doi=10.1016/S0012-365X(00)00455-6 |doi-access=free |author-link2=Sebastiano Vigna}}</ref>''' when <math>\varphi^*</math> is a [[Fibred category|categorical fibration]]. The definition of categorical fibration<ref name="borceux">{{cite book |last=Borceux |first=Francis |title=Handbook of Categorical Algebra 2 |series=Encyclopedia of Mathematics and Its Applications |volume=51 |publisher=Cambridge University Press |year=1994}}</ref> is credited to [[Alexander Grothendieck|Grothendieck]].<ref name="grothendieck">{{cite journal |last=Grothendieck |first=Alexander |title=Technique de descente et théorèmes d'existence en géométrie algébrique, I. Généralités. Descente par morphismes fidèlement plats |journal=Séminaire Bourbaki |volume=190 |year=1959–1960 |url=http://www.numdam.org/item/SB_1958-1960__5__299_0}}</ref>
== Elementary definition ==
An elementary definition of fibration can be easily derived: <math>\varphi \colon G \to B</math> is a fibration if and only if for every arc <math>a</math> of <math>B</math> and every node <math>x</math> of <math>G</math> such that <math>\varphi(x) = t(a)</math> there exists a unique arc <math>a^x</math> of <math>G</math> satisfying <math>\varphi(a^x) = a</math> and <math>t(a^x) = x</math>. The graph <math>G</math> is the ''total graph'' of the fibration, and <math>B</math> is its ''base''. The set of nodes of <math>G</math> mapped to a node <math>x</math> of <math>B</math> is called the ''fibre'' over <math>x</math>.<ref name="boldivigna" />
{{multiple image | image1 = Graph non-fibration example.svg | caption1 = 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. | image2 = Graph fibration example.svg | caption2 = A fibration (node mapping is defined by colors). Every arc in the base can be uniquely lifted along the fibre of its target. | total_width = 400 }}
The property defining fibrations is called the ''lifting property'': each arc of <math>B</math> 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 <math>x</math> of <math>B</math>, we obtain a local in-isomorphism—a [[bijection]] between the [[neighbourhood (graph theory)|in-neighbourhood]] of <math>x</math> and that of every <math>y</math> in the fibre of <math>x</math>.<ref name="boldivigna" />
Dually, an ''opfibration'' has the property that each arc of <math>B</math> 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]],<ref name="boldivigna" /> 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).<ref name="grothendieck" />
=== Universal total graphs and minimum bases ===
Two important concepts about fibrations are the ''universal total graph at'' <math>x</math>—the unique largest [[arborescence (graph theory)|in-tree]] fibred over <math>G</math> whose root is mapped to <math>x</math> (AKA the ''view at'', ''in-tree at'', or ''unfolding from'' <math>x</math>)—and the ''minimum base'' (AKA ''coarsest equitable partition'' or [[Weisfeiler Leman graph isomorphism test|''Weisfeiler–Leman canonical form'']])—the smallest graph over which <math>G</math> 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 <math>G</math>. The minimum fibration base is ''fibration prime'', that is, it cannot be fibred nontrivially and epimorphically.<ref name="boldivigna" />
[[File:Graph fibration unfolding example.svg|left|thumb|200px|A graph (top left), its minimum base (bottom left, nodes with the same color are in the same fiber of a minimal fibration) and its infinite total graph at the black node (right).]]
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 finite automaton|nondeterministic automaton]] (appearing, e.g., in [[concurrency theory]]), and the minimisation of a [[Shift of finite type|''sofic system'']] (a particular kind of finite-state automaton—see [[#Symbolic dynamics and one-sided coverings|below]]).<ref name="lindmarcus" />
It is immediate to prove by lifting that an (op)fibration with [[Strongly connected component|strongly connected]] base is [[epimorphism|epimorphic]] (i.e., both the node and arc components are [[surjective function|surjective]]). Because of this fact, in some context (op)fibrations have been directly defined as [[epimorphism]]s; 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 and one-sided coverings|symbolic dynamics]], for instance, it is often assumed that all nodes have strictly positive [[degree (graph theory)|indegree and outdegree]]: again, the theory of graph (op)fibrations can be developed without such assumptions.<ref name="boldivigna" />
Several properties of ''factor maps'' proved in the context of [[#Symbolic dynamics and one-sided coverings|symbolic dynamics]] have interesting categorical counterparts. For instance, Masakazu Nasu proved that if the functor <math>\varphi^* \colon G^* \to B^*</math> has bounded fibres (in dynamicspeak, it must be ''uniformly finite-to-one'') the [[characteristic polynomial]] of <math>B</math> divides that of <math>G</math> and the maximum [[eigenvalue]] is the same.<ref name="nasu1982">{{cite journal |last=Nasu |first=Masakazu |title=Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=39 |issue=2 |pages=171–197 |year=1982 |doi=10.1016/0012-365X(82)90141-8}}</ref>
== Connections with topological graph theory ==
A graph homomorphism that is both a fibration and an opfibration is a ''[[covering space|covering]]''. In this case, the whole [[neighbourhood (graph theory)|neighbourhood]] of <math>x</math> and that of every <math>y</math> in the fibre of <math>x</math> are in [[bijection]].<ref name="boldivigna" />
The connection with the more standard, topological notion of graph covering on [[graph (discrete mathematics)|undirected graphs]] is immediate once undirected graphs are represented as directed graphs endowed with an ''[[involution (mathematics)|involution]]'' <math>\beta</math> satisfying <math>\beta \circ t = s</math> (which implies <math>\beta \circ s = t</math>). The involution identifies arcs in opposite directions, and each [[group action#Orbits and .stabilizers|orbit]] of the involution is identified with an undirected arc. Now a covering (as defined above) preserving involutions is exactly a topological graph covering.<ref name="boldivigna" />
Indeed, using the definition of covering given above solves the rather subtle issues determined by the presence of [[loop (graph theory)|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.<ref name="boldivigna" />
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 <math>\mathfrak C</math> zu Streckenkomplex <math>\mathfrak C^*</math>”).<ref>{{Cite book |last=Reidemeister |first=Kurt |title=Einführung in die kombinatorische Topologie |publisher=Friedr, Vieweg & Sohn A.-G. XII |year=1932 |series=Wissenschaft |volume=86 |location=Braunschweig |arxiv=1402.3906}}</ref><ref>{{Cite journal |last1=Fiala |first1=Jiří |last2=Kratochvíl |first2=Jan |date=2008 |title=Locally constrained graph homomorphisms—structure, complexity, and applications |url=https://linkinghub.elsevier.com/retrieve/pii/S1574013708000178 |journal=Computer Science Review |language=en |volume=2 |issue=2 |pages=97–111 |doi=10.1016/j.cosrev.2008.06.001 |url-access=subscription}}</ref> Incidentally, Reidemeister defines undirected graphs using an involution as above.
== Divisors and spectrum ==
The community working on [[spectral graph theory|spectra of graphs]] (i.e., the study of the [[eigenvalue]]s of the [[adjacency matrix|adjacency matrices]] of graphs) defined in the sixties the concept of graph (front) ''divisor'' (in German, "Teiler"). A graph <math>D</math> is a front divisor of <math>G</math> if it is possible to build a map <math>f \colon N_G \to N_D</math> so that the number of links going from a node <math>x</math> of <math>G</math> to all nodes in <math>f^{-1}(z)</math> is equal to the number of links going from <math>f(x)</math> to <math>z</math>. The ''raison d'être'' of divisors is that if <math>D</math> is a divisor of <math>G</math> the [[characteristic polynomial]] of <math>D</math> divides that of <math>G</math>; this happens because every eigenvector <math>\mathbf{x}</math> of <math>D</math> can be turned into an eigenvector <math>\mathbf{y}</math> of <math>G</math> for the same eigenvalue by choosing <math>y_i = x_{f(i)}</math>.<ref name="cvetkovic" />
It is immediate that the existence of an opfibration from <math>G</math> to <math>D</math> exhibits <math>D</math> as a front divisor of <math>G</math> (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 action|group acting on a graph]] induces a fibration and an opfibration).<ref name="cvetkovic">{{cite book |last1=Cvetković |first1=Dragoš M. |last2=Doob |first2=Michael |last3=Sachs |first3=Horst |title=Spectra of Graphs |publisher=Academic Press |year=1980}}</ref>
Note that lacking a direct definition of (op)fibration, the connection with graph homomorphism was observed in a different way by Horst Sachs: if <math>G</math> covers <math>B</math> (in the classical undirected sense) then the characteristic polynomial of <math>B</math> divides that of <math>G</math>.<ref name="sachs">{{cite journal |last=Sachs |first=Horst |title=Simultane Überlagerung gegebener Graphen |journal=Magyar Tud. Akad. Mat. Kutató Int. Közl. |volume=9 |pages=415–427 |year=1965}}</ref>
=== Lifting and lowering of eigenvectors ===
Given a fibration <math>\varphi \colon G \to B</math> and a vector <math>\mathbf{x}</math> indexed by <math>B</math>, define the (right) ''lifting'' of <math>\mathbf{x}</math> along <math>\varphi</math>, denoted <math>\mathbf{x}^{\varphi}</math>, by <math>(\mathbf{x}^{\varphi})_i = x_{\varphi(i)}</math> (essentially, we copy the components of <math>\mathbf{x}</math> along each fibre). If <math>\mathbf{x}</math> is an [[eigenvector]] of <math>B</math>, then <math>\mathbf{x}^{\varphi}</math> is an eigenvector of <math>G</math> for the same eigenvalue (as in the case of divisors), as <math>\mathbf x^\varphi G = (\mathbf x B)^\varphi</math>.<ref name="cvetkovic" /><ref name="blsv" />
Symmetrically, if <math>\mathbf{x}</math> is a vector indexed by <math>G</math>, define the (left) ''lowering'' of <math>\mathbf{x}</math> along <math>\varphi</math>, denoted <math>{}_{\varphi}\mathbf{x}</math>, by adding up the values of <math>\mathbf{x}</math> along each fibre. If <math>\mathbf{x}</math> is an eigenvector of <math>G</math> and <math>{}_{\varphi}\mathbf{x}</math> is not zero, then <math>{}_{\varphi}\mathbf{x}</math> is an eigenvector of <math>B</math> for the same eigenvalue.<ref name="blsv" />
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 <math>\varphi</math> is an (op)fibration <math>\varphi^*</math> 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.<ref name="kitchens">{{cite journal |last1=Kitchens |first1=Bruce |last2=Marcus |first2=Brian |last3=Trow |first3=Paul |title=Eventual factor maps and compositions of closing maps |journal=Ergodic Theory and Dynamical Systems |volume=11 |issue=1 |pages=85–113 |year=1991 |doi=10.1017/S0143385700006039}}</ref>
=== Lifting and lowering of damped spectral rankings === Using a slight extension of the same argument, given a weight-preserving fibration <math>\varphi \colon G \to B</math> between weighted graphs, one can prove that<math display="block">\mathbf x^\varphi\sum_{i\geq 0} \alpha^i G^i = \left(\mathbf x\sum_{i\geq 0} \alpha^i B^i\right)^\varphi</math>for every <math>\alpha</math> for which the summations converge.<ref name="blsv" /> The two expressions define a ''damped spectral ranking''<ref>{{Cite journal |last=Vigna |first=Sebastiano |date=2016 |title=Spectral Ranking |url=https://www.cambridge.org/core/product/identifier/S2050124216000217/type/journal_article |journal=Network Science |language=en |volume=4 |issue=4 |pages=433–445 |doi=10.1017/nws.2016.21 |issn=2050-1242 |hdl=2434/527942 |hdl-access=free}}</ref> on <math>G</math> and <math>B</math>, respectively, with damping factor <math>\alpha</math> and preference vectors <math>\mathbf x^\varphi</math> and <math>\mathbf x</math>. For example, if <math>G</math> is weighted stochatically, as in definition of [[PageRank]], one can compute PageRank on <math>B</math>, instead of <math>G</math>, which might result in a simpler computation.<ref name="blsv" /> 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.<ref>{{Cite journal |last1=Boldi |first1=Paolo |last2=Furia |first2=Flavio |last3=Vigna |first3=Sebastiano |author-link3=Sebastiano Vigna |date=2023 |title=Monotonicity in undirected networks |url=https://www.cambridge.org/core/product/identifier/S205012422200042X/type/journal_article |journal=Network Science |language=en |volume=11 |issue=3 |pages=351–373 |doi=10.1017/nws.2022.42 |issn=2050-1242 |hdl=2434/1023351 |hdl-access=free}}</ref>
== 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 {{smallcaps|Extend}} method.<ref name="unger">{{cite journal |last=Unger |first=Stephen H. |title=GIT—A Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism |journal=[[Communications of the ACM]] |volume=7 |issue=1 |pages=26–34 |year=1964 |doi=10.1145/363872.363899}}</ref> Immediately after, the same idea appeared in chemistry (and probably elsewhere).<ref>{{Cite journal |last=Morgan |first=H. L. |date=1965-05-01 |title=The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service. |url=https://doi.org/10.1021/c160017a018 |journal=Journal of Chemical Documentation |volume=5 |issue=2 |pages=107–113 |doi=10.1021/c160017a018 |issn=0021-9576 |url-access=subscription}}</ref> Building on Unger's work, a further refinement was proposed (always starting from a minimum base) by Corneil and Gotlieb.<ref name="corneil">{{cite journal |last1=Corneil |first1=D. G. |last2=Gotlieb |first2=C. C. |title=An Efficient Algorithm for Graph Isomorphism |journal=[[Journal of the ACM]] |volume=17 |pages=51–64 |year=1970 |doi=10.1145/321556.321562}}</ref> The technique is sometimes called ''[[Colour refinement algorithm|color refinement]]''.
Cardon and [[Maxime Crochemore|Crochemore]]<ref name="cardon">{{cite journal |last1=Cardon |first1=A. |last2=Crochemore |first2=Maxime |title=Partitioning a Graph in O({{!}}A{{!}} log₂ {{!}}V{{!}}) |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=19 |pages=85–98 |year=1982 |doi=10.1016/0304-3975(82)90016-0}}</ref> proposed a very efficient computation of the minimum base by exploiting some ideas from [[John Hopcroft|Hopcroft]]'s [[DFA minimization|minimal-automaton algorithm]].<ref name="hopcroft">{{cite book |last=Hopcroft |first=John |chapter=An ''n'' log ''n'' Algorithm for Minimizing States in a Finite Automaton |title=Theory of Machines and Computation |publisher=Academic Press |year=1971 |pages=189–196 |doi=10.1016/B978-0-12-417750-5.50022-1 |isbn=978-0-12-417750-5}}</ref> They claim an <math>O(m \log n)</math> time bound, albeit the actual bound is <math>O((m+n) \log n)</math>.<ref>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.</ref>
Independently from this computer-science related line of development, [[Boris Weisfeiler]] and Andrei Leman proposed a reduction of a graph to a [[Weisfeiler Leman graph isomorphism test|'''canonical form''']] that is just the minimum base.<ref name="weisfeiler">{{cite journal |last1=Weisfeiler |first1=Boris |last2=Leman |first2=Andrei |title=The reduction of a graph to canonical form and the algebra which appears therein (English translation by G. Ryabov.) |journal=Nauchno-Technicheskaya Informatsia |volume=2 |issue=9 |pages=12–16 |year=1968 |url=https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf}}</ref> 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 graph isomorphism test|Weisfeiler–Leman canonical form]] and its extensions have become recently very popular in the literature about [[graph neural network]]s).
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 <math>C</math> adjacent to a vertex <math>x</math> must depend only on the part of <math>x</math>. The concept has been introduced by Allen J. Schwenk.<ref name="schwenk">{{cite book |last=Schwenk |first=Allen J. |chapter=Computing the Characteristic Polynomial of a Graph |title=Graphs and Combinatorics |series=Lecture Notes in Mathematics |volume=406 |pages=153–172 |publisher=Springer-Verlag |year=1974 |doi=10.1007/BFb0066438 |isbn=978-3-540-06854-9}}</ref> 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 (mathematician)|Brendan McKay]] used ''coarsest'' equitable partitions as a starting point for his graph-isomorphism program <code>nauty</code> (actually, <code>nauty</code> is much more, as it can compute [[graph automorphism|automorphism groups]] and [[graph canonization|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 (<math>O(n^2 \log n)</math>) than that of Cardon and Crochemore.<ref name="mckay">{{cite journal |last=McKay |first=Brendan |title=Practical Graph Isomorphism |journal=Congressus Numerantium |volume=30 |pages=45–87 |year=1981 |url=http://cs.anu.edu.au/~bdm/nauty/PGI/}}</ref>
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 <math>O(n \log n + m \log(n + m + c) \log n)</math>, where <math>c</math> is the number of colours.<ref name="blsv">{{cite journal |last1=Boldi |first1=Paolo |last2=Lonati |first2=Violetta |last3=Santini |first3=Massimo |last4=Vigna |first4=Sebastiano |title=Graph fibrations, graph isomorphism, and PageRank |journal=RAIRO Informatique Théorique |volume=40 |pages=227–253 |year=2006 |issue=2 |doi=10.1051/ita:2006004 |url=http://www.numdam.org/articles/10.1051/ita:2006004/ |author-link4=Sebastiano Vigna}}</ref> The latter algorithm is oriented towards very large graphs and requires no data structure—just <math>n</math> vectors containing overall <math>m</math> integers and six vectors of <math>n</math> integers each.
Note that [[Fractional graph isomorphism|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.
== Fibrations and distributed systems ==
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 <math>\varphi \colon G \to H</math> implies that, whatever algorithm is used, there are executions in which the behaviour of the nodes in <math>G</math> 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.<ref name="boldivigna_effective">{{cite conference |last1=Boldi |first1=Paolo |last2=Vigna |first2=Sebastiano |title=An Effective Characterization of Computability in Anonymous Networks |book-title= |series=Lecture Notes in Computer Science |volume=2180 |year=2001 |pages=33–47 |publisher=Springer-Verlag |doi=10.1007/3-540-45414-4_3 |conference=Distributed Computing (DISC 2001) |author-link2=Sebastiano Vigna}}</ref> Analogous strong results were proved for a class of [[self-stabilization|self-stabilizing systems]].<ref name="boldivigna_selfstab">{{cite journal |last1=Boldi |first1=Paolo |last2=Vigna |first2=Sebastiano |title=Universal Dynamic Synchronous Self-Stabilization |journal=Distributed Computing |volume=15 |pages=137–153 |year=2002 |issue=3 |doi=10.1007/s004460100062 |author-link2=Sebastiano Vigna}}</ref>
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 [[leader election|election]] in an interleaved model with bidirectional communication.<ref name="angluin">{{cite conference |last=Angluin |first=Dana |title=Local and global properties in networks of processors |book-title= |pages=82–93 |year=1980 |publisher=ACM |doi=10.1145/800141.804655 |conference=STOC '80: Proceedings of the twelfth annual ACM symposium on Theory of computing}}</ref> 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).<ref name="boldivigna_effective" />
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 <math>n - 1</math>,<ref name="norris">{{cite journal |last=Norris |first=Nancy |title=Universal covers of graphs: Isomorphism to depth ''n''−1 implies isomorphism to all depths |journal=Discrete Applied Mathematics |volume=56 |pages=61–74 |year=1995 |doi=10.1016/0166-218X(93)E0133-J}}</ref> which was easily extended to universal total graphs by Boldi and Vigna, and the even tighter result that <math>n + D</math> levels (where <math>D</math> is the [[distance (graph theory)|diameter]]) of any universal total graph of a strongly connected fibration-prime graph uniquely identify the latter.<ref name="boldivigna" />
The researchers working in distributed systems were not aware of the body of knowledge gathered by the community working on [[symbolic dynamics]] (see [[#Symbolic dynamics and one-sided coverings|below]]), so some results were reproved from scratch. Analogously, the known limits on the computational power of [[Graph Neural Network|graph neural networks]] based on the [[Weisfeiler Leman graph isomorphism test|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.<ref name="xu2019">{{Cite conference |last1=Xu |first1=Keyulu |last2=Hu |first2=Weihua |last3=Leskovec |first3=Jure |last4=Jegelka |first4=Stefanie |author4-link=Stefanie Jegelka |author3-link=Jure Leskovec |date=2019 |title=How Powerful are Graph Neural Networks? |book-title= |conference=ICLR 2019 |arxiv=1810.00826}}</ref> Velarde, Parra, Boldi, and Makse analyze this connection in great detail.<ref>{{Cite journal |last1=Velarde |first1=Osvaldo M. |last2=Parra |first2=Lucas C. |last3=Boldi |first3=Paolo |last4=Makse |first4=Hernán A. |date=2026-01-27 |title=The role of fibration symmetries in geometric deep learning |journal=Proceedings of the National Academy of Sciences |language=en |volume=123 |issue=4 |article-number=e2416552123 |doi=10.1073/pnas.2416552123 |issn=0027-8424 |pmc=12849690 |pmid=41564124 |pmc-embargo-date=July 21, 2026 |bibcode=2026PNAS..12316552V}}</ref>
== Synchronization and symmetry in dynamical systems and biology == {{Main|Fibration symmetry}}
More generally, fibrations can be used to study the symmetries and the synchronization properties of different kinds of dynamical systems.<ref>{{Cite journal |last1=Nijholt |first1=Eddie |last2=Rink |first2=Bob |last3=Sanders |first3=Jan |date=November 2016 |title=Graph fibrations and symmetries of network dynamics |url=https://linkinghub.elsevier.com/retrieve/pii/S0022039616301784 |journal=Journal of Differential Equations |language=en |volume=261 |issue=9 |pages=4861–4896 |doi=10.1016/j.jde.2016.07.013 |bibcode=2016JDE...261.4861N |url-access=subscription}}</ref><ref>{{Cite journal |last=Lerman |first=Eugene |date=August 2018 |title=Networks of open systems |url=https://linkinghub.elsevier.com/retrieve/pii/S0393044018301931 |journal=Journal of Geometry and Physics |language=en |volume=130 |pages=81–112 |doi=10.1016/j.geomphys.2018.03.020 |arxiv=1705.04814 |bibcode=2018JGP...130...81L}}</ref> They have been used in particular to study synchronization patterns in biology.<ref>{{Cite journal |last1=Morone |first1=Flaviano |last2=Leifer |first2=Ian |last3=Makse |first3=Hernán A. |date=2020-04-14 |title=Fibration symmetries uncover the building blocks of biological networks |journal=Proceedings of the National Academy of Sciences |language=en |volume=117 |issue=15 |pages=8306–8314 |doi=10.1073/pnas.1914628117 |doi-access=free |issn=0027-8424 |pmc=7165483 |pmid=32234788 |arxiv=2006.06826 |bibcode=2020PNAS..117.8306M}}</ref><ref>{{Cite journal |last1=Alvarez |first1=Luis |last2=Liu |first2=Kuang |last3=Ishida |first3=Cecilia |last4=Sánchez-Pérez |first4=Mishael |last5=Wuchty |first5=Stefan |last6=Makse |first6=Hernán A |date=2025 |editor-last=Barabasi |editor-first=Albert-Laszlo |editor2-last=Bahar |editor2-first=Ivet |title=Symmetries in metabolic networks of Escherichia coli |url=https://academic.oup.com/pnasnexus/article/doi/10.1093/pnasnexus/pgaf080/8081867 |journal=PNAS Nexus |language=en |volume=4 |issue=3 |article-number=pgaf080 |doi=10.1093/pnasnexus/pgaf080 |doi-access=free |issn=2752-6542 |pmc=11937945 |pmid=40144777}}</ref><ref>{{Cite journal |last1=Stewart |first1=Ian |last2=Reis |first2=Saulo D. S. |last3=Makse |first3=Hernán A. |date=2024 |title=Dynamics and bifurcations in genetic circuits with fibration symmetries |journal=Journal of the Royal Society Interface |language=en |volume=21 |issue=217 |article-number=20240386 |doi=10.1098/rsif.2024.0386 |issn=1742-5662 |pmc=11322742 |pmid=39139035}}</ref>
== Semicovers ==
Working on the spectra of [[tree (graph theory)|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.<ref name="hic">{{cite journal |last1=Híc |first1=P. |last2=Nedela |first2=Roman |last3=Pavlíková |first3=S. |title=Front-Divisors of Trees |journal=Acta Mathematica Universitatis Comenianae |volume=LXI |issue=1 |pages=69–84 |year=1992 |url=https://emis.de/ft/15885}}</ref> In particular, they notice the relation with divisors and propose a functional voltage representation. The representation has been reintroduced independently by Boldi and Vigna<ref name="boldivigna" /> and extended to a [[equivalence of categories|categorical equivalence]] between the category of fibrations over <math>B</math> and the category of [[presheaf (category theory)|presheaves]] on <math>B^*</math>. 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 graph|quotient]] by the automorphism group, which is not true in general).<ref name="hic" />
== Symbolic dynamics and one-sided coverings ==
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.<ref name="lindmarcus">{{cite book |last1=Lind |first1=Douglas |last2=Marcus |first2=Brian |title=An Introduction to Symbolic Dynamics and Coding |publisher=Cambridge University Press |year=1995}}</ref> Some results proved by Boldi and Vigna<ref name="boldivigna" /> in a categorical setting appear here, albeit usually with some additional hypothesis.
A ''sofic shift'' is a shift formed by the bi-infinite [[path (graph theory)|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 finite automaton|deterministic automata]], and the ''Fischer cover'' of a right-resolving sofic shift is the smallest such presentation—the [[DFA minimization|minimum deterministic automaton]] (recognising the same [[formal language|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 [[formal language|language]] recognised starting at a node <math>x</math> 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.<ref name="krieger">{{cite journal |last=Krieger |first=Wolfgang |title=On sofic systems. I |journal=[[Israel Journal of Mathematics]] |volume=48 |issue=4 |pages=305–330 |year=1984 |doi=10.1007/BF02760631}}</ref> Again, these differences are immaterial in the development of fibration theory, as it uses general graphs (in fact, not even necessarily finite).<ref name="boldivigna" />
All algorithms developed for [[#Equitable partitions and graph isomorphism|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 [[shift of finite type|shifts of finite type]].<ref name="adler">{{cite book |last1=Adler |first1=Roy L. |last2=Marcus |first2=Brian |title=Topological entropy and equivalence of dynamical systems |series=Memoirs of the American Mathematical Society |volume=20 |year=1979 |at=Definition 3.31}}</ref> 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,<ref name="nasu1983">{{cite journal |last=Nasu |first=Masakazu |title=Constant-to-one and onto global maps of homomorphisms between strongly connected graphs |journal=Ergodic Theory and Dynamical Systems |volume=3 |issue=3 |pages=387–413 |year=1983 |doi=10.1017/S0143385700002042}}</ref> 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<ref name="lindmarcus" /> 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.<ref name="williams">{{cite journal |last=Williams |first=R. F. |title=Classification of Subshifts of Finite Type |journal=[[Annals of Mathematics]] |volume=98 |pages=128–153 |year=1973 |issue=1 |doi=10.2307/1970908 |jstor=1970908}}</ref> Williams introduced also the notions of ''state splitting'' and ''state merging'', which when applied to a graph <math>G</math> roughly correspond to building a graph fibred over <math>G</math> or a graph over which <math>G</math> can be fibred, respectively.
== The categorical side ==
There is a very elegant characterization of categorical discrete (op)fibrations that can be easily carried over to the case of graphs: a homomorphism <math>\varphi \colon G \to B</math> is a fibration if and only if the following square
[[File:Graph fibration comm diag 0.svg|center|frameless|Target function commutative diagram.]]
is a [[pullback (category theory)|pullback]] (dually, <math>\varphi</math> is an opfibration if and only if the analogous square with <math>t</math> replaced by <math>s</math> is a pullback).<ref name="boldivigna" /> 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 [[equivalence of categories|categorical equivalence]] between [[presheaf (category theory)|presheaves]] over <math>G^*</math> and the category of fibrations into <math>G</math>. The equivalence extends to the case of fibrations the notion of [[voltage graph|''voltage assignment'']].<ref name="gross">{{cite journal |last1=Gross |first1=Jonathan L. |last2=Tucker |first2=Thomas W. |title=Generating all graph coverings by permutation voltage assignments |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=18 |issue=3 |pages=273–283 |year=1977 |doi=10.1016/0012-365X(77)90131-5}}</ref> The representation of a fibration as a presheaf over <math>G^*</math> gives, for each arc of <math>G</math>, 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.<ref name="boldivigna" />
[[Pullback (category theory)|Pullbacks]] of (op)fibrations are (op)fibrations. From this result (and using the classification of coverings of [[bouquet graph|bouquets]]) it is easy to show that finite [[regular graph|regular]] directed graphs of the same degree have a finite common cover.<ref name="boldivigna" />
== References == {{reflist}}
{{CC notice|bysa4|url=https://vigna.di.unimi.it/fibrations/|author=Sebastiano Vigna}}
[[Category:Graph theory]] [[Category:Algebraic graph theory]] [[Category:Category theory]] [[Category:Morphisms]]