# Graph coverings and twisted operators

David Cimasoni  David Cimasoni – Université de Genève, Suisse
<EMAIL_ADDRESS>and  Adrien Kassel  Adrien Kassel – CNRS, École
Normale Supérieure de Lyon, France<EMAIL_ADDRESS>
###### Abstract.

Given a graph and a representation of its fundamental group, there is a
naturally associated twisted adjacency operator. The main result of this
article is the fact that these operators behave in a controlled way under
graph covering maps. When such an operator can be used to enumerate objects,
or compute a partition function, this has concrete implications on the
corresponding enumeration problem, or statistical mechanics model. For
example, we show that if $\widetilde{\Gamma}$ is a finite connected covering
graph of a graph $\Gamma$ endowed with edge-weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}}$, then the spanning
tree partition function of $\Gamma$ divides the one of $\widetilde{\Gamma}$ in
the ring $\mathbb{Z}[\mathsf{x}]$. Several other consequences are obtained,
some known, others new.

##  1\. Introduction

The aim of this article is to present a result of algebraic graph theory,
probably known to the experts, in a fairly self-contained and elementary
manner. This brings into what we believe to be the correct framework several
well-known results in combinatorics, statistical mechanics, and $L$-function
theory, but also provides new ones. In order to preserve its non-technical
nature, we focus in the present article on relatively direct consequences,
leaving the more elaborate implications to subsequent papers [9, 10].

We now explain our main result in an informal way, referring to Section 2 for
precise definitions and background, to Theorem 3.6 for the complete formal
statement, and to Section 3.2 for its proof. Given a locally finite weighted
graph $\Gamma$ and a representation $\rho$ of its fundamental group, one can
define a twisted adjacency operator $\mathsf{A}_{\Gamma}^{\rho}$. Consider a
covering map $\widetilde{\Gamma}\to\Gamma$ of finite degree between two
connected locally finite graphs. Via this map, the fundamental group
$\pi_{1}(\widetilde{\Gamma})$ embeds into $\pi_{1}(\Gamma)$. As a consequence,
any representation $\rho$ of $\pi_{1}(\widetilde{\Gamma})$ defines an induced
representation $\rho^{\\#}$ of $\pi_{1}(\Gamma)$. Our main result is the fact
that the operator $\mathsf{A}^{\rho}_{\widetilde{\Gamma}}$ is conjugate to
$\mathsf{A}_{\Gamma}^{\rho^{\\#}}$.

Let us mention that the existence of an isomorphism between the relevant
vector spaces can be understood as a chain-complex version of the so-called
Eckmann-Shapiro lemma, originally stated in group cohomology (see Remark 3.7).
The interesting part of Theorem 3.6, which we have not been able to find in
the literature, is the fact that the explicited isomorphism conjugates the
aptly defined twisted adjacency operators.

As an immediate consequence of this result, we see that the decomposition of
$\rho^{\\#}$ into irreducible representations leads to a direct sum
decomposition of $\mathsf{A}_{\Gamma}^{\rho^{\\#}}$, and therefore of
$\mathsf{A}^{\rho}_{\widetilde{\Gamma}}$. For example, if $\rho$ is taken to
be the trivial representation, we readily obtain the fact that
$\mathsf{A}_{\Gamma}$ is a direct summand of
$\mathsf{A}_{\widetilde{\Gamma}}$, see Corollary 3.8. (Here, the absence of
superscript means that these operators are not twisted, or twisted by the
trivial representation.) Furthermore, if the covering is normal, then
$\mathsf{A}_{\widetilde{\Gamma}}$ factors as a direct sum of the operators
$\mathsf{A}_{\Gamma}^{\rho}$ twisted by the irreducible representations of the
Galois group of the covering, see Corollary 3.9.

Whenever $\mathsf{A}^{\rho}_{\Gamma}$ can be used to enumerate combinatorial
objects in $\Gamma$, or in an associated graph $\mathsf{G}$, these statements
have very concrete combinatorial implications. More generally, if these
operators can be used to compute some partition functions of the weighted
graph $(\Gamma,\mathsf{x})$, or of an associated weighted graph
$(\mathsf{G},\mathsf{x})$, these results have often non-trivial consequences
on the corresponding models. Several of these implications are well-known, but
others are new. We now state some of them, referring to Section 4 for details.

There is an obvious place to start, namely the matrix-tree theorem: the
Laplacian $\Delta_{\mathsf{G}}$ allows to enumerate spanning trees (STs) and
rooted spanning forests (RSFs) in $\mathsf{G}$. More generally, if
$\mathsf{G}=(\mathsf{V},\mathsf{E})$ is endowed with edge-weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}\in\mathsf{E}}$, then it
allows to compute the corresponding partition functions
$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})$ and
$\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},\mathsf{x})$, which can be thought of as
elements of the polynomial ring
$\mathbb{Z}[\mathsf{x}]=\mathbb{Z}[\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}\in\mathsf{E}}]$.
Applying Corollary 3.8 to the Laplacian
$\mathsf{A}_{\Gamma}=\Delta_{\mathsf{G}}$, we obtain the following result: if
$\widetilde{\mathsf{G}}$ is a finite covering graph of a finite connected
graph $\mathsf{G}$ endowed with edge-weights $\mathsf{x}$, and if
$\tilde{\mathsf{x}}$ denotes these weights lifted to the edges of
$\widetilde{\mathsf{G}}$, then
$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})$ divides
$\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ and
$\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},\mathsf{x})$ divides
$\mathsf{Z}_{\mathit{RSF}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ in the
ring $\mathbb{Z}[\mathsf{x}]$. As an immediate consequence, the number of
spanning trees in $\mathsf{G}$ divides the number of spanning trees in
$\widetilde{\mathsf{G}}$ (a fact first proved by Berman [4] using a different
method), and similarly for rooted spanning forests (to the best of our
knowledge, a new result).

Another interesting class of operators is given by the weighted skew-adjacency
matrices defined by Kasteleyn [20, 21] in his study of the dimer model on
surface graphs. For this model, Corollary 3.8 can only be applied to cyclic
coverings, yielding a known result [15, 25]. Applying Corollary 3.9 to the
case of a graph embedded in the torus yields an immediate proof of the
classical fact that the dimer characteristic polynomial behaves
multiplicatively under so-called enlargement of the fundamental domain [24,
Theorem 3.3]. However, applying our results to the study of the dimer model on
graphs embedded in the Klein bottle leads to new powerful results, that are
harnessed in the parallel article [9].

Let us finally mention that our main result can be interpreted as the fact
that the operators $\mathsf{A}_{\Gamma}^{\rho}$ satisfy the so-called Artin
formalism, a set of axioms originating from the study of $L$-series of Galois
field extensions [2, 3]. As a consequence, we obtain several results on the
associated $L$-series
$L(\Gamma,\mathsf{x},\rho)=\det(\operatorname{I}-\mathsf{A}_{\Gamma}^{\rho})^{-1}$,
providing a wide generalization of the results of Stark and Terras [33, 34],
see Section 3.3.

We conclude this introduction with one final remark. There are two ways to
consider graphs: either as combinatorial objects, or as topological ones
(namely $1$-dimensional CW-complexes). Hence, there are two corresponding ways
to define and study the associated fundamental groups and covering maps. In
our pursuit of simplicity, we have chosen the combinatorial one. As a result,
we provide the reader with a brief and dry but self-contained treatment of the
required parts of algebraic topology translated from the topological to the
combinatorial category, see Sections 2.1–2.3.

This paper is organised as follows. Section 2 deals with the necessary
background material and claims no originality: we start from scratch with
graphs, their fundamental groups and covering maps, before moving on to
connections on graphs, and basics of representation theory of groups. Section
3 contains the definition of the twisted operators, our main result with its
proof and corollaries, together with the analogy with algebraic number theory
via the Artin formalism. Finally, Section 4 deals with the aforementioned
combinatorial applications.

### Acknowledgements

D.C. thanks Pierre de la Harpe and Anders Karlsson for useful conversations,
and the Swiss National Science Foundation for partial support. A.K.
acknowledges the hospitality of the Université de Genève and the partial
support of the ANR project DIMERS, grant number ANR-18-CE40-0033.

##  2\. Background on graphs and representations

In this section, we first recall the combinatorial definitions of the
fundamental group of a graph and of graph coverings, adapting the standard
references [32] and [14] to our purposes, see also [26]. We then proceed with
connections on graph vector bundles following [22], and linear representations
of groups following [31].

###  2.1. Graphs and their fundamental groups

This first paragraph deals with the elementary concepts of graph and directed
graph. Since there is no universal agreement on the relevant terminology and
notation, we record here these formal definitions following [32].

######  Definition 2.1.

A directed graph (or digraph) $\Gamma$ consists of a set $\mathsf{V}$ of
vertices, a set $\mathsf{D}$ of (directed) edges, together with maps
$s,t\colon\mathsf{D}\to\mathsf{V}$ assigning to each edge $e\in\mathsf{D}$ its
source vertex $s(e)\in\mathsf{V}$ and its target vertex $t(e)\in\mathsf{V}$.

A graph $\Gamma$ consists of sets $\mathsf{V},\mathsf{D}$ and maps
$s,t\colon\mathsf{D}\to\mathsf{V}$ as above, together with an involution of
$\mathsf{D}$ assigning to each edge $e\in\mathsf{D}$ its inverse
$\overline{e}\in\mathsf{D}$ such that $\overline{e}\neq e$ and
$s(\overline{e})=t(e)$. We let $\mathsf{E}=\mathsf{D}/(e\sim\overline{e})$
denote the set of unoriented edges, and write $\mathsf{e}\in\mathsf{E}$ for
the unoriented edge corresponding to $e,\overline{e}\in\mathsf{D}$.

A (directed) graph is locally finite if for all $v\in\mathsf{V}$, the sets
$\mathsf{D}_{v}=\\{e\in\mathsf{D}\,|\,s(e)=v\\}$ and
$\mathsf{D}^{v}=\\{e\in\mathsf{D}\,|\,t(e)=v\\}$ are finite. It is called
finite if both sets $\mathsf{V}$ and $\mathsf{D}$ are finite.

Note that these graphs are not simple in general: we allow multiple edges and
loops. Note also that in this formalism, graphs are special types of directed
graphs. Moreover, given a directed graph $\Gamma$, one can build an associated
graph (still denoted by $\Gamma$) by formally adding an inverse $\overline{e}$
to each edge $e\in\mathsf{D}$.

Let us fix a directed graph $\Gamma$. A path of length $n\geq 1$ is a sequence
$\gamma=(e_{1},e_{2},\ldots,e_{n})$ of edges such that $t(e_{i})=s(e_{i+1})$
for all $i\in\\{1,\ldots,n-1\\}$. We shall write $s(\gamma)=s(e_{1})$ and
$t(\gamma)=t(e_{n})$ for the source and target of $\gamma$, respectively. A
path of length $0$, or constant path $\gamma$, is given by a vertex, which is
both the source and target of $\gamma$. A loop (based at $v$) is a path
$\gamma$ with $s(\gamma)=t(\gamma)=v$.

The directed graph $\Gamma$ is said to be connected if for any
$v,w\in\mathsf{V}$, there is a path $\gamma$ with $s(\gamma)=v$ and
$t(\gamma)=w$.

###  2.2. The fundamental group of a graph

Let us now assume that $\Gamma$ is a graph, and fix a vertex $v\in\mathsf{V}$.

Note that the set of loops based at $v$ is a monoid with respect to the
concatenation of paths, with neutral element $1$ given by the constant path
based at $v$. Let us call two loops based at $v$ (or more generally, two paths
with same source and same target) homotopic if one can be obtained from the
other by removing or adding loops of the form $(e,\overline{e})$ along the
path. Then, the set of homotopy classes of loops based at $v$ forms a group,
with the inverse of $\gamma=(e_{1},\dots,e_{n})$ given by
$\overline{\gamma}=(\overline{e}_{n},\dots,\overline{e}_{1})$.

######  Definition 2.2.

This group is the fundamental group of the graph $\Gamma$ based at $v$, and is
denoted by $\pi_{1}(\Gamma,v)$.

If $\Gamma$ is connected, then the isomorphism class of $\pi_{1}(\Gamma,v)$ is
easily seen not to depend on the base vertex $v$.

By a slight abuse of terminology, we define the fundamental group of a
directed graph $\Gamma$ as the fundamental group of the associated graph
obtained by adding an inverse to each edge of $\Gamma$.

We will make use of the alternative definition of the fundamental group, based
on a spanning tree. Recall that a circuit (of length $n\geq 1$) is a loop
$\gamma=(e_{1},\dots,e_{n})$ such that $e_{i+1}\neq\overline{e}_{i}$ for
$i\in\\{1,\dots,n-1\\}$, $e_{1}\neq\overline{e}_{n}$, and such that the
vertices $t(e_{1}),\dots,t(e_{n})$ are all distinct. A spanning tree of
$\Gamma$ is a connected non-empty subgraph $T\subset\Gamma$ without circuit,
such that the vertices of $T$ coincide with the vertices of $\Gamma$. Note
that the number of vertices and edges in a finite tree satisfy
$|\mathsf{V}(T)|-|\mathsf{E}(T)|=1$.

The fundamental group of the graph $\Gamma$ based at $T$, denoted by
$\pi_{1}(\Gamma,T)$, is defined as the quotient of the free group over
$\mathsf{D}$ by the relations $\overline{e}=e^{-1}$ for all edges of $\Gamma$,
and $e=1$ for all edges of $T$. If $\Gamma$ is connected, then it admits a
spanning tree, and the groups $\pi_{1}(\Gamma,v)$ and $\pi_{1}(\Gamma,T)$ are
easily seen to be isomorphic for all $v\in\mathsf{V}$ and all spanning trees
$T$ of $\Gamma$. As a consequence, if $\Gamma$ is connected and finite, its
fundamental group is free of rank $|\mathsf{E}|-|\mathsf{V}|+1$.

###  2.3. Covering graphs

A morphism of digraphs $p$ from
$\widetilde{\Gamma}=(\widetilde{\mathsf{V}},\widetilde{\mathsf{D}},\tilde{s},\tilde{t})$
to $\Gamma=(\mathsf{V},\mathsf{D},s,t)$ consists of two maps
$p_{0}:\widetilde{\mathsf{V}}\to\mathsf{V}$ and
$p_{1}:\widetilde{\mathsf{D}}\to\mathsf{D}$ such that $s\circ
p_{1}=p_{0}\circ\tilde{s}$ and $t\circ p_{1}=p_{0}\circ\tilde{t}$. A morphism
of graphs $p\colon\widetilde{\Gamma}\to\Gamma$ is a morphism of digraphs which
also satisfies the equality $p_{1}(\overline{e})=\overline{p_{1}(e)}$ for all
$e\in\widetilde{\mathsf{D}}$.

As one easily checks, a morphism of graphs
$p\colon\widetilde{\Gamma}\to\Gamma$ induces in the obvious way a homomorphism
of groups $p_{*}\colon\pi_{1}(\widetilde{\Gamma},v)\to\pi_{1}(\Gamma,p(v))$ .

######  Definition 2.3.

A covering map is a morphism of directed graphs
$p\colon\widetilde{\Gamma}\to\Gamma$ with
$p_{0}\colon\widetilde{\mathsf{V}}\to\mathsf{V}$ surjective, such that for all
$\tilde{v}\in\widetilde{\mathsf{V}}$, the restriction of $p_{1}$ defines
bijections $\widetilde{\mathsf{D}}_{\tilde{v}}\to\mathsf{D}_{p(\tilde{v})}$
and $\widetilde{\mathsf{D}}^{\tilde{v}}\to\mathsf{D}^{p(\tilde{v})}$. In that
case, $\widetilde{\Gamma}$ is called a covering digraph of $\Gamma$.

If $\Gamma$ is a connected digraph, then the fibers $p_{0}^{-1}(v)$ and
$p_{1}^{-1}(e)$ have the same cardinality for all $v\in\mathsf{V}$ and
$e\in\mathsf{D}$. This is called the degree of the covering. From now on, we
will drop the subscripts in $p_{0}$ and $p_{1}$ and denote both maps by $p$.

Note that any morphism of digraphs $p\colon\widetilde{\Gamma}\to\Gamma$
extends to a unique morphism between the associated graphs (obtained by adding
an inverse to each edge). Moreover, if the morphism of digraphs is a covering
map, then so is the associated morphism of graphs. In such a case, the graph
$\widetilde{\Gamma}$ is called a covering graph of $\Gamma$.

The easy proof of the following lemma is left to the reader.

######  Lemma 2.4.

If $p\colon\widetilde{\Gamma}\to\Gamma$ is a covering map, then:

  1. (i)

the homomorphism
$p_{*}\colon\pi_{1}(\widetilde{\Gamma},v)\to\pi_{1}(\Gamma,p(v))$ is
injective;

  2. (ii)

for any $v\in\mathsf{V}$, the following subsets of $\widetilde{\mathsf{V}}$
coincide:

$\\{t(\tilde{e})\in\widetilde{\mathsf{V}}\,|\,\tilde{e}\in\widetilde{\mathsf{D}}_{\tilde{v}}\text{
with }{\tilde{v}}\in
p^{-1}(v)\\}=\\{\tilde{w}\in\widetilde{\mathsf{V}}\,|\,\text{there
exists~{}$e\in\mathsf{D}_{v}$ with~{}$t(e)=p(\tilde{w})$}\\}\,.$

The following path lifting property is a direct consequence of the
definitions, but nevertheless a fundamental feature of a covering map
$p\colon\widetilde{\Gamma}\to\Gamma$. Given any path $\gamma$ in $\Gamma$ with
$s(\gamma)=v_{0}$ and any $\tilde{v}_{0}\in p^{-1}(v_{0})$, there is a unique
path $\tilde{\gamma}$ in $\widetilde{\Gamma}$ with $p(\tilde{\gamma})=\gamma$
and $s(\tilde{\gamma})=\tilde{v}_{0}$. Furthermore, the formula
$[\gamma]\cdot\tilde{v}_{0}=t(\tilde{\gamma})$ defines an action of
$\pi_{1}(\Gamma,v_{0})$ on $p^{-1}(v_{0})$. If $\widetilde{\Gamma}$ is
connected, then this action is easily seen to be transitive, with isotropy
group of $\tilde{v}_{0}$ equal to
$p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))$. As a consequence, the
degree of the covering coincides with the index of
$p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))$ in $\pi_{1}(\Gamma,v_{0})$.

