# Graph Fibrations

The purpose of this page is discuss the definition of a particular kind of graph morphism that has found application in several different fields of mathematics and computer science. Since the idea has been rediscovered several times by different people, it is useful to have a single place where all definitions are compared.

An effort has been made to compare results and to track the oldest definitions. If you find a mistake in the attribution, or missing references, please write me.

## Preliminaries

A *graph* `G` is given by a set of *nodes* `N _{G}`, by a set of

*arcs*

`A`, and by source and target functions

_{G}`s`:

_{G}`A`→

_{G}`N`and

_{G}`t`:

_{G}`A`→

_{G}`N`that specify the

_{G}*source*and the

*target*of each arc. The subscripts will be dropped when no confusion can arise. In the finite case, we usually write

`n`for the number of nodes and

`m`for the number of arcs.

A *graph (homo)morphism* φ:`G`→`H` is given by two functions (ambiguously
denoted by the same symbol)
φ:`N _{G}`→

`N`and φ:

_{H}`A`→

_{G}`A`which commute with source and target: that is,

_{H}`t`∘φ=φ∘

_{H}`t`and

_{G}`s`∘φ=φ∘

_{H}`s`.

_{G}## Fibrations

Each graph `G` generates freely a category `G`* that has the nodes of `G` as objects,
and the paths of `G` as arrows (composition is concatenation, and the empty paths pointed at each node are the identities).
Given a graph morphism φ:`G`→`B`,
the free category functor gives a functor φ*:`G`*→`B`*. We say that φ
is a graph fibration when φ* is a fibration (see, e.g., Francis Borceux, “Handbook of Categorical Algebra 2”,
volume 51 of the *Encyclopedia of Mathematics and Its Applications*, Cambridge University Press, 1994). The
definition of categorical fibration is credited to Grothendieck (“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”,
*Seminaire Bourbaki*, 190, 1959‒1960).

An elementary definition of fibration can be easily derived:
φ:`G`→`B` is a fibration iff for every arc `a` of `B`
and every node `x` of `G` such that φ(`x`)=`t`(`a`) there
exist a unique arc `a`^{x} of `G` satisfying
φ(`a`^{x})=`a` and `t`(`a`^{x})=`x`.
The graph `G` is the *total graph* of the fibration, and `B` is its *base*.
The set of nodes of `G` mapped to a node `x` of `B` is called the *fibre* over
`x`.

The property defining fibrations is called the *lifting* property: each arc of `B` can be uniquely lifted along
the fibre of its target. The figure on the left shows two
graphs and a morphism specified implicitly by the colours on the nodes. The morphism is not a fibration
because the loop on the grey node lacks a lifting, and the other arc has too many. The figure
on the right shows a fibration, instead.

Note that by repeating the lifting for all arcs coming into a node `x` of `B`,
we obtain a local in-isomorphism—a bijection between the in-neighbourhood of `x` and that of
every `y` in the fibre of `x`.

Dually, an *opfibration* has the property that each arc of `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 in “Fibrations of
Graphs” (*Discrete Math.*, 243:21‒66, 2002), but the elementary definition appears several times in previous
literature with different names. Grothendieck's definition is however 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).

Two important concepts about fibrations are the *universal total graph at x*—the unique largest in-tree
fibred over

`G`whose root is mapped to

`x`—and the

*minimum base*—the smallest graph over which

`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

`G`. The minimum fibration base is

*fibration prime*, that is, it cannot be fibred nontrivially and epimorphically.

In fact, 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).

We note that 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 φ*:`G`*→`B`* has
bounded fibres (in dynamicspeak, it must be *uniformly finite-to-one*) the
characteristic polynomial of `B` divides that of `G` and the maximum eigenvalue is the same
(“Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs”,
*Discrete Math.*, 39(2):171-197, 1982).

## Connections with topological graph theory

A graph morphism that is both a fibration and an opfibration is a *covering*. In this case, the whole
neighbourhood of `x` and that of every `y` in the fibre of `x` 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
β∘`t`=s (which implies β∘`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.

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 “Fibrations of Graphs”.

## Divisors and spectrum

The community working on spectra of graphs (e.g., to 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 `D` is a front divisor of `G`
if it is possible to build a map `f`:`N _{G}`→

`N`so that the number of links going from a node a node

_{B}`x`of

`G`to all nodes in

`f`(

^{‒1}`z`) is equal to the number of links going from

`f`(

`x`) to

`z`. The

*raison d'être*of divisors is that if

`D`is a divisor of

`G`the characteristic polynomial of

`D`divides that of

`G`.

It is immediate that the existence
of an opfibration from `G` to `D` exhibits `D` as a front divisor of `G` (the same
hold 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 extends immediately
to (op)fibrations (for instance, every group acting on a graph
induces a fibration and an opfibration). See the encyclopedic
book “Spectra of Graphs”, by Dragoš M. Cvetković, Michael Doob and Horst Sachs (Academic Press, 1980),
and its extended bibliography.

Note that lacking a direct definition of (op)fibration, the
connection with graph morphism was observed in a different way by Horst
Sachs in his paper “Simultane Überlangerung gegebener Graphen”
(*Magyar Tud. Akad. Mat. Kutató Int. Közl.*, 9:415‒427,
1965): if `G` covers `B` (in the classical undirected sense) then the characteristic polynomial
of `B` divides that of `G`.

Actually, even more is true: given a fibration φ:`G`→`B` and a vector ` x`
indexed by

`B`, define the

*(right) lifting*of

`along φ, denoted`

**x**

**x**^{φ}, by (

**x**^{φ})

_{i}=

`x`

_{φ(i)}(essentially, we copy the components of

`along each fibre). If`

**x**`is an eigenvector of`

**x**`B`, then

**x**^{φ}is an eigenvector of

`G`for the same eigenvalue.

Symmetrically, if ` x` is a vector indexed by

`G`define the

*(left) lowering*of

`along φ, denoted`

**x**_{φ}

`, by adding up the values of`

**x**`along each fibre. If`

**x**`is an eigenvector of`

**x**`G`and

_{φ}

`is not zero, then`

**x**_{φ}

`is an eigenvector of`

**x**`B`for the same eigenvalue.

These results induce a number of relationships between the eigenvalues and eigenvectors of
two graphs related by a fibrations (dual results exists for opfibrations). Note however that
the abovementioned results by Masakazu Nasu show that divisibility of
characteristic polynomials is provable under weaker conditions, as
if φ is an (op)fibration φ* has bounded fibres, but there are graph morphisms 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 Bruce Kitchens, Brian Marcus, and Paul Trow in
“Eventual factor maps and compositions of closing maps”, *Ergodic Theory Dynam. Systems*, 11(1):85-113, 1991.

## Equitable partitions and graph isomorphism

Starting from the paper by D. G. Corneil and C. C. Gotlieb “An Efficient Algorithm for Graph Isomorphism” (*Journal
of the ACM*, 17:51‒64, 1970), several people studying practical (albeit not polynomial) graph-isomorphism algorithms
have based their effort on the construction of the minimum base of the graph (or on the minimum opfibration base). In particular,
A. Cardon and Maxime Crochemore (“Partitioning a Graph in *O*(|`A`| log_{2} |`V`|)”,
*Theor. Comput. Sci.*, 19:85‒98, 1982) proposed a very efficient computation by exploiting some ideas appeared in
Hopcroft's minimal-automaton algorithm (“An `n` log`n` Algorithm for Minimizing
States in a Finite Automaton”, in *Theory of Machines and Computation*, Academic Press, 1971). They claim
an *O*(`m` log`n`) time bound, albeit the actual bound is
*O*((`m`+`n`) log`n`).

Independently from this computer-science related line of development, mathematicians
studied 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 `C` adjacent to a vertex `x` must depend only on the part of `x`.
The concept has been introduced by Allen J. Schwenk in “Computing the Characteristic Polynomial of a Graph” (*Graphs and
Combinatorics*, volume 406 of *Lecture Notes in Mathematics*, 153‒172. Springer–Verlag, 1974). The fact that equitable
partitions and divisors were actually the same concept, however, went apparently unnoticed for some time.

Brendan McKay used *coarsest* equitable partitions as a starting point for its 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 (*O*(`n`^{2} log`n`)) than that of Cardon and Crochemore
(“Practical Graph Isomorphism”, *Congressus Numerantium*, 30:45‒87, 1981).

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 Paolo Boldi, Violetta Lonati, Massimo Santini and Sebastiano Vigna in
“Graph fibrations, graph isomorphism, and PageRank”
(*RAIRO Inform. Théor.*, 40:227‒253, 2006) and working in time
*O*(`n` log`n` + `m` log(`n`+`m`+`c`) log`n`), where
`c` is the number of colours. The latter algorithm is oriented towards very large graphs and
requires no data structure—just `n`
vectors containing overall `m` integers and six vectors of `n` integers each.

In implicit form, however, equitable partitions appeared in Stephen H. Unger's program for
graph isomorphism (“GIT—A Heuristic Program for Testing Pairs of
Directed Line Graphs for Isomorphism”, *Comm. ACM*, 7(1):26‒34, 1964).

## 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 φ:`G`→`H`
implies that, whatever algorithm is used, there are executions in which the behaviour of the nodes in `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. Analogous strong results were proved for a class of self-stabilising systems.