Let us finally recall that a covering map $p\colon\widetilde{\Gamma}\to\Gamma$
is said to be normal (or regular) if $p_{*}(\pi_{1}(\widetilde{\Gamma},v))$ is
a normal subgroup of $\pi_{1}(\Gamma,p(v))$. In such a case, we denote the
quotient group by $G(\widetilde{\Gamma}/\Gamma)$. This is nothing but the
group of covering transformations of this covering map, usually referred to as
the Galois group.

###  2.4. Connections on graphs

Following [22, Section 3.1], let us fix a vector bundle on a graph $\Gamma$,
i.e. a vector space $W$ and the choice of a vector space $W_{v}$ isomorphic to
$W$ for each $v\in\mathsf{V}$. Such a vector bundle can be identified with
$W_{\Gamma}:=\bigoplus_{v\in\mathsf{V}}W_{v}\simeq W^{\mathsf{V}}$.

######  Definition 2.5.

A connection on a vector bundle $W_{\Gamma}$ is the choice
$\Phi=(\varphi_{e})_{e\in\mathsf{D}}$ of an isomorphism $\varphi_{e}\colon
W_{t(e)}\to W_{s(e)}$ for each $e\in\mathsf{D}$, such that
$\varphi_{\overline{e}}=\varphi_{e}^{-1}$ for all $e\in\mathsf{D}$.

Two connections $\Phi=(\varphi_{e})_{e\in\mathsf{D}}$ and
$\Phi^{\prime}=(\varphi^{\prime}_{e})_{e\in\mathsf{D}}$ are said to be gauge-
equivalent if there is a family of automorphisms $\\{\psi_{v}\colon W_{v}\to
W_{v}\\}_{v\in\mathsf{V}}$ such that
$\psi_{s(e)}\circ\varphi_{e}=\varphi^{\prime}_{e}\circ\psi_{t(e)}$ for all
$e\in\mathsf{D}$.

Let us fix a base vertex $v_{0}\in\mathsf{V}$ and a connection $\Phi$ on a
vector bundle $W_{\Gamma}$. Any loop $\gamma=(e_{1},\dots,e_{n})$ based at
$v_{0}$ gives an automorphism $\varphi_{e_{1}}\circ\dots\circ\varphi_{e_{n}}$
of $W_{v_{0}}=:W$ called the monodromy of $\gamma$. This construction defines
a homomorphism

$\rho^{\Phi}\colon\pi_{1}(\Gamma,v_{0})\longrightarrow\operatorname{GL}(W)\,,$

i.e. a representation of the fundamental group of $\Gamma$ in $W$.

Any representation $\rho\colon\pi_{1}(\Gamma,v_{0})\to\operatorname{GL}(W)$ is
of the form $\rho^{\Phi}$ for some connection $\Phi$: indeed, one can fix a
spanning tree $T\subset\Gamma$ (recall that
$\pi_{1}(\Gamma,v_{0})\simeq\pi_{1}(\Gamma,T)$), set
$\varphi_{e}=\operatorname{id}_{W}$ for each edge of $T$ and
$\varphi_{e}=\rho_{e}$ for each of the remaining edges of $\Gamma$.
Furthermore, given two connections $\Phi$ and $\Phi^{\prime}$ on $W_{\Gamma}$,
one easily checks that $\rho^{\Phi}$ and $\rho^{\Phi^{\prime}}$ are conjugate
representations if and only if $\Phi$ and $\Phi^{\prime}$ are gauge-equivalent
connections.

In other words, the $\operatorname{GL}(W)$-character variety of
$\pi_{1}(\Gamma,v_{0})$, i.e. the set of conjugation classes of homomorphisms
$\pi_{1}(\Gamma,v_{0})\to\operatorname{GL}(W)$, is given by the set of
connections on $W_{\Gamma}$ up to gauge-equivalence.

######  Remark 2.6.

The definition of a connection as isomorphisms $\varphi_{e}\colon W_{s(e)}\to
W_{t(e)}$ seems more natural, but leads to antihomomorphisms of
$\pi_{1}(\Gamma,v_{0})$. On the other hand, our convention yields
homomorphisms, and is coherent with the definition of a local coefficient
system for twisted homology, see e.g. [36, p. 255].

###  2.5. Linear representations of groups

We now recall the necessary notation and terminology of linear representations
of groups, following [31]. Throughout this subsection, $G$ denotes a group.

Let us first recall that the degree of a representation $\rho\colon
G\to\operatorname{GL}(W)$, denoted by $\deg(\rho)$, is defined as the
dimension of $W$, which we always assume to be finite. The only representation
of degree $0$ is written $\rho=0$, while the degree $1$ representation sending
all elements of $G$ to $1\in\mathbb{C}^{*}=\operatorname{GL}(\mathbb{C})$ is
denoted by $\rho=1$.

Let us now fix two linear representations $\rho\colon
G\to\operatorname{GL}(W)$ and $\rho^{\prime}\colon
G\to\operatorname{GL}(W^{\prime})$. The direct sum of $\rho$ and
$\rho^{\prime}$ is the representation $\rho\oplus\rho^{\prime}\colon
G\to\operatorname{GL}(W\oplus W^{\prime})$ given by
$(\rho\oplus\rho^{\prime})_{g}=\rho_{g}\oplus\rho_{g^{\prime}}$. A
representation of $G$ is said to be irreducible if it is not the direct sum of
two representations that are both not $0$.