The usage of graph homomorphisms to prove impossibility results, of course, is not new and started
with Dana Angluin's seminal paper “Local and global properties in networks of processors” (*Proc.
12th Symposium on the Theory of Computing*, pages 82‒93, 1980), 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. 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).

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 iff they are isomorphic
up to level `n`−1
(“Universal covers of graphs: Isomorphism to depth `n`−1 implies isomorphism to all depths”, *Discrete Appl. Math.*, 56:61‒74, 1995),
which was easily extended to universal total graphs by Boldi and Vigna, and the even tighter result
that `n`+`D` levels (where `D` is the diameter)
of any universal total graph of a strongly connected
fibration-prime graph uniquely identify the latter (see again “Fibrations of graphs”).

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.

## Semicovers

Working on the spectra of trees, P. Híc, Roman Nedela and S.
Pavlíková have previously defined in their 1992 paper “Front-Divisors
of Trees” (*Acta Math. Univ. Comenianae*, LXI(1), 1992, pp.
69‒84) the notion of *semicovering projection* (in our
terminology, opfibration), and applied it to the symmetric
representation of undirected trees. In particular, they notice the
relation with divisors and propose a functional voltage representation.
The representation has been reintroduced independently in “Fibrations
of Graphs” and extended to a categorical equivalence between the
category of fibrations over `B` and the category of presheaves
on `B`*. The authors prove also 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).

## 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 “An Introduction to Symbolic Dynamics and Coding”, by Douglas Lind and Brian Marcus (Cambridge University Press, 1995) collects the large amount of knowledge gathered in the field. Some results proved in “Fibrations of Graphs” in a categorical settings appear here, albeit usually with some additional hypothesis. We will try to briefly highlight the main connections.

A *sofic shift* is a shift formed by the biinfinite paths
of an arc-labelled graph (the graphs considered are usually strongly
connected, a.k.a. *irreducible*). 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 of the fact that all states are initial and final,
the minimum deterministic automaton, however, 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—you don't need universal total graphs and all the rest, because the language
recognised starting at a node `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 (“On sofic systems. I”, *Israel J. Math.*, 48(4):305‒330, 1984). Again, these differences
are immaterial in the development of fibration theory, as it uses general graphs
(in fact, not even necessarily finite).

Of course, 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 in the treatise “Topological entropy and equivalence of dynamical systems”
(volume 20 of *Mem. Amer. Math. Soc.*, 1979), define *(right-) left-resolving* maps (Definition 3.31)
between shifts of finite type. 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 hypothesis 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 (“Constant-to-one and onto global maps of homomorphisms between strongly connected graphs”,
*Ergodic Theory Dynam. Systems*, 3(3):387‒413, 1983), 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 in “An Introduction to Symbolic Dynamics and Coding” is identical to that of (op)fibration.

Williams (“Classification of Subshifts of Finite Type”, *Ann. of Math.*, 98:128‒153, 1973)
introduced the notions of subdivision and amalgamation matrices, which can be used as a substitute
of left/right-coverings. Williams introduced also the notions of *state splitting* and
*state merging*, which when applied to a graph `G` roughly correspond to building
a graph fibred over `G` or a graph over which `G` can be fibred, respectively.

## The categorical side

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 `G`* and the category of fibrations into `G`. The equivalence extends to
the case of fibrations the notion of *voltage assignment* (Jonathan L. Gross and Thomas W. Tucker,
“Generating all graph coverings by permutation voltage assignments”, *Discrete Math.*, 18(3):273‒283, 1977).
The representation of a fibration as a presheaf over `G`* gives, for each arc of `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.

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. More results can be found in “Fibrations of Graphs”.