Now, fix a subgroup $H<G$ of finite index, and a representation $\rho\colon
H\to\operatorname{GL}(W)$. There is a representation $\rho^{\\#}\colon
G\to\operatorname{GL}(Z)$ which is uniquely determined up to isomorphism by
the following two properties. Let $R\subset G$ denote a set of representatives
of $G/H$, i.e. each $g\in G$ can be written uniquely as $g=rh\in G$ with $r\in
R$ and $h\in H$.

  1. (i)

We have $Z=\bigoplus_{r\in R}\rho_{r}^{\\#}(W)$.

  2. (ii)

For any $g\in G$ and $w\in W$, we have
$\rho_{g}^{\\#}(\rho_{r}^{\\#}(w))=\rho_{r^{\prime}}^{\\#}(\rho_{h}(w))$ where
$gr=r^{\prime}h\in G$ with $r^{\prime}\in R$ and $h\in H$.

This representation $\rho^{\\#}\colon G\to\operatorname{GL}(Z)$ is said to be
induced by $\rho\colon H\to\operatorname{GL}(W)$.

##  3\. Twisted operators on graph coverings

This section contains the proof of our main result, Theorem 3.6, which relates
twisted adjacency operators on directed graphs connected by a covering map. We
start in Section 3.1 by defining the relevant twisted operators, while Section
3.2 deals with Theorem 3.6, its proof, and a couple of corollaries. Finally,
Section 3.3 shows how this result can be interpreted as a combinatorial
version of the Artin formalism for these operators, yielding consequences on
associated $L$-series.

###  3.1. Twisted weighted adjacency operators

Fix a locally finite directed graph $\Gamma=(\mathsf{V},\mathsf{D},s,t)$. Let
us assume that it is endowed with edge-weights, i.e. a collection
$x=\\{x_{e}\\}_{e\in\mathsf{D}}$ of complex numbers attached to the edges. The
associated weighted adjacency operator $\mathsf{A}_{\Gamma}$ acts on
$\mathbb{C}^{\mathsf{V}}$ via

$(\mathsf{A}_{\Gamma}f)(v)=\sum_{e\in\mathsf{D}_{v}}x_{e}\,f(t(e))\quad\text{for
all~{}$f\in W^{\mathsf{V}}$ and~{}$v\in\mathsf{V}$}\,.$

Adapting [22, Section 3.2] to our purposes, this operator can be twisted by a
representation $\rho\colon\pi_{1}(\Gamma,v_{0})\to\operatorname{GL}(W)$ in the
following way. Fix a vector bundle $W_{\Gamma}\simeq W^{\mathsf{V}}$ and a
connection $\Phi=(\varphi_{e})_{e\in\mathsf{D}}$ representing $\rho$.

######  Definition 3.1.

The associated twisted weighted adjacency operator
$\mathsf{A}_{\Gamma}^{\rho}$ is the operator on $W^{\mathsf{V}}$ given by

$(\mathsf{A}^{\rho}_{\Gamma}f)(v)=\sum_{e\in\mathsf{D}_{v}}x_{e}\,\varphi_{e}(f(t(e)))\quad\text{for
all~{}$f\in W^{\mathsf{V}}$ and~{}$v\in\mathsf{V}$}\,.$

Several remarks are in order.

######  Remark 3.2.

  1. (i)

By Section 2.4, conjugate representations are given by gauge equivalent
connections. Furthermore, the corresponding twisted operators are conjugated
by an automorphism of $W^{\mathsf{V}}$. Therefore, the conjugacy class of
$\mathsf{A}_{\Gamma}^{\rho}$ only depends on the conjugacy class of $\rho$.

  2. (ii)

If a representation $\rho$ is given by the direct sum of $\rho_{1}$ and
$\rho_{2}$, then the operator $\mathsf{A}_{\Gamma}^{\rho}$ is conjugate to
$\mathsf{A}_{\Gamma}^{\rho_{1}}\oplus\mathsf{A}_{\Gamma}^{\rho_{2}}$.

  3. (iii)

The operator $\mathsf{A}^{1}_{\Gamma}$ is nothing but the untwisted operator
$\mathsf{A}_{\Gamma}$.

Obviously, the untwisted operator $\mathsf{A}_{\Gamma}$ is uniquely associated
to a directed graph $\Gamma$, so our setting may seem quite restrictive.
Nevertheless, there are many natural assignments $\mathsf{G}\mapsto\Gamma$
mapping a directed graph $\mathsf{G}$ to another directed graph $\Gamma$ so
that $\mathsf{A}_{\Gamma}$ provides a new operator on $\mathsf{G}$. Moreover,
if there is a natural homomorphism
$\alpha\colon\pi_{1}(\Gamma)\to\pi_{1}(\mathsf{G})$, then a $\rho$-twisted
version of this new operator can be understood as
$\mathsf{A}_{\Gamma}^{\alpha\circ\rho}$. Finally, if the assignment
$\mathsf{G}\mapsto\Gamma$ preserves covering maps, then our results apply to
these new twisted operators as well.

We now give three explicit examples of such natural maps
$\mathsf{G}\mapsto\Gamma$, claiming no exhaustivity. It is easy indeed to find
additional interesting ones, e.g. the Fisher correspondance used in the study
of the Ising model [12].

######  Example 3.3.

Let $\mathsf{G}=(\mathsf{V}(\mathsf{G}),\mathsf{E}(\mathsf{G}))$ be a graph
endowed with symmetric edge-weights, i.e. labels
$\mathsf{x}=(\mathsf{x}_{\mathsf{e}})_{\mathsf{e}\in\mathsf{E}(\mathsf{G})}$
associated to its unoriented edges. Consider the associated graph
$\Gamma=(\mathsf{V},\mathsf{E})$ defined by
$\mathsf{V}=\mathsf{V}(\mathsf{G})$ and
$\mathsf{E}=\mathsf{E}(\mathsf{G})\cup\mathsf{V}(\mathsf{G})$, with source,
target, and involution maps of $\Gamma$ given by extending the ones of
$\mathsf{G}$ via $\overline{v}=v$ and $s(v)=t(v)=v$ for all $v\in\mathsf{V}$.
(Concretely, the graph $\Gamma$ is obtained from $\mathsf{G}$ by adding a loop
at each vertex.) Also, extend the edge-weights on $\mathsf{G}$ to symmetric
edge-weights on $\Gamma$ via
$\mathsf{x}_{v}=-\sum_{e\in\mathsf{D}(\mathsf{G})_{v}}\mathsf{x}_{e}$. Then,
the corresponding weighted adjacency operator $\mathsf{A}_{\Gamma}$ is (the
opposite of) the Laplacian $\Delta_{\mathsf{G}}$ on $\mathsf{G}$. It can be
used to count spanning trees of $\mathsf{G}$ – this is the celebrated matrix-
tree theorem – but also rooted spanning forests, see Section 4.1.

Note that there is a natural homomorphism
$\alpha\colon\pi_{1}(\Gamma,v_{0})\to\pi_{1}(\mathsf{G},v_{0})$ mapping all
the newly introduced loops to the neutral element. Given any representation
$\rho$ of $\pi_{1}(\mathsf{G},v_{0})$, the associated twisted operator
$\mathsf{A}^{\alpha\circ\rho}_{\Gamma}$ is the vector bundle Laplacian
$\Delta^{\rho}_{\mathsf{G}}$ of [22]. When the representation $\rho$ takes
values in $\mathbb{C}^{*}$ or $\operatorname{SL}_{2}(\mathbb{C})$, then
$\Delta^{\rho}_{\mathsf{G}}$ can be used to study cycle-rooted spanning
forests [13, 22], while representations of higher degree yield more involved
combinatorial objects [19].

######  Example 3.4.

Let $\Gamma$ be a graph endowed with symmetric edge-weights
$\mathsf{x}=(\mathsf{x}_{\mathsf{e}})_{\mathsf{e}\in\mathsf{E}}$. Fix an
orientation of the edges of $\Gamma$ and consider the same graph $\Gamma$
endowed with the anti-symmetric edge-weights $x=\\{x_{e}\\}_{e\in\mathsf{D}}$
given by $x_{e}=\mathsf{x}_{\mathsf{e}}$ if the orientation of
$e\in\mathsf{D}$ agrees with the fixed orientation, and
$x_{e}=-\mathsf{x}_{\mathsf{e}}$ else. Then, the operator
$\mathsf{A}_{\Gamma}$ is a weighted skew-adjacency operator that has been used
by Kasteleyn [20, 21] and many others in the study of the 2-dimensional dimer
and Ising models, see Section 4.2. Such operators twisted by
$\operatorname{SL}_{2}(\mathbb{C})$-representations are also considered by
Kenyon in his study of the double-dimer model [23].

######  Example 3.5.

Let us start with a graph
$\mathsf{G}=(\mathsf{V}(\mathsf{G}),\mathsf{D}(\mathsf{G}),s_{\mathsf{G}},t_{\mathsf{G}},i)$
endowed with symmetric edge-weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}}$, and consider the
associated directed line graph $\Gamma=(\mathsf{V},\mathsf{D},s,t)$ defined by

$\mathsf{V}=\mathsf{D}(\mathsf{G}),\quad\mathsf{D}=\\{(e,e^{\prime})\in\mathsf{V}\times\mathsf{V}\,|\,t_{\mathsf{G}}(e)=s_{\mathsf{G}}(e^{\prime})\text{
but }e^{\prime}\neq\overline{e}\\},\quad s(e,e^{\prime})=e,\quad
t(e,e^{\prime})=e^{\prime},$

and endowed with the edge-weights
$x=\\{x_{e,e^{\prime}}\\}_{(e,e^{\prime})\in\mathsf{D}}$ defined by
$x_{e,e^{\prime}}=\mathsf{x}_{\mathsf{e}}$. Then, the operator
$\operatorname{I}-\mathsf{A}_{\Gamma}$ is considered by Stark and Terras [33,
34] in their study of prime cycles (see Section 3.3), while a similar operator
is defined by Kac and Ward [17] in their exploration of the planar Ising model
(see Section 4.2). Note also that there is a natural homomomorphism
$\alpha\colon\pi_{1}(\Gamma,e_{0})\to\pi_{1}(\mathsf{G},s(e_{0}))$, so any
representation $\rho\colon\pi_{1}(\mathsf{G},v_{0})\to\operatorname{GL}(W)$
defines a twisted operator
$\operatorname{I}-\mathsf{A}^{\rho\circ\alpha}_{\Gamma}$.

###  3.2. The main result

We are finally ready to state and prove our main theorem.

Let $\Gamma=(\mathsf{V},\mathsf{D},s,t)$ be a locally finite connected
directed graph with weights $x=(x_{e})_{e\in\mathsf{D}}$, and let
$p\colon\widetilde{\Gamma}\to\Gamma$ be a covering map of finite degree $d$,
with $\widetilde{\Gamma}=(\widetilde{\mathsf{V}},\widetilde{\mathsf{D}},s,t)$
connected. The weights $x$ on $\Gamma$ lift to weights $\tilde{x}$ on
$\widetilde{\Gamma}$ via $\tilde{x}_{\tilde{e}}:=x_{p(\tilde{e})}$ for all
$\tilde{e}\in\widetilde{\mathsf{D}}$, so $\widetilde{\Gamma}$ is a weighted
directed graph, which is locally finite.

Fix base vertices $v_{0}\in\mathsf{V}$ and $\tilde{v}_{0}\in p^{-1}(v_{0})$,
and recall from Lemma 2.4 that $p$ induces an injection
$p_{*}\colon\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})\to\pi_{1}(\Gamma,v_{0})$
between the fundamental groups of the associated graphs, so
$\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})$ can be considered as a subgroup of
$\pi_{1}(\Gamma,v_{0})$ of index $d$. Therefore, as explained in Section 2.5,
any representation
$\rho\colon\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})\to\operatorname{GL}(W)$
induces a representation
$\rho^{\\#}\colon\pi_{1}(\Gamma,v_{0})\to\operatorname{GL}(Z)$.

######  Theorem 3.6.

For any covering map of connected directed graphs
$p\colon\widetilde{\Gamma}\to\Gamma$ as above and any representation
$\rho\colon\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})\to\operatorname{GL}(W)$,
there is an isomorphism $\psi\colon W^{\widetilde{\mathsf{V}}}\to
Z^{\mathsf{V}}$ such that
$\psi\circ\mathsf{A}_{\widetilde{\Gamma}}^{\rho}=\mathsf{A}_{\Gamma}^{\rho^{\\#}}\circ\psi$.

######  Remark 3.7.

The existence of an isomorphism $W^{\widetilde{\mathsf{V}}}\simeq
Z^{\mathsf{V}}$ is a chain-complex version of the Eckmann-Shapiro Lemma,
traditionally stated in the context of group (co)homology (see e.g. [6, p.
73]). Moreover, the tensor-product definition of the induced representation
(see [31, Chapter 7]) makes the existence of this isomorphism a routine check.
The interesting part of Theorem 3.6 is the explicit form of this isomorphism
in this setting, which turns out to conjugate the relevant twisted adjacency
operators.

Before giving the proof of Theorem 3.6, we present a couple of consequences.

######  Corollary 3.8.

If $\widetilde{\Gamma}$ is a connected covering digraph of $\Gamma$ of finite
degree, then $\mathsf{A}_{\widetilde{\Gamma}}$ is conjugate to
$\mathsf{A}_{\Gamma}\oplus\mathsf{A}_{\Gamma}^{\rho^{\prime}}$ for some
representation $\rho^{\prime}$ of $\pi_{1}(\Gamma,v_{0})$.

###### Proof.

Applying Theorem 3.6 to the trivial representation $\rho=1$ of
$\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})=:H$, we get that
$\mathsf{A}^{\rho}_{\widetilde{\Gamma}}=\mathsf{A}_{\widetilde{\Gamma}}$ is
conjugate to $\mathsf{A}_{\Gamma}^{\rho^{\\#}}$, with $\rho^{\\#}$ the induced
representation of $\pi_{1}(\Gamma,v_{0})=:G$. By definition, this
representation is nothing but the action of $G$ on the vector space $Z$ with
basis $G/H$, an action given by left multiplication of $G$ on $G/H$. Since $G$
acts by permutation on the set $G/H$, which is finite, the subspace of $Z$
generated by the sum of these basis elements is fixed by this action.
Therefore, the induced representation splits as
$\rho^{\\#}=1\oplus\rho^{\prime}$ for some representation $\rho^{\prime}$ of
$\pi_{1}(\Gamma,v_{0})$. The statement now follows from the second and third
points of Remark 3.2. ∎

######  Corollary 3.9.

If $\widetilde{\Gamma}\to\Gamma$ is a normal covering map of finite degree
with $\widetilde{\Gamma}$ connected, then $\mathsf{A}_{\widetilde{\Gamma}}$ is
conjugate to

$\bigoplus_{\rho\text{
irred.}}\left(\mathsf{A}_{\Gamma}^{\rho\circ\mathrm{pr}}\right)^{\oplus\deg(\rho)}\,,$

where the direct sum is over all irreducible representations of
$G(\widetilde{\Gamma}/\Gamma)$, and $\mathrm{pr}$ stands for the canonical
projection of $\pi_{1}(\Gamma,v_{0})$ onto
$\pi_{1}(\Gamma,v_{0})/p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))=G(\widetilde{\Gamma}/\Gamma)$.

###### Proof.

Applying Theorem 3.6 to the trivial representation $\rho=1$ of
$\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})$, we see that the induced
representation can be written as
$\rho^{\\#}=\rho_{\mathrm{reg}}\circ\mathrm{pr}$, with $\mathrm{pr}$ as above
and $\rho_{\mathrm{reg}}$ the so-called regular representation of
$G(\widetilde{\Gamma}/\Gamma)$. Since this group is finite, this
representation splits as

$\rho_{\mathrm{reg}}=\bigoplus_{\rho\text{ irred.}}\rho^{\oplus\deg(\rho)}\,,$

the sum being over all irreducible representations of
$G(\widetilde{\Gamma}/\Gamma)$ (see [31, Section 2.4]). The statement now
follows from the second point of Remark 3.2. ∎

###### Proof of Theorem 3.6.

Let $p\colon\widetilde{\Gamma}\to\Gamma$ be a covering map of degree $d$
sending the base vertex $\tilde{v}_{0}$ of $\widetilde{\Gamma}$ to the base
vertex $v_{0}$ of $\Gamma$, with $\Gamma=(\mathsf{V},\mathsf{D},s,t)$ a
locally finite and connected directed graph endowed with edge-weights
$x=(x_{e})_{e\in\mathsf{D}}$, and
$\widetilde{\Gamma}=(\widetilde{\mathsf{V}},\widetilde{\mathsf{D}},s,t)$ a
(locally finite) connected directed graph endowed with the lifted edge-weights
$\tilde{x}=(\tilde{x}_{\tilde{e}})_{\tilde{e}\in\widetilde{\mathsf{D}}}$
defined by $\tilde{x}_{\tilde{e}}=x_{p(\tilde{e})}$. As always, we use the
same notation $\widetilde{\Gamma},\Gamma$ for the directed graphs and for the
associated graphs.

Let
$\rho\colon\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})\to\operatorname{GL}(W)$
be a representation, and let
$\rho^{\\#}\colon\pi_{1}(\Gamma,v_{0})\to\operatorname{GL}(Z)$ be the induced
representation. The aim is to find connections $\widetilde{\Phi}$ on
$W^{\widetilde{\mathsf{V}}}$ and $\Phi$ on $Z^{\mathsf{V}}$ such that
$\rho^{\widetilde{\Phi}}=\rho$ and $\rho^{\Phi}=\rho^{\\#}$, together with a
natural isomorphism $\psi\colon W^{\widetilde{\mathsf{V}}}\to Z^{\mathsf{V}}$
such that the following diagram commutes:

$\textstyle{W^{\widetilde{\mathsf{V}}}}$$\textstyle{Z^{\mathsf{V}}}$$\textstyle{W^{\widetilde{\mathsf{V}}}}$$\textstyle{Z^{\mathsf{V}}.}$$\textstyle{\psi}$$\textstyle{\mathsf{A}_{\widetilde{\Gamma}}^{\widetilde{\Phi}}}$$\textstyle{\mathsf{A}_{\Gamma}^{\Phi}}$$\textstyle{\psi}$

Note that here, we use the more precise notation $\mathsf{A}_{\Gamma}^{\Phi}$
(instead of $\mathsf{A}_{\Gamma}^{\rho^{\\#}}$) for the operator
$\mathsf{A}_{\Gamma}$ twisted by the connection $\Phi$, and similarly for
$\mathsf{A}_{\widetilde{\Gamma}}^{\widetilde{\Phi}}$ instead of
$\mathsf{A}_{\widetilde{\Gamma}}^{\rho}$.

Since $\Gamma$ is connected, it contains a spanning tree $T$. Note that for
any $v\in\mathsf{V}$, there is a path $\gamma_{v}$ in $T$ from $v_{0}$ to $v$
which is unique up to homotopy. Set $\Phi=(\varphi_{e})_{e\in\mathsf{D}}$ with
$\varphi_{e}=\rho^{\\#}_{[e]}\in\operatorname{GL}(Z)$ and
$[e]\in\pi_{1}(\Gamma,v_{0})$ defined by

$[e]=[\gamma_{s(e)}\,e\,\overline{\gamma}_{t(e)}]\,,$

where $\overline{\gamma}$ denotes the inverse of the path $\gamma$. This is
illustrated in Figure 1. The lift $p^{-1}(T)$ of $T$ is a subgraph of
$\widetilde{\Gamma}$ which does not contain any circuit and spans all vertices
of $\widetilde{\Gamma}$, i.e. it is a spanning forest. Since
$\widetilde{\Gamma}$ is connected, this spanning forest can be completed to a
spanning tree $\widetilde{T}$ of $\widetilde{\Gamma}$. Here again, for any
$\tilde{v}\in\widetilde{\mathsf{V}}$, there is a path $\gamma_{\tilde{v}}$ in
$\widetilde{T}$ from $\tilde{v}_{0}$ to $\tilde{v}$ which is unique up to
homotopy. Set
$\tilde{\varphi}_{\tilde{e}}=\rho_{[\tilde{e}]}\in\operatorname{GL}(W)$ with
$[\tilde{e}]=[\gamma_{s(\tilde{e})}\,\tilde{e}\,\overline{\gamma}_{t(\tilde{e})}]\in\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0})$.
By construction, the connections $\Phi$ and $\widetilde{\Phi}$ represent
$\rho^{\\#}$ and $\rho$, respectively.

We now come to the definition of the map $\psi\colon
W^{\widetilde{\mathsf{V}}}\to Z^{\mathsf{V}}$. For $f\in
W^{\widetilde{\mathsf{V}}}$ and $v\in\mathsf{V}$, set

$\psi(f)(v)=\sum_{{\tilde{v}}\in
p^{-1}(v)}\rho^{\\#}_{g_{\tilde{v}}}(f({\tilde{v}}))\in Z,$

where for any ${\tilde{v}}\in p^{-1}(v)$, the element
$g_{\tilde{v}}\in\pi_{1}(\Gamma,v_{0})$ is defined by

$g_{\tilde{v}}=[\gamma_{v}\,p(\overline{\gamma}_{\tilde{v}})]\,.$

To show that $\psi$ is an isomorphism, first note that it splits as the direct
sum $\psi=\bigoplus_{v\in\mathsf{V}}\psi_{v}$, with $\psi_{v}$ the restriction
of $\psi$ to $W^{p^{-1}(v)}$. Therefore, we only need to check that for all
$v\in\mathsf{V}$, the map

$\psi_{v}\colon\bigoplus_{\tilde{v}\in p^{-1}(v)}W\longrightarrow
Z,\quad(f({\tilde{v}}))_{\tilde{v}}\longmapsto\sum_{{\tilde{v}}\in
p^{-1}(v)}\rho^{\\#}_{g_{\tilde{v}}}(f({\tilde{v}}))$

is an isomorphism. By definition of the induced representation, we have
$Z=\bigoplus_{r\in R}\rho_{r}^{\\#}(W)$, where $R\subset\pi_{1}(\Gamma,v_{0})$
is a set of representatives of the cosets
$\pi_{1}(\Gamma,v_{0})/p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))$.
Therefore, we are left with the proof that for all $v\in\mathsf{V}$, the set
$\\{g_{\tilde{v}}\,|\,{\tilde{v}}\in p^{-1}(v)\\}$ is a set of representatives
of these cosets. In other words, we need to show that for any
$g\in\pi_{1}(\Gamma,v_{0})$, there is a unique $\tilde{v}\in p^{-1}(v)$ such
that $g=g_{\tilde{v}}\,h$ with $h\in
p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))$.

\begin{overpic}[width=199.16928pt]{gamma.pdf} \put(-1.0,10.0){$v_{0}$}
\put(102.0,-1.0){$s(e)$} \put(86.0,45.0){$t(e)$} \put(101.0,25.0){$e$}
\put(70.0,3.0){$\gamma_{s(e)}$} \put(53.0,39.0){$\overline{\gamma}_{t(e)}$}
\end{overpic} Figure 1. The composition of the three paths $\gamma_{s(e)}$,
$e$ and $\overline{\gamma}_{t(e)}$ forms a loop based at $v_{0}$ whose
homotopy class
$[\gamma_{s(e)}\,e\,\overline{\gamma}_{t(e)}]\in\pi_{1}(\Gamma,v_{0})$
corresponds to $[e]\in\pi_{1}(\Gamma,T)$.

To check this claim, note that the path $\gamma_{\tilde{v}}$ can be written as
$\gamma_{\tilde{v}}=\alpha\,\tilde{\gamma}_{v}$, with $\alpha$ a path in
$\widetilde{T}$ from $\tilde{v}_{0}$ to
$t(\alpha)=[p(\alpha)]\cdot\tilde{v}_{0}\in p^{-1}(v_{0})$ (recall the
transitive action of $\pi_{1}(\Gamma,v_{0})$ on $p^{-1}(v_{0})$ from Section
2.3), and $\tilde{\gamma}_{v}$ the unique lift of $\gamma_{v}$ with
$s(\tilde{\gamma}_{v})=t(\alpha)$. As a consequence, we have
$g_{\tilde{v}}=[\gamma_{v}\,p(\overline{\gamma}_{\tilde{v}})]=[\gamma_{v}\,\overline{\gamma}_{v}\,p(\overline{\alpha})]=[p(\alpha)]^{-1}$.
Hence, given any $g\in\pi_{1}(\Gamma,v_{0})$, let $\tilde{v}$ be the unique
element in $p^{-1}(v)$ such that the corresponding path
$\gamma_{\tilde{v}}=\alpha\,\tilde{\gamma}_{v}$ satisfies
$[p(\alpha)]^{-1}\cdot\tilde{v}_{0}=g\cdot\tilde{v}_{0}$. By construction, we
now have $g^{-1}g_{\tilde{v}}$ belonging to the isotropy subgroup of
$\tilde{v}_{0}$, i.e. to $p_{*}(\pi_{1}(\widetilde{\Gamma},\tilde{v}_{0}))$.
This completes the proof that $\psi$ is an isomorphism.

Let us now check that the diagram commutes, i.e. that the equality

$(\psi\circ\mathsf{A}_{\widetilde{\Gamma}}^{\widetilde{\Phi}})(f)(v)=(\mathsf{A}_{\Gamma}^{\Phi}\circ\psi)(f)(v)$

holds for all $f\in W^{\widetilde{\mathsf{V}}}$ and all $v\in\mathsf{V}$.
Expanding the left-hand side using the definition of $\psi$, of
$\mathsf{A}_{\widetilde{\Gamma}}^{\widetilde{\Phi}}$ and of
$\widetilde{\Phi}$, the linearity of $\rho^{\\#}_{g}$, the equality
$\rho_{[\tilde{e}]}=\rho^{\\#}_{p_{*}([\tilde{e}])}$ together with the fact
that $\rho^{\\#}$ is a group homomorphism, we get

$(\psi\circ\mathsf{A}_{\widetilde{\Gamma}}^{\widetilde{\Phi}})(f)(v)=\sum_{{\tilde{v}}\in
p^{-1}(v)}\sum_{\tilde{e}\in\widetilde{\mathsf{D}}_{\tilde{v}}}\tilde{x}_{\tilde{e}}\,\rho^{\\#}_{g_{\tilde{v}}\,p_{*}([\tilde{e}])}(f(t(\tilde{e})))\,.$

Expanding the right-hand side in a similar way, we get

$(\mathsf{A}_{\Gamma}^{\Phi}\circ\psi)(f)(v)=\sum_{e\in\mathsf{D}_{v}}\sum_{\tilde{w}\in
p^{-1}(t(e))}x_{e}\,\rho^{\\#}_{[e]\,g_{\tilde{w}}}(f({\tilde{w}}))\,.$

Since $p\colon\widetilde{\Gamma}\to\Gamma$ is a covering map, we can apply the
second point of Lemma 2.4, which states that the two families of evaluations
of $f$ displayed above are over the same subset of $\widetilde{\mathsf{V}}$.
Furthermore, the equality $\tilde{x}_{\tilde{e}}=x_{e}$ holds by definition.
Therefore, we are left with the proof that for any
$\tilde{e}\in\widetilde{\mathsf{D}}$ with source vertex $\tilde{v}$, target
vertex $\tilde{w}$ and image $p(\tilde{e})=e$, the equality
$[e]\,g_{\tilde{w}}=g_{\tilde{v}}\,p_{*}([\tilde{e}])$ holds in
$\pi_{1}(\Gamma,v_{0})$. Writing $p(\tilde{v})=v$ and $p(\tilde{w})=w$, we
have

$[e]\,g_{\tilde{w}}=[\gamma_{v}\,e\,\overline{\gamma}_{w}]\,[\gamma_{w}\,p(\overline{\gamma}_{\tilde{w}})]=[\gamma_{v}\,e\,p(\overline{\gamma}_{\tilde{w}})]=[\gamma_{v}\,p(\overline{\gamma}_{\tilde{v}})]\,[p(\gamma_{\tilde{v}})\,e\,p(\overline{\gamma}_{\tilde{w}})]=g_{\tilde{v}}\,p_{*}([\tilde{e}])\,.$

This concludes the proof. ∎

###  3.3. The Artin formalism for graphs

In his foundational work in algebraic number theory [2, 3], Artin associates
an $L$-series to any Galois field extension endowed with a representation of
its Galois group. He shows that these $L$-series satisfy $4$ axioms, the so-
called Artin formalism (see [28, Chapter XII.2] for a modern account). Since
then, analogous axioms have been shown to hold for $L$-series in topology
[27], in analysis [16], and for some $L$-series associated to finite graphs
[34].

The aim of this subsection is to explain how Theorem 3.6 can be interpreted as
(the non-trivial part) of an Artin formalism for graphs. We also show that our
approach allows for wide generalisations of the results of Stark and Terras
[33, 34].

Recall from Section 3.1 that to any weighted locally finite directed graph
$\Gamma=(\mathsf{V},\mathsf{D},s,t)$ endowed with a representation
$\rho\colon\pi_{1}(\Gamma,v_{0})=:\pi_{1}(\Gamma)\to\operatorname{GL}(W)$, we
associate a twisted weighted adjacency operator $\mathsf{A}_{\Gamma}^{\rho}$
in $\operatorname{End}(W^{\mathsf{V}})$, well-defined up to conjugation.
Hence, given a normal covering $p\colon\widetilde{\Gamma}\to\Gamma$ and a
representation $\rho\colon G\to\operatorname{GL}(W)$ of its Galois group
$G:=G(\widetilde{\Gamma}/\Gamma)=\pi_{1}(\Gamma)/\pi_{1}(\widetilde{\Gamma})$,
one can consider the representation $\rho\circ\mathrm{pr}$ of
$\pi_{1}(\Gamma)$, where $\mathrm{pr}\colon\pi_{1}(\Gamma)\to G$ denotes the
canonical projection.

Let $\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho)$ be the associated conjugacy
class
$\left[\mathsf{A}_{\Gamma}^{\rho\circ\mathrm{pr}}\right]\in\operatorname{End}(W^{\mathsf{V}})/\\!\\!\sim$.

######  Proposition 3.10.

This association satisfies the following $4$ axioms.

  1. 1.

$\mathcal{O}(\widetilde{\Gamma}/\Gamma,1)=[\mathsf{A}_{\Gamma}]$, the
untwisted adjacency operator on $\Gamma$.

  2. 2.

Given any two representations $\rho_{1}$ and $\rho_{2}$ of $G$, we have

$\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho_{1}\oplus\rho_{2})=\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho_{1})\oplus\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho_{2})\,.$

  3. 3.

If $H$ is a normal subgroup of $G$ and
$\overline{\Gamma}=H\backslash\widetilde{\Gamma}$ denotes the corresponding
covering of $\Gamma$, then for any representation $\rho$ of $G/H$, we have

$\mathcal{O}(\overline{\Gamma}/\Gamma,\rho)=\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho\circ\pi)\,,$

where $\pi\colon G\to G/H$ denotes the canonical projection.

  4. 4.

If $H$ is a subgroup of $G$ and
$\overline{\Gamma}=H\backslash\widetilde{\Gamma}$, then for any representation
$\rho$ of $H$, we have

$\mathcal{O}(\widetilde{\Gamma}/\overline{\Gamma},\rho)=\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho^{\\#})\,,$

where $\rho^{\\#}$ is the representation of $G$ induced by $\rho$.

###### Proof.

The first and second points are reformulations of the trivial Remarks 3.2 (ii)
and (iii), while the third point follows from the fact that the composition
$\pi\circ\mathrm{pr}\colon\pi_{1}(\Gamma)\to G/H$ coincides with the canonical
projection of $\pi_{1}(\Gamma)$ onto
$\pi_{1}(\Gamma)/\pi_{1}(\overline{\Gamma})$. As for the last point, let
$\overline{p}\colon\overline{\Gamma}\to\Gamma$ denote the relevant covering
map, and $\overline{\mathrm{pr}}$ the canonical projection of
$\pi_{1}(\overline{\Gamma})$ onto
$\pi_{1}(\overline{\Gamma})/\pi_{1}(\widetilde{\Gamma})=H$. By naturality, the
composition of $\overline{\mathrm{pr}}$ with the inclusion of $H$ in $G$
coincides with $\mathrm{pr}\circ\overline{p}_{*}$. Therefore, the
representation induced by $\rho\circ\overline{\mathrm{pr}}$ coincides with
$\rho^{\\#}\circ\mathrm{pr}$. The fourth point is now a formal consequence of
Theorem 3.6:

$\mathcal{O}(\widetilde{\Gamma}/\overline{\Gamma},\rho)=[\mathsf{A}_{\overline{\Gamma}}^{\rho\circ\overline{\mathrm{pr}}}]=[\mathsf{A}_{\Gamma}^{(\rho\circ\overline{\mathrm{pr}})^{\\#}}]=[\mathsf{A}_{\Gamma}^{\rho^{\\#}\circ\mathrm{pr}}]=\mathcal{O}(\widetilde{\Gamma}/\Gamma,\rho^{\\#})\,.\qed$

With the $L$-series of [34] in mind, it is natural to consider
$\det(\operatorname{I}-\mathsf{A}_{\Gamma}^{\rho\circ\mathrm{pr}})^{-1}$ as
the object of study. The fact that these $L$-series satisfy the Artin
formalism follows from the proposition above.

Actually, our method easily yields results on more general $L$-series, as
follows. Let us fix a map associating to a weighted graph
$(\mathsf{G},\mathsf{x})$ a weighted directed graph $(\Gamma,x)$, as in
Examples 3.3–3.5. Formally, we want this assignment to preserve the
ingredients of Theorem 3.6: a covering map
$\widetilde{\mathsf{G}}\to\mathsf{G}$ of locally finite connected graphs is
sent to a covering map $\widetilde{\Gamma}\to\Gamma$ of locally finite
connected digraphs, and there is a natural group homomorphism
$\alpha\colon\pi_{1}(\Gamma)\to\pi_{1}(\mathsf{G})$. Given any representation
$\rho$ of $\pi_{1}(\mathsf{G})$, we can now consider the $L$-series

$L(\mathsf{G},\mathsf{x},\rho)=\det(\operatorname{I}-\mathsf{A}_{\Gamma}^{\rho\circ\alpha})^{-1}\in\mathbb{C}[\\![\mathsf{x}]\\!]\,.$

By the Amitsur formula (see [1, 30]), it can be written as

$L(\mathsf{G},\mathsf{x},\rho)=\prod_{[\gamma]}\det(1-x(\gamma)\rho_{\gamma})^{-1}\,,$

where the product is over all loops $\gamma$ in $\Gamma$ that cannot be
expressed as $\delta^{\ell}$ for some path $\delta$ and integer $\ell>1$,
loops considered up to change of base vertex. Also, $x(\gamma)$ denotes the
product of the weights of the edges of $\gamma$, while $\rho_{\gamma}$ is the
monodromy of the loop $\gamma$. (Note that changing the base point yields a
conjugate monodromy, so $\det(1-x(\gamma)\rho_{\gamma})$ is well defined.) Of
course, these loops in $\Gamma$ correspond to some class of loops in
$\mathsf{G}$, a class which depends on the way $\Gamma$ is obtained from
$\mathsf{G}$. But for any such assignment, the results of Section 3.2 have
straightforward implications on the corresponding $L$-series, and on the
corresponding class of loops in $\mathsf{G}$.

For concreteness, let us focus on the directed line graph assignment
$\mathsf{G}\mapsto\Gamma$ described in Example 3.5. The corresponding twisted
weighted operator $\operatorname{I}-\mathsf{A}_{\Gamma}^{\rho\circ\alpha}$
coincides with the operator considered in [34, Theorem 7], where the authors
restrict themselves to representations of a finite quotient of
$\pi_{1}(\mathsf{G})$, i.e. representations of the Galois group of a finite
cover of $\mathsf{G}$. In the expression displayed above, the product is over
so-called prime cycles in $\mathsf{G}$, i.e. equivalence classes of cyclic
loops in $\mathsf{G}$ that do not contain a subpath of the form
$(e,\overline{e})$ and that cannot be expressed as the power of a shorter
loop. In the special case when $\rho$ factorises through a finite quotient of
$\pi_{1}(\mathsf{G})$, this is what Stark and Terras define as the multiedge
Artin $L$-function of $\mathsf{G}$, an object extending several other
functions introduced in [33, 34].

The theory of Section 3 applied to $\mathsf{A}_{\Gamma}^{\rho\circ\alpha}$ now
allow us to easily extend their results to this more general $L$-function. For
example, our Corollary 3.8 shows that if $\widetilde{\mathsf{G}}$ is a finite
connected covering graph of a connected graph $\mathsf{G}$, then
$L(\mathsf{G},\mathsf{x},1)^{-1}$ divides
$L(\widetilde{\mathsf{G}},\tilde{\mathsf{x}},1)^{-1}$, extending Corollary 1
of [33, Theorem 3]. Also, our Corollary 3.9 recovers the corollary of [34,
Proposition 3], while our Theorem 3.6 extends Theorem 8 of [34]. Finally,
expanding the equality $\log
L(\widetilde{\mathsf{G}},\tilde{\mathsf{x}},\rho)=\log
L(\mathsf{G},\mathsf{x},\rho^{\\#})$ yields an extension of the technical
Lemma 7 of [34] to more general covers and representations.

We conclude this section by recalling that our approach immediately yields
similar results for any assignment $\mathsf{G}\mapsto\Gamma$ preserving
covering maps.

##  4\. Combinatorial applications

Each time the determinant of an operator counts combinatorial objects, Theorem
3.6 and Corollaries 3.8 and 3.9 have combinatorial implications. This is the
case of the operators given in Examples 3.3 and 3.4, whose determinants count
spanning trees and perfect matchings, respectively. We explain these
applications in Sections 4.1 and 4.2. We also briefly enumerate additional
applications in Section 4.3.

###  4.1. Spanning trees and rooted spanning forests

Our first combinatorial application relies on a slightly generalised version
of the matrix-tree theorem, that we now recall.

Let $\mathsf{G}=(\mathsf{V},\mathsf{E})$ be a finite graph endowed with
symmetric weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}\in\mathsf{E}}$, that we
consider as formal variables. Let $\Delta_{\mathsf{G}}$ be the associated
Laplacian, acting on $\mathbb{C}^{\mathsf{V}}$ via

$\Delta_{\mathsf{G}}f(v)=\sum_{e\in\mathsf{D}_{v}}x_{e}(f(v)-f(t(e)))$

for $f\in\mathbb{C}^{\mathsf{V}}$ and $v\in\mathsf{V}$. Set $n:=|\mathsf{V}|$,
and consider the characteristic polynomial in $|\mathsf{E}|+1$ variables

$P_{\mathsf{G}}(\lambda):=\det(\lambda\operatorname{I}-\Delta_{\mathsf{G}})=\sum_{i=0}^{n}c_{i}\,\lambda^{i}\in\mathbb{Z}[\mathsf{x},\lambda]\,.$

Then, the coefficient $c_{i}\in\mathbb{Z}[\mathsf{x}]$ admits the
combinatorial interpretation

$(-1)^{n-i}\,c_{i}=\sum_{F\subset\mathsf{G},\;|\pi_{0}(F)|=i}\phi(F)\prod_{\mathsf{e}\in\mathsf{E}(F)}\mathsf{x}_{\mathsf{e}}\,,$

where the sum is over all spanning forests $F$ in $\mathsf{G}$ with $i$
connected components (or equivalently, with $n-i$ edges), and
$\phi(F)\in\mathbb{Z}_{+}$ denotes the number of possible roots of $F$: if
$F=\bigsqcup_{j}T_{j}$ denotes the decomposition of $F$ into connected
components, then $\phi(F)=\prod_{j}|\mathsf{V}(T_{j})|$.

For example, there is a unique spanning forest $F$ in $\mathsf{G}$ with $n$
connected components (given by the vertices of $\mathsf{G}$), it admits a
unique root, leading to the expected value $c_{n}=1$. As additional reality
checks, we have the values
$-c_{n-1}=2\sum_{\mathsf{e}\in\mathsf{E}}\mathsf{x}_{\mathsf{e}}$ and
$c_{0}=\det(\Delta_{\mathsf{G}})=0$. Finally, since connected spanning forests
coincide with spanning trees, and all spanning trees admit exactly $n$ roots,
we have

$(-1)^{n-1}\,c_{1}=n\sum_{T\subset\mathsf{G}}\prod_{\mathsf{e}\in\mathsf{E}(T)}\mathsf{x}_{\mathsf{e}}\,,$

the sum being over all spanning trees of $\mathsf{G}$. This latter result is
nothing but Kirchoff’s matrix-tree theorem.

######  Remark 4.1.

This result can be derived from the (usual version of the) matrix-tree theorem
applied to the graph obtained from $\mathsf{G}$ by adding one vertex connected
to each vertex of $\mathsf{G}$ by an edge of weight $-\lambda$.

Let us also mention that this result was obtained by Chung and Langlands in
the context of graphs endowed with vertex-weights rather than edge-weights
[7]. Theorem 3.6 trivially extends to graphs endowed with vertex-weights (in
addition to edge-weights), and it is a routine task to adapt the results of
the present subsection to this more general case.

######  Definition 4.2.

The spanning tree partition function of a weighted graph
$(\mathsf{G},\mathsf{x})$ is

$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x}):=\sum_{T\subset\mathsf{G}}\prod_{\mathsf{e}\in\mathsf{E}(T)}\mathsf{x}_{\mathsf{e}}\,,$

the sum being over all spanning trees in $\mathsf{G}$. Similarly, the rooted
spanning forest partition function of $(\mathsf{G},\mathsf{x})$ is

$\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},\mathsf{x}):=\sum_{F\subset\mathsf{G}}\phi(F)\prod_{\mathsf{e}\in\mathsf{E}(F)}\mathsf{x}_{\mathsf{e}}\,,$

the sum being over all spanning forests in $\Gamma$.

Note that if one sets all the weights to $1$, then
$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},1)$ is the number of spanning trees in
$\mathsf{G}$, while $\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},1)$ counts the
number of rooted spanning forests in $\mathsf{G}$.

######  Theorem 4.3.

Let $\widetilde{\mathsf{G}}$ be a finite covering graph of a finite connected
graph $\mathsf{G}$ endowed with edge-weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}\in\mathsf{E}}$, and let
$\tilde{\mathsf{x}}$ denote these weights lifted to the edges of
$\widetilde{\mathsf{G}}$. Then
$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})$ divides
$\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ and
$\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},\mathsf{x})$ divides
$\mathsf{Z}_{\mathit{RSF}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ in the
ring $\mathbb{Z}[\mathsf{x}]$.

This immediately leads to the following corollary. The first point is known
since the work of Berman (see [4, Theorem 5.7]), while the second one appears
to be new.

######  Corollary 4.4.

Let $\widetilde{\mathsf{G}}$ be a finite covering graph of a finite connected
graph $\mathsf{G}$.

  1. (i)

The number of spanning trees in $\mathsf{G}$ divides the number of spanning
trees in $\widetilde{\mathsf{G}}$.

  2. (ii)

The number of rooted spanning forests in $\mathsf{G}$ divides the number of
rooted spanning forests in $\widetilde{\mathsf{G}}$.∎

###### Proof of Theorem 4.3.

First note that
$\mathsf{Z}_{\mathit{RSF}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ is
multiplicative with respect to connected sum while
$\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ vanishes
for $\widetilde{\mathsf{G}}$ not connected. Therefore, it can be assumed that
$\widetilde{\mathsf{G}}$ is connected. Let
$\widetilde{\mathsf{G}}\to\mathsf{G}$ be a covering map between two finite
connected graphs, with edge-weights $\mathsf{x}$ on $\mathsf{G}$ inducing
lifted edge-weights $\tilde{\mathsf{x}}$ on $\widetilde{\mathsf{G}}$. Let
$\widetilde{\Gamma}$ (resp. $\Gamma$) be the graph associated with
$\widetilde{\mathsf{G}}$ (resp. $\mathsf{G}$) as in Example 3.3. Note that the
graphs $\widetilde{\Gamma}$ and $\Gamma$ remain finite and connected, and the
covering map $\widetilde{\mathsf{G}}\to\mathsf{G}$ trivially extends to a
covering map $\widetilde{\Gamma}\to\Gamma$. By Example 3.3 and Corollary 3.8,
we know that $\Delta_{\widetilde{\mathsf{G}}}=\mathsf{A}_{\widetilde{\Gamma}}$
is conjugate to
$\mathsf{A}_{\Gamma}\oplus\mathsf{A}_{\Gamma}^{\rho}=\Delta_{\mathsf{G}}\oplus\Delta_{\mathsf{G}}^{\rho}$
for some representation $\rho$ of $\pi_{1}(\Gamma,v_{0})$. Therefore, setting
$P_{\mathsf{G}}^{\rho}(\lambda):=\det(\lambda\operatorname{I}-\Delta^{\rho}_{\mathsf{G}})\in\mathbb{C}[\mathsf{x},\lambda]$,
we have the equality

$P_{\widetilde{\mathsf{G}}}(\lambda)=P_{\mathsf{G}}(\lambda)\cdot
P^{\rho}_{\mathsf{G}}(\lambda)\in\mathbb{C}[\mathsf{x},\lambda]\,.$

Observe that $P_{\widetilde{\mathsf{G}}}(\lambda)$ and
$P_{\mathsf{G}}(\lambda)$ belong to $\mathbb{Z}[\mathsf{x},\lambda]$, so
$P^{\rho}_{\mathsf{G}}(\lambda)$ belongs to the intersection of
$\mathbb{C}[\mathsf{x},\lambda]$ with the field of fractions
$Q(\mathbb{Z}[\mathsf{x},\lambda])={\mathbb{Q}}(\mathsf{x},\lambda)$, i.e. it
belongs to the ring ${\mathbb{Q}}[\mathsf{x},\lambda]$. Since the leading
$\lambda$-coefficient of $P_{\mathsf{G}}(\lambda)$ is equal to $1$, the
greatest common divisor of its coefficients is $1$. An application of Gauss’s
lemma (see e.g. [29, Corollary 2.2]) now implies that
$P^{\rho}_{\mathsf{G}}(\lambda)$ belongs to $\mathbb{Z}[\mathsf{x},\lambda]$.
In conclusion, we have that $P_{\mathsf{G}}(\lambda)$ divides
$P_{\widetilde{\mathsf{G}}}(\lambda)$ in $\mathbb{Z}[\mathsf{x},\lambda]$.

By the extended matrix-tree theorem stated above, we have that
$P_{\mathsf{G}}(-1)=\pm\mathsf{Z}_{\mathit{RSF}}(\mathsf{G},\mathsf{x})$
divides
$P_{\widetilde{\mathsf{G}}}(-1)=\pm\mathsf{Z}_{\mathit{RSF}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$
in $\mathbb{Z}[\mathsf{x}]$, proving the second claim.

To show the first one, consider again the equation
$P_{\widetilde{\mathsf{G}}}(\lambda)=P_{\mathsf{G}}(\lambda)\cdot
P^{\rho}_{\mathsf{G}}(\lambda)$ in $\mathbb{Z}[\mathsf{x},\lambda]$, and
observe that $P_{\widetilde{\mathsf{G}}}(\lambda)$ and
$P_{\mathsf{G}}(\lambda)$ are both multiples of $\lambda$. Dividing both sides
by $\lambda$ and setting $\lambda=0$, the matrix-tree theorem (in the form
stated above) implies

$|\mathsf{V}(\widetilde{\mathsf{G}})|\cdot\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})=\pm|\mathsf{V}(\mathsf{G})|\cdot\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})\cdot
P^{\rho}_{\mathsf{G}}(0)\,,$

i.e.
$\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})=\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})\cdot
g(\mathsf{x})$, with $g(\mathsf{x})=\frac{\pm
1}{\deg(\widetilde{\mathsf{G}}/\mathsf{G})}P^{\rho}_{\mathsf{G}}(0)\in{\mathbb{Q}}[\mathsf{x}]$.
Since both
$\mathsf{Z}_{\mathit{ST}}(\widetilde{\mathsf{G}},\tilde{\mathsf{x}})$ and
$\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})$ belong to
$\mathbb{Z}[\mathsf{x}]$ and the greatest common divisor of the coefficients
of $\mathsf{Z}_{\mathit{ST}}(\mathsf{G},\mathsf{x})$ is $1$, one more
application of Gauss’s lemma yields that $g(\mathsf{x})$ lies in
$\mathbb{Z}[\mathsf{x}]$, and concludes the proof. ∎

###  4.2. Perfect matchings

In this subsection, we review some applications of Theorem 3.6 to perfect
matchings, and more generally to the dimer model.

Recall that a perfect matching (or dimer configuration) in a graph $\Gamma$ is
a family of edges $M\subset\mathsf{E}$ such that each vertex of $\Gamma$ is
adjacent to a unique element of $M$. If $\Gamma$ is finite and endowed with
symmetric edge-weights
$\mathsf{x}=\\{\mathsf{x}_{\mathsf{e}}\\}_{\mathsf{e}\in\mathsf{E}}$, then one
defines the dimer partition function of $\Gamma$ as

$\mathsf{Z}_{\text{dimer}}(\Gamma,\mathsf{x})=\sum_{M}\prod_{\mathsf{e}\in
M}\mathsf{x}_{\mathsf{e}}\,,$

the sum being over all perfect matchings in $\Gamma$. Note that if all the
weights are equal to $1$, then $\mathsf{Z}_{\text{dimer}}(\Gamma,1)$ simply
counts the number of perfect matchings in $\Gamma$.

Now, assume that $\Gamma$ is embedded in the plane, and endowed with an
orientation of its edges so that around each face of
$\Gamma\subset\mathbb{R}^{2}$, there is an odd number of edges oriented
clockwise. Let $x=\\{x_{e}\\}_{e\in\mathsf{D}}$ be the anti-symmetric edge-
weights obtained as in Example 3.4, and let $\mathsf{A}_{\Gamma}$ be the
associated weighted skew-adjacency operator. By Kasteleyn’s celebrated theorem
[20, 21], the Pfaffian of $\mathsf{A}_{\Gamma}$ is equal to
$\pm\mathsf{Z}_{\text{dimer}}(\Gamma,\mathsf{x})$.

With this powerful method in hand, we can try to use Theorem 3.6 in studying
the dimer model on symmetric graphs. Quite unsurprisingly, the straightforward
applications of our theory are not new. Indeed, the only divisibility
statement that we obtain via Corollary 3.8 is the following known result (see
Theorem 3 of [15] for the bipartite case, and Section IV.C of [25] for a
general discussion).

######  Proposition 4.5.

Fix a planar, finite, connected weighted graph
$(\widetilde{\Gamma},\tilde{\mathsf{x}})$ invariant under rotation around a
point in the complement of $\widetilde{\Gamma}$, of angle $\frac{2\pi}{d}$ for
some odd integer $d$. Let $(\Gamma,\mathsf{x})$ be the resulting quotient
weighted graph. Then, the partition function
$\mathsf{Z}_{\mathrm{dimer}}(\Gamma,\mathsf{x})$ divides
$\mathsf{Z}_{\mathrm{dimer}}(\widetilde{\Gamma},\tilde{\mathsf{x}})$ in the
ring $\mathbb{Z}[\mathsf{x}]$.

###### Proof.

Let us fix an orientation of the edges of $\Gamma$ satisfying the clockwise-
odd condition. It lifts to an orientation of $\widetilde{\Gamma}$ which
trivially satisfies the same condition around all faces except possibly the
face containing the center of rotation; for this later face, it does satisfy
the condition since $d$ is odd. Hence, we have a $d$-fold cyclic covering of
connected weighted graphs $(\widetilde{\Gamma},\tilde{x})\to(\Gamma,x)$, and
Corollary 3.8 can be applied. Together with Kasteleyn’s theorem, it yields the
following equality in $\mathbb{C}[\mathsf{x}]$:

$\mathsf{Z}_{\text{dimer}}(\widetilde{\Gamma},\tilde{\mathsf{x}})^{2}=\det(\mathsf{A}_{\widetilde{\Gamma}})=\det(\mathsf{A}_{\Gamma})\det(\mathsf{A}_{\Gamma}^{\rho})=\mathsf{Z}_{\text{dimer}}(\Gamma,\mathsf{x})^{2}\cdot\det(\mathsf{A}_{\Gamma}^{\rho})\,.$

This ring being factorial, it follows that
$\mathsf{Z}_{\text{dimer}}(\widetilde{\Gamma},\tilde{\mathsf{x}})=\mathsf{Z}_{\text{dimer}}(\Gamma,\mathsf{x})\cdot
g$ for some $g\in\mathbb{C}[\mathsf{x}]$. The fact that $g$ belongs to
$\mathbb{Z}[\mathsf{x}]$ follows from Gauss’s lemma as in the proof of Theorem
4.3. ∎

Our approach is limited by the fact that we consider graph coverings
$\widetilde{\Gamma}\to\Gamma$ which, in the case of normal coverings,
correspond to free actions of $G(\widetilde{\Gamma}/\Gamma)$ on
$\widetilde{\Gamma}$. For this specific question of enumerating dimers on
symmetric planar graphs, the discussion of Section IV of [25] is more
complete, as non-free actions are also considered.

However, our approach is quite powerful when applied to non-planar graphs.
Indeed, recall that Kasteleyn’s theorem can be extended to weighted graphs
embedded in a closed (possibly non-orientable) surface $\Sigma$, but the
computation of the dimer partition function requires the Pfaffians of
$2^{2-\chi(\Sigma)}$ different (possibly complex-valued) skew-adjacency
matrices [35, 11, 8]. In particular, the partition function of any graph
embedded in the torus $\mathbb{T}^{2}$ is given by $4$ Pfaffians. For the
Klein bottle $\mathcal{K}$, we also need $4$ Pfaffians, which turn out to be
two pairs of conjugate complex numbers, so $2$ well-chosen Pfaffians are
sufficient. We now illustrate the use of Theorem 3.6 in these two cases.

Let us first consider a toric graph $\Gamma\subset\mathbb{T}^{2}$, and let
$\widetilde{\Gamma}=\Gamma_{mn}$ denote the lift of $\Gamma$ by the natural
$m\times n$ covering of the torus by itself. This covering is normal with
Galois group
$G(\widetilde{\Gamma}/\Gamma)\simeq\mathbb{Z}/m\mathbb{Z}\oplus\mathbb{Z}/n\mathbb{Z}$.
This group being abelian, all the irreducible representations are of degree
$1$; more precisely, they are given by $\\{\rho(z,w)\\}_{w^{m}=1,\,z^{n}=1}$,
where $\rho(z,w)$ maps a fixed generator of $\mathbb{Z}/m\mathbb{Z}$ (resp.
$\mathbb{Z}/n\mathbb{Z}$) to $w\in\mathbb{C}^{*}$ (resp.
$z\in\mathbb{C}^{*}$). Writing
$P_{mn}(z,w)=\det(\mathsf{A}_{\Gamma_{mn}}^{\rho(z,w)})$ and $P_{1,1}=P$,
Corollary 3.9 immediately yields the equality

$P_{mn}(1,1)=\prod_{z^{n}=1}\prod_{w^{m}=1}P(z,w)\,.$

This is the well-known Theorem 3.3 of [24], a result of fundamental importance
in the study of the dimer model on biperiodic graphs.

Figure 2. A graph $\Gamma$ embedded in the Klein bottle $\mathcal{K}$
(pictured as a square with opposite sides identified according to the arrows),
and the lift $\Gamma_{mn}\subset\mathcal{K}$, here with $m=2$ and $n=3$.

Let us now consider a weighted graph $\Gamma$ embedded in the Klein bottle
$\mathcal{K}$, and let $\widetilde{\Gamma}=\Gamma_{mn}$ denote the lift of
$\Gamma$ by the natural $m\times n$ cover $\mathcal{K}_{mn}\to\mathcal{K}$ of
the Klein bottle by itself (with $n$ odd), as illustrated in Figure 2. Now, we
can interpret the two skew-adjacency matrices of
$\widetilde{\Gamma}=\Gamma_{mn}$ used in the computation of the corresponding
dimer partition function as weighted adjacency operators twisted by
$1$-dimensional representations $\rho,\rho^{\prime}$ of
$\pi_{1}(\mathcal{K}_{mn})<\pi_{1}(\mathcal{K})$. Using Theorem 3.6, we see
that these matrices are conjugate to the skew-adjacency operators on
$\Gamma\subset\mathcal{K}$ twisted by the corresponding induced
representations $\rho^{\\#},(\rho^{\prime})^{\\#}$ of $\pi_{1}(\mathcal{K})$.
Unlike that of the torus, the fundamental group of the Klein bottle is not
abelian, so the representations $\rho^{\\#},(\rho^{\prime})^{\\#}$ need not
split as products of $1$-dimensional representations. It turns out that they
split as products of representations of degree $1$ and $2$, yielding a closed
formula for $\mathsf{Z}_{\text{dimer}}(\Gamma_{mn},x)$ in terms of
determinants of $\mathsf{A}_{\Gamma}^{\tau}$, with $\tau$ of degree $1$ and
$2$. This result is at the core of the study of the dimer model on Klein
bottles of the first-named author [9].

As a final remark, let us note that all the considerations of this subsection
can be applied equally well to the Ising model, either via the use of Kac-Ward
matrices [17], or via skew-adjacency matrices on the associated Fisher graph
[12].

###  4.3. Further combinatorial applications

We conclude this article with a very brief and informal description of
additional applications of our results.

As discovered by Forman [13], the determinant of $\Delta_{\mathsf{G}}^{\rho}$
with $\deg(\rho)=1$ can be expressed as a sum over cycle-rooted spanning
forests (CRSFs) in $\mathsf{G}$, each forest being counted with a complex
weight depending on $\rho$. If there is a finite connected covering
$\widetilde{\mathsf{G}}\to\mathsf{G}$ and a degree $1$ representation of
$\pi_{1}(\widetilde{\mathsf{G}},\tilde{v}_{0})$ such that the induced
representation of $\pi_{1}(\mathsf{G},v_{0})$ admits a degree $1$
subrepresentation $\rho^{\prime}$, then the CRSF partition function on
$\mathsf{G}$ twisted by $\rho^{\prime}$ divides the partition function on
$\widetilde{\mathsf{G}}$ twisted by $\rho$, in the ring
$\mathbb{C}[\mathsf{x}]$. Furthermore, in the case of a normal abelian
covering of degree $d$, Corollary 3.9 gives a factorisation of the CRSF
partition function of $\widetilde{\mathsf{G}}$ in terms of $d$ CRSF partition
functions of $\mathsf{G}$.

Finally, let $X$ be a finite CW-complex of dimension $r$ with weights
$\mathsf{x}=(\mathsf{x}_{\mathsf{e}})_{\mathsf{e}}$ associated to the cells of
top dimension. Let $\mathsf{G}$ be the weighted graph with vertex set given by
the $(r-1)$-dimensional cells of $X$, two such vertices being connected by an
unoriented edge of $\mathsf{G}$ each time they are in the boundary of an
$r$-dimensional cell. (Note that if $r=1$, then the $1$-dimensional cell
complex $X$ is nothing but the geometric realisation of the graph
$\mathsf{G}$.) Finally, let $\Gamma$ denote the weighted graph obtained from
$\mathsf{G}$ as in Example 3.3. Then, the resulting operator
$\mathsf{A}_{\Gamma}$ is the Laplacian $\Delta_{X}$ acting on $r$-cells of
$X$. This operator can be used to count so-called higher dimensional rooted
forests in $X$, see [18, 5] and references therein. Using Corollary 3.8, it is
now straightforward to prove that, given any finite cover $\widetilde{X}\to
X$, the corresponding rooted forest partition function of $X$ divides the
rooted forest partition function of $\widetilde{X}$, extending Theorem 4.3 to
higher dimensional objects.

## References

  * [1] S. A. Amitsur.  On the characteristic polynomial of a sum of matrices.  Linear and Multilinear Algebra, 8(3):177–182, 1979/80.
  * [2] E. Artin.  Über eine neue Art von L-Reihen.  Abh. Math. Sem. Univ. Hamburg, 3(1):89–108, 1924.
  * [3] E. Artin.  Zur Theorie der L-Reihen mit allgemeinen Gruppencharakteren.  Abh. Math. Sem. Univ. Hamburg, 8(1):292–306, 1931.
  * [4] Kenneth A. Berman.  Bicycles and spanning trees.  SIAM J. Algebraic Discrete Methods, 7(1):1–12, 1986.
  * [5] Olivier Bernardi and Caroline J. Klivans.  Directed rooted forests in higher dimension.  Electron. J. Combin., 23(4):Paper 4.35, 20, 2016.
  * [6] Kenneth S. Brown.  Cohomology of groups, volume 87 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1994.  Corrected reprint of the 1982 original.
  * [7] F. R. K. Chung and Robert P. Langlands.  A combinatorial Laplacian with vertex weights.  J. Combin. Theory Ser. A, 75(2):316–327, 1996.
  * [8] David Cimasoni.  Dimers on graphs in non-orientable surfaces.  Lett. Math. Phys., 87(1-2):149–179, 2009.
  * [9] David Cimasoni.  The dimer and Ising models on Klein bottles.  2020\.  arXiv:2010.11047 [math-ph].
  * [10] David Cimasoni and Adrien Kassel.  2020+.  in preparation.
  * [11] David Cimasoni and Nicolai Reshetikhin.  Dimers on surface graphs and spin structures. I.  Comm. Math. Phys., 275(1):187–208, 2007.
  * [12] Michael E. Fisher.  On the dimer solution of planar Ising models.  Journal of Mathematical Physics, 7(10):1776–1781, 1966.
  * [13] Robin Forman.  Determinants of Laplacians on graphs.  Topology, 32(1):35–46, 1993.
  * [14] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.
  * [15] William Jockusch.  Perfect matchings and perfect squares.  J. Combin. Theory Ser. A, 67(1):100–115, 1994.
  * [16] Jay Jorgenson and Serge Lang.  Artin formalism and heat kernels.  J. Reine Angew. Math., 447:165–200, 1994.
  * [17] Mark Kac and John C. Ward.  A combinatorial solution of the two-dimensional Ising model.  Phys. Rev., 88:1332–1337, 1952.
  * [18] Gil Kalai.  Enumeration of ${\bf Q}$-acyclic simplicial complexes.  Israel J. Math., 45(4):337–351, 1983.
  * [19] Adrien Kassel and Thierry Lévy.  2020+.  in preparation.
  * [20] P. W. Kasteleyn.  Dimer statistics and phase transitions.  J. Mathematical Phys., 4:287–293, 1963.
  * [21] P. W. Kasteleyn.  Graph theory and crystal physics.  In Graph Theory and Theoretical Physics, pages 43–110. Academic Press, London, 1967.
  * [22] Richard Kenyon.  Spanning forests and the vector bundle Laplacian.  Ann. Probab., 39(5):1983–2017, 2011.
  * [23] Richard Kenyon.  Conformal invariance of loops in the double-dimer model.  Comm. Math. Phys., 326(2):477–497, 2014.
  * [24] Richard Kenyon, Andrei Okounkov, and Scott Sheffield.  Dimers and amoebae.  Ann. of Math. (2), 163(3):1019–1056, 2006.
  * [25] Greg Kuperberg.  An exploration of the permanent-determinant method.  The Electronic Journal of Combinatorics, pages R46–R46, 1998.
  * [26] Jin Ho Kwak and Roman Nedela.  Graphs and their coverings.  2005\.
  * [27] Serge Lang.  $L$-series of a covering.  Proc. Nat. Acad. Sci. U.S.A., 42:422–424, 1956.
  * [28] Serge Lang.  Algebraic number theory, volume 110 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1994.
  * [29] Serge Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 2002.
  * [30] Christophe Reutenauer and Marcel-Paul Schützenberger.  A formula for the determinant of a sum of matrices.  Lett. Math. Phys., 13(4):299–302, 1987.
  * [31] Jean-Pierre Serre.  Linear representations of finite groups, volume 42.  Springer, 1977.
  * [32] Jean-Pierre Serre.  Trees.  Springer-Verlag, Berlin-New York, 1980.  Translated from the French by John Stillwell.
  * [33] H. M. Stark and A. A. Terras.  Zeta functions of finite graphs and coverings.  Adv. Math., 121(1):124–165, 1996.
  * [34] H. M. Stark and A. A. Terras.  Zeta functions of finite graphs and coverings. II.  Adv. Math., 154(1):132–195, 2000.
  * [35] Glenn Tesler.  Matchings in graphs on non-orientable surfaces.  J. Combin. Theory Ser. B, 78(2):198–231, 2000.
  * [36] George W. Whitehead.  Elements of homotopy theory, volume 61 of Graduate Texts in Mathematics.  Springer-Verlag, New York-Berlin, 1978.