# Arborescences of Covering Graphs

###### Abstract.

An _arborescence_ of a directed graph $\Gamma$ is a spanning tree directed
toward a particular vertex $v$. The arborescences of a graph rooted at a
particular vertex may be encoded as a polynomial $A_{v}(\Gamma)$ representing
the sum of the weights of all such arborescences. The arborescences of a graph
and the arborescences of a covering graph $\tilde{\Gamma}$ are closely
related. Using _voltage graphs_ to construct arbitrary regular covers, we
derive a novel explicit formula for the ratio of $A_{v}(\Gamma)$ to the sum of
arborescences in the lift $A_{\tilde{v}}(\tilde{\Gamma})$ in terms of the
determinant of Chaiken’s voltage Laplacian matrix, a generalization of the
Laplacian matrix. Chaiken’s results on the relationship between the voltage
Laplacian and vector fields on $\Gamma$ are reviewed, and we provide a new
proof of Chaiken’s results via a deletion-contraction argument.

##  1\. Introduction

In this paper, we examine the relationship between arborescences of a graph
and the arborescences of its covering graph. An _arborescence_ rooted at a
vertex $v$ in a directed graph $\Gamma$ is a weighted spanning tree of
$\Gamma$ that is directed towards $v$. We define $A_{v}(\Gamma)$ to be the sum
of the weights of all arborescences in $\Gamma$ rooted at $v$. Using the
Matrix Tree Theorem [FS99, Theorem 5.6.8], we can compute $A_{v}(\Gamma)$ as a
minor of the Laplacian matrix of $\Gamma$.

It is natural to ask to what extent the arborescences of a graph $\Gamma$
characterize the arborescences of a covering graph $\tilde{\Gamma}$. Every
arborescence of $\Gamma$ lifts to a partial arborescence of $\tilde{\Gamma}$,
and this lift is unique if the root of the arborescence in $\tilde{\Gamma}$ is
fixed. Conversely, every arborescence of $\tilde{\Gamma}$ descends to a
subgraph of $\Gamma$ containing an arborescence. These properties lead us to
ask whether there is a meaningful relationship between $A_{v}(\Gamma)$ and
$A_{\tilde{v}}(\tilde{\Gamma})$, where $\tilde{v}$ is a lift of $v$. We show
that $A_{v}(\Gamma)$ always divides $A_{\tilde{v}}(\tilde{\Gamma})$, meaning
that each arborescence of $\Gamma$ corresponds to a set of arborescences of
$\tilde{\Gamma}$. The primary goals of this paper are to derive an explicit
formula for the ratio $\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$
and to examine cases where this ratio is especially computationally nice.

The ratio $\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ first arose in
Galashin and Pylyavskyy’s study of _$R$ -systems_ [GP19]. The $R$-system is a
discrete dynamical system on a edge-weighted strongly connected simple
directed graph $\Gamma=(V,E,\wt)$ whose state vector $X=(X_{v})_{v\in V}$
evolves to its next state $X^{\prime}=(X_{v}^{\prime})_{v\in V}$ according to
the following relation:

(1) $\displaystyle\sum_{(u,v)\in
E}\wt(u,v)\frac{X_{v}}{X_{u}^{\prime}}=\sum_{(v,w)\in
E}\wt(v,w)\frac{X_{w}}{X_{v}^{\prime}}$

In (1), the vertex $v$ is fixed, and the vertices $u$ and $w$ range over the
start and endpoints of the ingoing and outgoing edges of $v$, respectively.
This system is homogeneous in both $X$ and $X^{\prime}$, so we consider
solutions in projective space. Galashin and Pylyavskyy determined all
solutions $X^{\prime}$ of this equation as a function of $X$:

######  Theorem 1.1.

[GP19] The system given by equation (1) has solution

$\displaystyle X^{\prime}_{v}=\frac{X_{v}}{A_{v}(\Gamma)}.$

This solution is unique up to scalar multiplication, yielding a unique
solution to the $R$-system in $\mathbb{P}^{|V|}$.

However, we can see the value of $X^{\prime}_{v}$ in equation (1) depends only
on the neighborhood of the vertex $v$. Thus, in the case of a covering graph
$\tilde{\Gamma}$, we may find two solutions to the $R$-system: one by applying
the previous theorem directly, and one by treating each vertex of
$\tilde{\Gamma}$ locally like a vertex of $\Gamma$, and then applying the
theorem. The two respective solutions are

$\displaystyle
X_{\tilde{v}}^{\prime}=\frac{X_{\tilde{v}}}{A_{\tilde{v}}(\tilde{\Gamma})}$
and $\displaystyle
X_{\tilde{v}}^{\prime}=\frac{X_{\tilde{v}}}{A_{v}({\Gamma})}.$

Therefore, uniqueness of the solution implies that the vectors

$\displaystyle\left(\frac{X_{\tilde{v}}}{A_{\tilde{v}}(\tilde{\Gamma})}\right)_{\tilde{v}\in\tilde{V}}$
and
$\displaystyle\left(\frac{X_{\tilde{v}}}{A_{v}({\Gamma})}\right)_{\tilde{v}\in\tilde{V}}$

are scalar multiples of each other, where $\tilde{v}$ is any lift of $v$.
Equivalently:

######  Corollary 1.2.

When $\Gamma$ is strongly connected and simple, the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ is independent of the
choice of vertex $v$ and of the choice of lift $\tilde{v}$.

The existence of this invariance motivates finding an explicit formula for
this ratio. The following is the main theorem of this paper.

######  Theorem 1.3.

Let $\Gamma=(V,E,\wt)$ be an edge-weighted multigraph, and let
$\tilde{\Gamma}$ be a $k$-fold cover of $\Gamma$ such that each lifted edge is
assigned the same weight as its base edge. Denote by $\mathscr{L}(\Gamma)$ the
voltage Laplacian of $\Gamma$. Then for any vertex $v$ of $\Gamma$ and any
lift $\tilde{v}$ of $v$ in $\tilde{\Gamma}$ of $\Gamma$, we have

$\displaystyle\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}=\frac{1}{k}{\det[\mathscr{L}(\Gamma)}]_{\BZ[E]}.$

If $\tilde{\Gamma}$ is a regular cover, it is a derived cover by a group $G$
with $|G|=k$. In this case, in the above formula
$\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$ is the determinant of
$\mathscr{L}(\Gamma)$ as a $\BZ[E]$-linear transformation. We may evaluate
this determinant by restriction of scalars (see Section 3 for details). For an
arbitrary cover (including non-regular ones), the matrix
$[\mathscr{L}(\Gamma)]_{\BZ[E]}$ can be determined concretely from the
covering graph (Definition 3.5), so the determinant can be explicitly
computed.

When $\tilde{\Gamma}$ is a regular cover of prime order, we will be able to
prove the following refinement in Section 3.2:

######  Corollary 1.4.

Let $p$ be a prime, let $\Gamma=(V,E,\wt,\nu)$ be an edge-weighted
$\BZ/p\BZ$-voltage directed multigraph, and let $\mathscr{L}(\Gamma)$ be its
voltage Laplacian matrix. Then for any vertex $v$ of $\Gamma$ and any lift
$\tilde{v}$ of $v$ in the derived graph $\tilde{\Gamma}$ of $\Gamma$, we have

$\displaystyle\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$
$\displaystyle=\frac{1}{|G|}N_{\BQ(\zeta_{p})/\BQ}\left(\det\left[\mathscr{L}(\Gamma)\right]\right)$
$\displaystyle=\frac{1}{|G|}\prod_{i=1}^{p-1}\det[\sigma_{i}(\mathscr{L}(\Gamma))]$

where
$N_{\BQ(\zeta_{p})/\BQ}\left(\det\left[\mathscr{L}(\Gamma)\right]\right)$
denotes the field norm of $\BQ(\zeta_{p})$ over $\BQ$, naturally extended to a
norm on $\BQ(\zeta_{p})[E]$, and $\sigma_{i}$ is the field automorphism on
$\BQ(\zeta_{p})$ mapping $\zeta_{p}\mapsto\zeta_{p}^{i}$.

In the case $|G|=2$, we obtain a conjecture by Galashin and Pylyavskyy:

######  Corollary 1.5.

Let $\Gamma=(V,E,\wt,\nu)$ be an edge-weighted $\BZ/2\BZ$-voltage directed
multigraph, and let $\mathscr{L}(\Gamma)$ be its voltage Laplacian matrix.
Then for any vertex $v$ of $\Gamma$ and any lift $\tilde{v}$ of $v$ in the
derived graph $\tilde{\Gamma}$ of $\Gamma$, we have

$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}=\frac{1}{2}\det\left[\mathscr{L}(\Gamma)\right].$

Corollary 1.5 follows directly from Corollary 1.4 by setting $p=2$ and noting
that $\sigma_{1}$ is the identity.

Theorem 1.3 allows us to easily conclude nice properties about the ratio:

######  Corollary 1.6.

If the edge weights of $\Gamma$ are indeterminates then the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ is a homogeneous
polynomial in the edge weights with integer coefficients.

######  Proof 1.7.

Since ${\det[\mathscr{L}(\Gamma)}]_{\BZ[E]}\in\BZ[E]$, Theorem 1.3 tells us
that $\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}\in\BQ[E]$. Note that
every coefficient of $A_{v}(\Gamma)$ is 1 since every edge of $\Gamma$ has a
different weight. Therefore, $A_{v}(\Gamma)$ is a primitive polynomial over
the integers, so by Gauss’ lemma,
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}\in\BZ[E]$.

Homogeneity follows from the fact that every arborescence of a given graph has
the same number of edges.

We furthermore conjecture the following (see Section 5):

######  Conjecture 1.8.

Let $\Gamma$ be a directed graph, $\tilde{\Gamma}$ a $k$-cover of $\Gamma$,
$v$ a vertex of $\Gamma$ and $\tilde{v}$ a lift of $v$ in $\tilde{\Gamma}$. If
the edge weights of $\Gamma$ are indeterminates then the polynomial
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ has positive
coefficients.

This conjecture suggests there may be a combinatorial interpretation of
$\det[\mathscr{L}(\Gamma)]_{\mathbb{Z}[E]}$.

Conjecture 1.8 is motivated by the positivity property of cluster algebras.
Cluster algebras, introduced by Fomin and Zelevinsky [FZ02], are rings with a
distinguished set of generators called _cluster variables_. Algebraically
independent subsets of cluster variables are called _clusters_. Galashin and
Pylyavskyy’s $R$-systems are intimately related to cluster algebras (see
Section 9 of [GP19]), so it is reasonable to expect that the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ that arises in the
context of $R$-systems may also be related to cluster algebras.

It is obvious from the definition of a cluster algebra that given a cluster,
we can write all cluster variables as a rational function with all positive
coefficients in the variables of that cluster. However, it is also true (and
not at all obvious) that this rational function can always be simplified to a
Laurent polynomial with positive coefficients. Our situation is similar: it is
obvious that both $A_{\tilde{v}}(\tilde{\Gamma})$ and $A_{v}(\Gamma)$ have
positive coefficients. By Theorem 1.3, we know the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ is a polynomial and we
believe that, as in the case of cluster algebras, this polynomial has positive
coefficients.

It is also useful to explore the consequences of our main result in a graph
theory context, as it describes a relationship between a graph and its covers.

One might be interested in the ratio of the _numbers_ of arborescences of
$\tilde{\Gamma}$ and of $\Gamma$. We can get this number from Theorem 1.3 by
specializing the edge weights to 1:

$\displaystyle\frac{A_{\tilde{v}}(\tilde{\Gamma})|_{wt=1}}{A_{v}(\Gamma)|_{wt=1}}=\left.\frac{1}{k}{\det[\mathscr{L}(\Gamma)}]_{\BZ[E]}\right|_{wt=1}.$

It is conceivable that this special case might be easier to prove than the
general result, but we have not found this to be the case. It is worth noting
that the positivity conjecture is trivial in this setting, since the number of
arborescences must always be nonnegative.

Our main theorem is an example of a result relating an invariant of a graph to
the same invariant on its cover. It would be interesting to try to describe
similar results on a larger class of graph invariants.

######  Problem 1.9.

For which graph invariants $I$ does the ratio
$\frac{I(\tilde{\Gamma})}{I(\Gamma)}$ have nice properties? For example, when
can the ratio be expressed as an integer or a polynomial with integer
coefficients? When does the ratio have positivity properties?

One invariant for which our work gives a partial answer is the number of Euler
circuits. An Euler circuit in a directed graph is a cycle that uses each edge
of the graph precisely once. Euler showed that a graph has an Euler circuit
precisely when the graph is connected and every vertex has the same number of
edges in and out. In this case, the so-called “BEST” Theorem [vAEdB51] gives a
formula for the number of Euler circuits $E(G)$ of a graph $G$:

$E(G)=A_{v}(G)|_{\wt=1}\cdot\prod_{v\text{ vertex in }G}(\deg v-1)!,$

where $\deg v$ is the outdegree of $v$.

We can combine this formula with Theorem 1.3 to say:

######  Corollary 1.10.

$\frac{E(\tilde{\Gamma})}{E(\Gamma)}=\frac{1}{k}\left.\det[\mathscr{L}(\Gamma)]_{\BZ[E]}\right|_{\wt=1}\cdot\prod_{v}((\deg
v-1)!)^{k-1},$

where the product is over the vertices in $\Gamma$. This quantity is a
positive integer.

A recent example of this approach was taken by Verma [Ver21], who explored the
ratio of Tutte polynomials between a graph and its cover. For certain very
special graphs and a particular specialization of the Tutte polynomial, the
ratio in Problem 1.9 is nice, although in general, the ratio of Tutte
polynomials does behave nearly as nicely as the ratio of arborescence sums.

The rest of the paper will proceed as follows. Section 2 covers the background
and conventions necessary to read this paper. In this section, we also discuss
the Laplacian matrix and the Matrix Tree Theorem in greater detail, and give
additional topological background on covering graphs. In particular, we
introduce the _voltage graph_ , a construction that allows us to compactly
describe arbitrary regular covering graphs $\tilde{\Gamma}$ by assigning a
group-valued voltage to each edge of $\Gamma$. In Section 3, we prove the main
theorem. We also describe restriction of scalars and prove Corollary 1.4.
Section 4 reviews some known results relating _vector fields_ on voltage
graphs to the voltage Laplacian. Vector fields are closely related to
arborescences, and this discussion especially helps to frame the results of
the case of $2$-fold covers. We conclude with several open questions in
Section 5.

##  2\. Background and Definitions

###  2.1. Arborescences

Let $\Gamma=(V,E,\wt)$ be an edge-weighted directed multigraph with a weight
function on the edges $\wt:E\to R$, for some ring $R$. We will usually
abbreviate “edge-weighted” to “weighted” and “directed multigraph” to “graph.”
We will consider the weights of the edges of $G$ to be indeterminates,
treating the weight $\wt(e)$ of an edge $e$ as a variable. Let the set of such
variables be denoted $\wt(E)$. We denote the source vertex of an edge $e$ by
$e_{s}$ and target vertex of $e$ by $e_{t}$. If an edge has source $v$ and
target $w$, we may write $e=(v,w)$. However, note that when $\Gamma$ is not
necessarily simple, there may be more than one edge satisfying these
properties, so $(v,w)$ may specify multiple edges. We denote the set of
outgoing edges of a vertex $v$ by $E_{s}(v)$, and the set of incoming edges of
$v$ by $E_{t}(v)$.

######  Definition 2.1.

An _arborescence_ $T$ of $\Gamma$ rooted at $v\in V$ is a spanning tree
directed towards $v$. That is, for all vertices $w$, there exists a unique
directed path from $w$ to $v$ in $T$. 111In the literature, an arborescence
rooted at $v$ is usually defined to be a spanning tree directed _away_ from
$v$, so that $v$ is the unique source rather than the unique sink; see, for
example, [KV06], [Cha82], and [GM89]. Our convention is consistent with the
study of $R$-systems. We denote the set of arborescences of $\Gamma$ rooted at
vertex $v$ by $\mathcal{T}_{v}(\Gamma)$. The _weight of an arborescence_
$\wt(T)$ is the product of the weights of its edges:

$\displaystyle\wt(T)=\prod_{e\in T}\wt(e)$

We denote by $A_{v}(\Gamma)$ the sum of the weights of all arborescences of
$\Gamma$ rooted at $v$:

$\displaystyle A_{v}(\Gamma)=\sum_{T\in\mathcal{T}_{v}(\Gamma)}\wt(T)$

$A_{v}(\Gamma)$ is either zero or a homogeneous polynomial of degree $|V|-1$
in the edge weights of $G$.

######  Example 2.2.

Consider the following edge-weighted directed graph $\Gamma$.

$1$23$a$$b$$d$$e$$c$

The arborescences rooted at 2 are:

$1$23$b$$d$$1$23$b$$e$

The weight of the arborescence on the left is $bd$ and the weight of the
arborescence on the right is $be$. So, $A_{2}(\Gamma)=bd+be$.

###  2.2. The Laplacian matrix and the Matrix Tree Theorem

The Matrix Tree Theorem, also known as Kirchoff’s Theorem, yields a way of
computing $A_{v}(\Gamma)$ through the _Laplacian matrix_ of $\Gamma$.

######  Definition 2.3.

Label the vertices of $\Gamma$ as $v_{1},v_{2},\dots$. The _Laplacian matrix_
$L(\Gamma)$ of a graph $\Gamma$ is the difference of the weighted degree
matrix $D$ and the weighted adjacency matrix $A$ of $\Gamma$:

$\displaystyle L(\Gamma)=D(\Gamma)-A(\Gamma).$

Here, the weighted degree matrix is the diagonal matrix whose $i$-th entry is

$\displaystyle d_{ii}=\sum_{e\in E_{s}(v_{i})}\wt(e)$

and the weighted adjacency matrix has entries defined by

$\displaystyle a_{ij}=\sum_{e=(v_{i},v_{j})}\wt(e).$

Since we will always be working with weighted graphs in this paper, we will
usually drop the word “weighted” when talking about the Laplacian matrix. Note
also the ordering of the rows and columns of the Laplacian. We will always
assume that $v_{1}$ corresponds to the first row and column of $L(\Gamma)$,
that $v_{2}$ corresponds to the second row and column of $L(\Gamma)$, and so
on.

######  Theorem 2.4.

_(Matrix Tree Theorem)_ [Cha82] The sum of the weights of arborescences rooted
at $v_{i}$ is equal to the minor of $L(\Gamma)$ obtained by removing the
$i$-th row and column:

$\displaystyle A_{v_{i}}(\Gamma)=\det[L_{i}^{i}(\Gamma)].$

######  Example 2.5.

For the graph $\Gamma$ from Example 2.2, we have

$D(\Gamma)=\begin{bmatrix}a+b&0&0\\\ 0&c&0\\\ 0&0&d+e\end{bmatrix},\qquad
A(\Gamma)=\begin{bmatrix}a&b&0\\\ 0&0&c\\\ d&e&0\end{bmatrix},\qquad
L(\Gamma)=\begin{bmatrix}b&-b&0\\\ 0&c&-c\\\ -d&-e&d+e\end{bmatrix}.$

Removing row and column 2 and taking the determinant, we get

$\left|\begin{matrix}b&0\\\ -d&d+e\end{matrix}\right|=bd+be.$

As we computed in Example 2.2, this is $A_{2}(\Gamma)$.

###  2.3. Covering graphs, voltage graphs, and derived graphs

######  Definition 2.6.

A _k-fold cover_ of $\Gamma=(V,E)$ is a graph
$\tilde{\Gamma}=(\tilde{V},\tilde{E})$ that is a $k$-fold covering space of
$G$ in the topological sense that preserves edge weight. That is, we require
that a lifted edge in the covering graph has the same weight as its
corresponding base edge in the base graph. In order to use this definition, we
need to find a way to formally topologize directed graphs in a way that
encodes edge orientation. To avoid this, we instead give a more concrete
alternative definition of a covering graph. The graph
$\tilde{\Gamma}=(\tilde{V},\tilde{E})$ is a $k$-fold covering graph of
$\Gamma=(V,E)$ if there exists a projection map
$\pi:\tilde{\Gamma}\rightarrow\Gamma$ such that

  1. (1)

$\pi$ maps vertices to vertices and edges to edges;

  2. (2)

$|\pi^{-1}(v)|=|\pi^{-1}(e)|=k$ for all $v\in V,e\in E$;

  3. (3)

For all $\tilde{e}\in\tilde{E}$, we have $\wt(\tilde{e})=\wt(\pi(\tilde{e}))$;

  4. (4)

$\pi$ is a local homeomorphism. Equivalently,
$|E_{s}(\tilde{v})|=|E_{s}(\pi(\tilde{v}))|$ and
$|E_{t}(\tilde{v})|=|E_{t}(\pi(\tilde{v}))|$ for all $\tilde{v}\in\tilde{V}$.

When we refer to $\tilde{\Gamma}$ as a covering graph of $\Gamma$, we assume a
single distinguished projection $\pi:\tilde{\Gamma}\rightarrow\Gamma$ has been
fixed.

We do not require a covering graph to be connected. However, disconnected
graphs contain no arborescences, so our main quantity of interest
$A_{v}(\tilde{\Gamma})$ is always $0$ in the disconnected case.

######  Definition 2.7.

A _weighted permutation-voltage graph_ $\Gamma=(V,E,\wt,\nu)$ is a weighted
directed multigraph with each edge $e$ also labeled by a permutation
$\nu(e)=\sigma_{e}\in S_{k}$, the symmetric group on $k$ letters. This
labeling is called the _voltage_ of the edge $e$. Note that the voltage of an
edge $e$ is entirely distinct from the weight of $e$.

######  Definition 2.8.

Given a permutation-voltage graph $\Gamma$, we may construct an $k$-fold
covering graph $\tilde{\Gamma}=(\tilde{V},\tilde{E},\wt)$ of $\Gamma$.
$\tilde{\Gamma}$ is a graph with vertex set
$\tilde{V}=V\times\\{1,2,\ldots,k\\}$ and edge set

$\displaystyle\tilde{E}:=\left\\{\left[v\times
x,w\times\sigma_{e}(x)\right]:x\in\\{1,\ldots,k\\},e=(v,w)\in\Gamma\right\\}.$

Every covering graph of $\Gamma$ can be constructed in this way.

######  Example 2.9.

Let $\Gamma$ be the permutation-voltage graph shown in Figure 1, where edges
labeled $(x,y)$ have edge weight $x$ and voltage $y$. Then we can construct a
$k$-fold cover $\tilde{\Gamma}$, with vertices $(v,y)=v^{y}$ and with edges
labeled by weight, is shown in Figure 2.

$1$23$(a,321)$$(b,231)$$(d,123)$$(e,132)$$(c,123)$ Figure 1. A permutation-
voltage graph $\Gamma$.
$1^{1}$$2^{1}$$3^{1}$$1^{2}$$2^{2}$$3^{2}$$1^{3}$$2^{3}$$3^{3}$$a$$a$$a$$b$$b$$b$$c$$c$$c$$d$$d$$d$$e$$e$$e$
Figure 2. The derived covering graph $\tilde{\Gamma}$ of $\Gamma$ in Figure 3.
Edge colors denote correspondence to the edges of $\Gamma$ via the quotient
map.

There is a special case of the above definitions that will be particularly
useful for us. Let $G$ be a finite group of size $k$. Instead of assigning
each lift of an edge an integer in $\\{1,\ldots,k\\}$, we assign it an element
$g$ of $G$. Each edge $e$ of the base graph is assigned a group element
$g_{e}$, and the permutation-voltage $\sigma_{e}$ is obtained by the action of
the group: $\sigma_{e}(x):=\nu(e)\cdot x$. We will abuse notation and write
$\nu(e)=g_{e}$. In this context, we will call $\Gamma$ a $G$-voltage graph.

Given a $G$-voltage graph $\Gamma$, the associated $|G|$-fold covering graph
$\tilde{\Gamma}$ of $\Gamma$ is known as the _derived graph_. The vertex set
of $\tilde{\Gamma}$ is $\tilde{V}=V\times G$ and edge set

$\displaystyle\tilde{E}:=\left\\{\left[v\times x,w\times(gx)\right]:x\in
G,e=(v,w)\in\Gamma,\nu(e)=g\in G\right\\}.$

######  Example 2.10.

Let $G=\BZ/3\BZ=\\{1,g,g^{2}\\}$, and let $\Gamma$ be the $G$-voltage graph
shown in Figure 3, where edges labeled $(x,y)$ have edge weight $x$ and
voltage $y$. Then the derived graph $\tilde{\Gamma}$, with vertices
$(v,y)=v^{y}$ and with edges labeled by weight, is shown in Figure 4.

$1$23$(a,g)$$(b,1)$$(d,g^{2})$$(e,1)$$(c,g^{2})$ Figure 3. A
$\BZ/3\BZ$-voltage graph $\Gamma$.
$1^{1}$$2^{1}$$3^{1}$$1^{g}$$2^{g}$$3^{g}$$1^{g^{2}}$$2^{g^{2}}$$3^{g^{2}}$$a$$a$$a$$b$$b$$b$$c$$c$$c$$d$$d$$d$$e$$e$$e$
Figure 4. The derived covering graph $\tilde{\Gamma}$ of $\Gamma$ in Figure 3.
Edge colors denote correspondence to the edges of $\Gamma$ via the quotient
map.

While derived graphs in one sense are a very special subclass of covering
graphs, they actually account for all _regular covering graphs_.

######  Definition 2.11.

Given a graph $\Gamma$ and a covering graph $\tilde{\Gamma}$, the _deck group_
$\Aut(\pi)$ of $\tilde{\Gamma}$ is the subgroup of graph automorphisms on
$\tilde{\Gamma}$ that commute with $\pi$.

######  Definition 2.12.

A _regular cover_ $\tilde{\Gamma}$, sometimes known as a _Galois cover_ , of a
graph $\Gamma$ is a covering graph whose deck group is transitive on each
fiber $\pi^{-1}(v)$ for each $v\in V$.

######  Example 2.13.

Note that the vertex $1^{1}$ in Example 2.9 is part of a 2-cycle but vertex
$1^{2}$ is not. Thus, there is no automorphism that maps $1^{1}$ to $1^{2}$.
This means that $\tilde{\Gamma}$ is not a regular cover.

On the other hand, the derived graph in Example 2.10 is a regular cover
because the cyclic permutation $\sigma$ that sends each $v_{i,x}$ to
$v_{i,gx}$ is in $\Aut(\pi)$, which shows that $\Aut(\pi)$ is transitive on
each fiber $\pi^{-1}(v)$.

######  Theorem 2.14.

_(Theorems 3 and 4 in[GT75])_ Every regular cover $\tilde{\Gamma}$ of a graph
$\Gamma$ may be realized as a derived cover of $\Gamma$ with voltage
assignments in $\Aut(\pi)$. Conversely, every derived graph is a regular
cover.

The majority of this paper explores the relationship between the arborescences
of a voltage graph $\Gamma$ and the arborescences of its derived graph
$\tilde{\Gamma}$. Theorem 2.14 allows us to deal with all regular covering
graphs in the framework of a voltage. It turns out that regularity is not
necessary for Theorem 1.3, which holds for all $k$-fold covers; however, the
results of this main theorem have nice interpretations in terms of the voltage
Laplacian in the regular case.

###  2.4. Constructing arborescences of a covering graph: failure of the
obvious approach

In this subsection, we discuss the relationship between arborescences of
$\Gamma$ to arborescences of its cover $\tilde{\Gamma}$. If there were a
simple correspondence of arborescences of $\Gamma$ with (sets of)
arborescences of $\tilde{\Gamma}$, this could lead to a nice combinatorial
proof of Theorem 1.3. Unfortunately, we have not found such a relationship; we
illustrate the pitfalls.

Let $T$ be an arborescence of the base graph $\Gamma$ rooted at $v$. Given a
fixed lift $\tilde{v}$ of $v$ in the covering graph $\tilde{G}$, there exists
a unique connected lift of $T$ to $\tilde{\Gamma}$ by the local homeomorphism
property of covers. The resulting subtree of $\tilde{\Gamma}$ could
potentially be completed to a full arborescence of $\tilde{\Gamma}$, possibly
in multiple ways, by choosing an outgoing edge of the remaining vertices in
such a way as to avoid creating cycles. We project these edges down to $k-1$
_vector fields_ on $\Gamma$, using some method of partitioning the edges into
$k-1$ vector field classes. It is therefore natural to conjecture that
arborescences of $\tilde{\Gamma}$ can be put into correspondence with
arborescences of $\Gamma$ by utilizing this construction: each arborescence of
$\Gamma$ corresponds to a set of arborescences of $\tilde{\Gamma}$ by lifting
and then filling in the remaining edges in various combinations according to
some nicely enumerable vector field pattern. This conjecture was our main
motivation for our study of vector fields; see Section 4 for more discussion
on vector fields.

Unfortunately, it is not true that every arborescence of $\tilde{\Gamma}$ must
stem from such a construction. As a counterexample, consider the base graph
$\Gamma$:

$1$23

with regular $2$-fold covering graph $\tilde{\Gamma}$:

$1^{1}$$2^{1}$$3^{1}$$1^{2}$$2^{2}$$3^{2}$

Then the following is an arborescence of $\tilde{\Gamma}$ rooted at $3^{1}$:

$1^{1}$$2^{1}$$3^{1}$$1^{2}$$2^{2}$$3^{2}$

However, this arborescence cannot be constructed from a lift of an
arborescence of $\Gamma$ rooted at vertex $3$. Any such arborescence must
necessarily contain edges $(3,1)$ and $(1,3)$, which form a $2$-cycle. This
counterexample uses a regular covering graph, and the base graph has no loops
or multiple edges. Therefore non-regularity, loops, and multiple edges are not
essential impediments to the construction. This construction might be
salvageable, but any combinatorial bijection would need to be more complicated
than one that involves merely lifting the base arborescence.

Rather than fixing the data of a single arborescence on $\Gamma$ and
enumerating over the data of certain sets of $k-1$ vector fields on $\Gamma$,
one might consider applying the construction in the opposite way: fix a set of
$k-1$ vector fields and enumerate over arborescences. However, it is even less
clear how this construction would proceed. Moreover, Theorem 1.3 suggests that
the first method is likelier to succeed. Assuming that Conjecture 1.8 is true
(the arborescence ratio has positive coefficients), the theorem implies that
every arborescence of $\Gamma$ is associated to multiple arborescences of
$\tilde{\Gamma}$, which suggests that our first construction attempt is closer
to the truth. It is interesting and surprising that Theorem 1.3 is true
despite the lack of an obvious combinatorial relationship between
arborescences of $\Gamma$ and of $\tilde{\Gamma}$.

###  2.5. The reduced group algebra

We wish to define a matrix similar to the Laplacian matrix that tracks all the
relevant information in an $G$-voltage graph. In order to do so in general, we
need to extend our field of coefficients in order to codify the data given by
the voltage function $\nu$. Following the language of Reiner and Tseng in
[RT14]:

######  Definition 2.15.

The _reduced group algebra_ of a finite group $G$ over a ring $R$ is the
quotient where $R[G]$ is the group algebra of $G$ over $R$. That is, we
quotient the group algebra by the all-ones vector with respect to the basis
given by $G$.

For simplicity, in the remainder of this paper we take $R=\BZ$. Note that if
$G\cong\BZ/2\BZ$, then , with the non-identity element of $G$ identified with
$-1$.

Similarly, if $G\cong\BZ/p\BZ$, with $p$ prime, then , where $\zeta_{p}$ is a
primitive $p$-th root of unity and the generator $g$ of $G$ is identified with
$\zeta_{p}$. (To see this, note that both rings arise by adjoining to $\BZ$ an
element with minimal polynomial $\sum_{i=0}^{p-1}x^{i}$.) The fact that the
reduced group algebra of prime cyclic $G$ lies in a field extension over
$\BQ\supseteq\BZ$ will be important later in giving us nice formulas for the
ratio of arborescences described in the introduction.

###  2.6. The voltage Laplacian matrix

We now define a generalization of the Laplacian matrix that takes into account
voltages:

######  Definition 2.16.

The _voltage adjacency matrix_ $\mathscr{A}(G)$ has entries given by

$\displaystyle a_{ij}=\sum_{e=(v_{i},v_{j})\in E}\nu(e)\text{wt}(e),$

where we consider $\nu(e)$ as an element of the reduced group algebra . That
is, the $i,j$-th entry consists of sum of the _volted_ weights of all edges
going from the $i$-th vertex to the $j$-th vertex. The _voltage Laplacian
matrix_ $\mathscr{L}(\Gamma)$ is defined as

$\displaystyle\mathscr{L}(\Gamma)=D(\Gamma)-\mathscr{A}(\Gamma)$

where $D(\Gamma)$ is the (unvolted) weighted degree matrix as described in
Definition 2.3.

Note that when every edge has trivial voltage, then
$\mathscr{L}(\Gamma)=L(\Gamma)$, so that the voltage Laplacian is indeed a
generalization of the Laplacian. Since we consider the edge weights of
$\Gamma$ as indeterminates, we treat the entries of $\mathscr{L}(G)$ as
elements of —that is, the polynomial ring of edge weights with coefficients in
the reduced group algebra. We will often abuse notation and refer to this ring
as simply .

######  Example 2.17.

Let $\Gamma$ be the $\BZ/3\BZ$-voltage graph in Figure 3. Under the
identification , the voltage Laplacian of $\Gamma$ is

$\displaystyle\mathscr{L}(\Gamma)$ $\displaystyle=\begin{bmatrix}a+b&0&0\\\
0&c&0\\\ 0&0&d+e\end{bmatrix}-\begin{bmatrix}\zeta_{3}a&b&0\\\
0&0&\zeta_{3}^{2}c\\\ \zeta_{3}^{2}d&e&0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}(1-\zeta_{3})a+b&-b&\phantom{00000}0\phantom{00000}\\\
0&c&-\zeta_{3}^{2}c\\\ -\zeta_{3}^{2}d&-e&d+e\end{bmatrix}$

###  2.7. Notation

Before reintroducing our main result, we summarize the conventions and
notation that will be used consistently throughout the rest of the paper. For
a graph $\Gamma=(V,E,\wt)$ and a covering graph
$\tilde{\Gamma}=(\tilde{V},\tilde{E},\wt)$,

  * •

The parameter $n$ refers to the order (number of vertices) of $\Gamma$, and we
write $V=\\{v_{i}:i\in[n]\\}$

  * •

The parameter $k$ refers to the degree of the cover, i.e. $\tilde{\Gamma}$ is
a $k$-fold covering graph of $\Gamma$. When the cover is regular, we have
$k=|G|$.

  * •

We write the vertices of $\tilde{\Gamma}$ as
$\tilde{V}=\\{v_{i}^{j}:i\in[n],j\in[k]\\}$, where
$v_{i}^{1},\cdots,v_{i}^{k}$ are the lifts of $v_{i}$. For regular covers, we
write $\tilde{V}=\\{v_{i}^{g}:i\in[n],g\in G\\}$, associating each vertex with
an element $G$ for the purposes of the following bullet point.

  * •

In the case of a regular $G$-cover, the edges in $\tilde{\Gamma}$ are
$\tilde{E}=\\{(v_{i}^{h},v_{j}^{\nu(v_{i})h}):(v_{i},v_{j})\in E,h\in G\\}$.
When the cover is not necessarily regular, we assign a permutation in
$\mathfrak{S}_{k}$ to each edge of $\Gamma$. Then an edge $e=(v_{a},v_{b})$
with permutation $\sigma$ is lifted to the edges
$\\{(v_{a}^{i},v_{b}^{\sigma(i)}):i\in[k]\\}$; by abuse of notation, we write
$\nu(e)=\sigma$. Note the difference between $\sigma(i)$ and group
multiplication. For example, in Example 2.9, the permutation associated to the
edge $e$ is $132$ in one-line notation.

##  3\. Proof of the Main Theorem

###  3.1. Restriction of scalars

######  Definition 3.1.

Let $R$ be a commutative ring, and let $S$ be a free $R$-algebra of finite
rank. Let $T$ be an $S$-linear transformation on a free $S$-module $M$ of
finite rank. Then we may also consider $M$ as a free $R$-module of finite
rank, and $T$ as an $R$-linear transformation; this is known as _restriction
of scalars_. We write $\det_{R}T$ to denote the determinant of $T$ as an
$R$-linear transformation.

Recall that the voltage Laplacian $\mathscr{L}(\Gamma)$ has entries in the
reduced group algebra augmented by edge weights: $S=$. Letting $R=\BZ[E]$, we
may also consider $\mathscr{L}(\Gamma)$ as an $R$-linear transformation on a
$R$-module of rank $(k-1)n$. Note that due to the definition of the Laplacian
(the fact that row entries sum to 0), we will consider our linear
transformation to act on the right.

######  Example 3.2.

Returning to Example 2.17, the voltage Laplacian $\mathscr{L}(\Gamma)$ is a
matrix that represents a linear transformation on a $\BZ(\zeta_{3})[E]$-module
with basis vectors indexed by the three vertices of $\Gamma$:

$\mathscr{L}(\Gamma)=\begin{bmatrix}(1-\zeta_{3})a+b&-b&0\\\
0&c&-\zeta_{3}^{2}c\\\ -\zeta_{3}^{2}d&-e&d+e\end{bmatrix}$

We may consider this same module as a $\BZ[E]$-module instead, simply by
disallowing scalar multiplication outside of the subring
$\BZ[E]\subseteq\BZ(\zeta_{3})[E]$. Now we look at the basis vectors of the
$\BZ[E]$-module. Since the $\BZ[E]$-span of a set of vectors is smaller than
its $\BZ(\zeta_{3})[E]$-span, however, we will need more basis vectors than
before in order to span the entire module. One basis for this module has basis
vectors doubly indexed by vertices and the two non-identity group elements of
$\BZ/3\BZ$, which shows that the module has $\BZ[E]$-rank $6$. Ordering basis
vectors as
$v_{1}^{g},v_{2}^{g},v_{3}^{g},v_{1}^{g^{2}},v_{2}^{g^{2}},v_{3}^{g^{2}}$, the
voltage Laplacian may considered as a $\BZ[E]$-linear transformation, with
matrix

$\displaystyle[\mathscr{L}(\Gamma)]_{\BZ[E]}=\begin{bmatrix}a+b&-b&0&-a&0&0\\\
0&c&c&0&0&c\\\ d&-e&d+e&d&0&0\\\ a&0&0&2a+b&-b&0\\\ 0&0&-c&0&c&0\\\
-d&0&0&0&-e&d+e\end{bmatrix}$

and the $\BZ[E]$-determinant of this transformation is

$\displaystyle\det_{\BZ[E]}[\mathscr{L}(\Gamma)]$
$\displaystyle:=\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$
$\displaystyle=3a^{2}c^{2}d^{2}+3b^{2}c^{2}d^{2}+6abc^{2}d^{2}+9a^{2}c^{2}e^{2}+3b^{2}c^{2}e^{2}+9abc^{2}e^{2}+9a^{2}c^{2}de+3b^{2}c^{2}de+12abc^{2}de$

###  3.2. The prime cyclic case

The framework provided by restriction of scalar now allows us to prove that
Corollary 1.4 follows from Theorem 1.3.

######  Proof 3.3 (Proof of Corollary 1.4 given Theorem 1.3).

The corollary follows from the theorem if we can show that
$\det_{\BZ[E]}[\mathscr{L}(\Gamma)]=N_{\BQ(\zeta_{p})/\BQ}\left(\det\left[\mathscr{L}(\Gamma)\right]\right)$.
Theorem 1 of [Sil00] states that if $A$ is a commutative ring, if $B$ is a
commutative subring of $\mathrm{Mat}_{n}(A)$, and if
$M\in\mathrm{Mat}_{m}(B)$, then

$\displaystyle\det_{A}[M]=\det_{A}(\det_{B}[M])$

In this case, let $A:=\BQ[E]$. The reduced group algebra
$B:=\BZ(\zeta_{p})[E]$ may be realized as a subring of
$\mathrm{Mat}_{p-1}(A)$, with an element $\alpha$ of $\BZ(\zeta_{p})[E]$ being
identified with the $\BZ[E]$-matrix corresponding to multiplication by
$\alpha$ in $\BZ(\zeta_{p})[E]$, where we view $\BZ(\zeta_{p})[E]$ as an
$\BZ[E]$-module. Note that $\BZ[E]$ and $\BZ(\zeta_{p})[E]$ are both
commutative. Finally, we let $M=\mathscr{L}(\Gamma)$. But the field norm
$N_{\BQ(\zeta_{p})/\BQ}(\alpha)$ is defined as the determinant of the linear
map $x\mapsto\alpha x$ as a $\BQ$-linear transformation, or, equivalently in
our case, a $\BZ$-linear transformation. When extended to $\BQ(\zeta_{p})[E]$,
this definition shows that

$\displaystyle\det_{\BZ[E]}\left(\det_{\BZ(\zeta_{p})[E]}[\mathscr{L}(\Gamma)]\right)=N_{\BQ(\zeta_{p})/\BQ}\left(\det_{\BQ(\zeta_{p})[E]}[\mathscr{L}(\Gamma)]\right)$

as desired.

######  Example 3.4.

Let $\Gamma$ be the graph from Figure 3. We compute
$\det[\mathscr{L}(\Gamma)]$ in Example 4.3:

$\displaystyle\det[\mathscr{L}(\Gamma)]=(1-\zeta_{3})bcd+(1-\zeta_{3})acd+(1-\zeta_{3}^{2})bce+(1-\zeta_{3})(1-\zeta_{3}^{2})ace$

Since voltage is given by $\BZ/3\BZ$, the reduced group algebra is
$\BZ(\zeta_{3})[E]\subset\BQ(\zeta_{3})[E]$, which we treat as an extension
over $\BQ$. The Galois norm in this case is the same as the complex norm,
since the Galois conjugate of an element of $\BQ(\zeta_{3})[E]$ is its complex
conjugate. This norm is

$\displaystyle\det[\mathscr{L}(\Gamma)]\det[$
$\displaystyle=\left((1-\zeta_{3})bcd+(1-\zeta_{3})acd+(1-\zeta_{3}^{2})bce+(1-\zeta_{3})(1-\zeta_{3}^{2})ace\right)$
$\displaystyle\cdot\left((1-\zeta_{3}^{2})bcd+(1-\zeta_{3}^{2})acd+(1-\zeta_{3})bce+(1-\zeta_{3}^{2})(1-\zeta_{3})ace\right)$
$\displaystyle=3a^{2}c^{2}d^{2}+3b^{2}c^{2}d^{2}+6abc^{2}d^{2}+9a^{2}c^{2}e^{2}+3b^{2}c^{2}e^{2}+9abc^{2}e^{2}+9a^{2}c^{2}de+3b^{2}c^{2}de+12abc^{2}de$

which matches $\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$ from Example 3.2.

###  3.3. Triangularization

In this section we build up the machinery to prove our main result, Theorem
1.3.

For ease of notation, we will first fix an ordering on the basis of
$\tilde{\Gamma}$. Most of the time we won’t assume the covering graph to be
regular, and using the notations in Section 2.7, we order the basis vectors of
$\tilde{\Gamma}$ in a colexicographic order, i.e.
$v_{1}^{1}<\cdots<v_{n}^{1}<v_{1}^{2}<\cdots<v_{n}^{2}<\cdots<v_{1}^{k}<\cdots<v_{n}^{k}$.

######  Definition 3.5.

Let $\\{v_{1},\cdots,v_{n}\\}$ be the set of vertices of our graph $\Gamma$,
let $\tilde{\Gamma}$ be a $k$-fold cover of $\Gamma$, where vertex $v_{i}$ is
lifted to $v_{i}^{1},\cdots,v_{i}^{k}$. Define $n(k-1)\times n(k-1)$ matrices
$D$ and $A$ with basis
$v_{1}^{2},\cdots,v_{n}^{2},v_{1}^{3},\cdots,v_{n}^{3},\cdots,v_{1}^{k},\cdots,v_{n}^{k}$
as follows.

$A[v_{i}^{t},v_{j}^{r}]=\sum_{e=(v_{i}^{t},v_{j}^{r})}\wt(e)-\sum_{e=(v_{j}^{r},v_{i}^{1})}\wt(e)$
$D[v_{i}^{t},v_{i}^{t}]=\sum_{e\in E_{s}(v_{i}^{t})}\wt(e)$

for $1<t,r\leq k.$ Finally, we define

$[\mathscr{L}(\Gamma)]_{\BZ[E]}:=D-A.$

In the case of regular covers, we can choose an ordering $g_{1},\ldots,g_{k}$
on the group elements, and use the order
$v_{1}^{g_{1}}<\cdots<v_{n}^{g_{1}}<v_{1}^{g_{2}}<\cdots<v_{n}^{g_{2}}<\cdots<v_{1}^{g_{k}}<\cdots<v_{n}^{g_{k}}$
on the basis vectors of $\tilde{\Gamma}$. If $g_{1}$ is the identity element,
Definition 3.5 gives the $\BZ$-linearization of the voltage Laplacian. Note
that in the case of non-regular covers, the matrix cannot be interpreted as
the $\BZ$-linearization of a voltage Laplacian.

With this definition in hand, we remind the reader of Theorem 1.3:

Let $\Gamma=(V,E,\wt)$ be an edge-weighted multigraph, and let
$\tilde{\Gamma}$ be a $k$-fold covering graph of $\Gamma$. Then for any vertex
$v$ of $\Gamma$ and any lift $\tilde{v}$ of $v$, we have

$\displaystyle\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}=\frac{1}{k}{\det}[\mathscr{L}(\Gamma)]_{\BZ[E]}$

with $[\mathscr{L}(\Gamma)]_{\BZ[E]}$ given by Definition 3.5.

To prove this theorem, we carefully apply a change of basis to the Laplacian
matrix of $\tilde{\Gamma}$.

######  Lemma 3.6 (Triangularization Lemma).

Let $\Gamma$ be as in Theorem 1.3. Write $L(\tilde{\Gamma})$ with basis
vectors ordered as above. Let

$\displaystyle S=\begin{bmatrix}\id_{n}&\id_{n}&\dots&\id_{n}\\\ 0_{n}&&&\\\
\vdots&&\id_{(k-1)n}&\\\ 0_{n}&&&\end{bmatrix}$

Then the change of basis given by $S$ yields the following block
triangularization of $L(\tilde{\Gamma})$:

(2) $\displaystyle SL(\tilde{\Gamma})S^{-1}=\begin{bmatrix}L(\Gamma)&0\\\
*&\left[\mathscr{L}(\Gamma)\right]_{\BZ[E]}\end{bmatrix}$

######  Proof 3.7.

Let $\beta_{i}=\sum_{j\in[k]}v_{i}^{j}$. Conjugation by $S$ corresponds to a
change of basis that maps $v_{i}^{1}\mapsto\beta_{i}$ and $v_{i}^{j}\mapsto
v_{i}^{j}$ when $j\neq 1$. Therefore, all we need to do is examine the action
of the linear transformation corresponding to the matrix $L(\tilde{\Gamma})$
on this new basis. Denote this linear transformation as $T$.

First, we show that

$\displaystyle T(\beta_{i})=\sum_{j=1}^{n}\ell_{ij}\beta_{j}$

where $\ell_{ij}$ is the $(i,j)$-entry of $L(\Gamma)$. To see this, consider
the $k$ rows of $L(\tilde{\Gamma})$ corresponding to the fiber
$\\{v_{i}^{r}\\}_{r\in[k]}$ of $v_{i}$. The sum of these rows is equal to
$T(\beta_{i})$, expressed as a row vector with respect to the standard basis.
Choose a column of $L(\tilde{\Gamma})$ corresponding to $v_{j}^{r}$. The
entries of this column in the previously mentioned rows correspond (with
negative sign) to edges to $v_{j}^{r}$ from some element in the fiber of
$v_{i}$. Since there should be one of these for each edge $(v_{i},v_{j})$ in
$\Gamma$, the sum of these values is $\ell_{ij}$. Now choose the column of
$L(\tilde{\Gamma})$ corresponding to $v_{i}^{r}$. The entries of this column
in the previously mentioned rows on the off-diagonal correspond (with negative
sign) to edges to $v_{i}^{r}$ from some element in the fiber of $v_{i}$ other
than $v_{i}^{r}$. The diagonal entry of the column corresponds (with negative
sign) to edges from $v_{i}^{r}$ to itself as well as (with positive sign) all
edges out of $v_{i}^{r}$. Adding these values, we get $\ell_{ii}$, since there
is one edge into $v_{i}^{r}$ from a vertex in the fiber of $v_{i}$ for each
edge from $v_{i}$ to itself and one edge out of $v_{i}^{r}$ for each edge out
of $v_{i}$. Thus, the sum of the $n$ rows of $L(\tilde{\Gamma})$ corresponding
to the fiber $\\{v_{i}^{r}\\}_{r\in[k]}$ is precisely

$\displaystyle
T(\beta_{i})=\sum_{j=1}^{n}\sum_{r\in[k]}\ell_{ij}v_{j}^{r}=\sum_{i=1}^{n}\ell_{ij}\beta_{j}$

as desired. Therefore, the upper-left and upper-right blocks of (2) are
correct.

The effect of our change of basis on the lower-right $(k-1)n\times(k-1)n$
block of $L(\tilde{\Gamma})$ is to subtract the $i$-th column of
$L(\tilde{\Gamma})$, for $i\in[n]$, from columns $i+n,i+2n,\dots,i+(k-1)n$.
This exactly follows the construction of $[\mathscr{L}(\Gamma)]_{\BZ[E]}$ from
Definition 3.5.

######  Example 3.8.

We illustrate Lemma 3.6 using Example 2.10, taking $\Gamma$ to be the graph in
Figure 3 and $\tilde{\Gamma}$ to be its corresponding derived graph as in
Figure 4. The Laplacian matrix of $\tilde{\Gamma}$ is

$\displaystyle L(\tilde{\Gamma})=\begin{bmatrix}a+b&-b&0&-a&0&0&0&0&0\\\
0&c&0&0&0&0&0&0&-c\\\ 0&-e&d+e&0&0&0&-d&0&0\\\ 0&0&0&a+b&-b&0&-a&0&0\\\
0&0&-c&0&c&0&0&0&0\\\ -d&0&0&0&-e&d+e&0&0&0\\\ -a&0&0&0&0&0&a+b&-b&0\\\
0&0&0&0&0-c&0&c&0\\\ 0&0&0&-d&0&0&0&-e&d+e\end{bmatrix}.$

Then letting $S$ be the $9\times 9$ change of basis matrix defined in the
lemma, we have

$\displaystyle SL(\tilde{\Gamma})S^{-1}=\begin{bmatrix}b&-b&0&0&0&0&0&0&0\\\
0&c&-c&0&0&0&0&0&0\\\ -d&-e&d+e&0&0&0&0&0&0\\\ 0&0&0&a+b&-b&0&-a&0&0\\\
0&0&-c&0&c&c&0&0&c\\\ -d&0&0&d&-e&d+e&d&0&0\\\ -a&0&0&a&0&0&2a+b&-b&0\\\
0&0&0&0&0&-c&0&c&0\\\ 0&0&0&-d&0&0&0&-e&d+e\end{bmatrix}.$

Recall from Example 2.5 that

$\displaystyle L(\Gamma)=\begin{bmatrix}b&-b&0\\\ 0&c&-c\\\
-d&-e&d+e\end{bmatrix},$

and recall from Example 3.2 that

$\displaystyle[\mathscr{L}(\Gamma)]_{\BZ[E]}=\begin{bmatrix}a+b&-b&0&-a&0&0\\\
0&c&c&0&0&c\\\ d&-e&d+e&d&0&0\\\ a&0&0&2a+b&-b&0\\\ 0&0&-c&0&c&0\\\
-d&0&0&0&-e&d+e\end{bmatrix}.$

We indeed find that $L(\Gamma)$ appears as the upper-left block of
$SL(\tilde{\Gamma})S^{-1}$ and that $[\mathscr{L}(\Gamma)]_{\BZ[E]}$ appears
as the lower-right block of $SL(\tilde{\Gamma})S^{-1}$, as predicted by the
lemma. Note also the upper-right block of zeros in $SL(\tilde{\Gamma})S^{-1}$.

We would like to make the following statement:

(3)
$\displaystyle\det[SL(\tilde{\Gamma})S^{-1}]_{i}^{i}=\det[L(\tilde{\Gamma})]_{i}^{i}$

for any $i\in[k]$. This would allow us to obtain an expression for
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ from Lemma 3.6, since
the left-hand side of 3 is

$\det[L({\Gamma})]_{i}^{i}\det[\mathscr{L}(\Gamma)]_{\BZ[E]}=A_{v_{i}}(\Gamma)\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$

and the right-hand side is

$\det[L(\tilde{\Gamma})]_{i}^{i}=A_{\tilde{v}_{i}^{1}}(\tilde{\Gamma}).$

Unfortunately, Equation 3 is _not true_ as stated. In general, a given minor
does not remain invariant under change of basis. However, Equation 3 turns out
to be _nearly true_ in that it is only off by a factor of $k$. Our goal is to
instead prove the correct statement

$\displaystyle\det[SL(\tilde{\Gamma})S^{-1}]_{i}^{i}=k\cdot\det[L(\tilde{\Gamma})]_{i}^{i}.$

To this end, we define $U=SL(\tilde{\Gamma})S^{-1}$. This is the matrix that
we will use to connect the two sides of Theorem 1.3. Without loss of
generality, assume that we want to root our arborescences of $\Gamma$ at
vertex $v_{1}$ and our arborescences of $\tilde{\Gamma}$ at vertex
$v_{1}^{1}$. Then the following result is immediate from Lemma 3.6 and Theorem
2.4:

######  Corollary 3.9.

$\det[U_{1}^{1}]=A_{v_{1}}(\Gamma)\det[\mathscr{L}(\Gamma)]_{\BZ[E]}.$

To complete the proof of Theorem 1.3, we need to show that

$\displaystyle\det[U_{1}^{1}]=k\cdot\det[L_{1}^{1}(\tilde{\Gamma})].$

###  3.4. The two-step change of basis

We will show the above equality by factoring $S$ as $QP$ for some matrices $Q$
and $P$ specified in Section 3.5. This means conjugation by $S$ is the same as
conjugation by $P$ and then conjugation by $Q$. In this section we will prove
two lemmas that will tell us how conjugation by each of these matrices affects
minors.

######  Lemma 3.10.

Let $L$ be the Laplacian matrix of some graph $\Gamma=(V,E,\wt)$. Fix a basis
vector $v_{i}$, and let $P$ be the change of basis matrix that maps
$v_{i}\mapsto\sum_{j=1}^{n}\alpha_{j}v_{j}$ with $\alpha_{i}\neq 0$. That is,
$P$ is the identity matrix but with $\alpha_{j}$ in entry $(i,j)$ for each
$j\in J$. Then

$\displaystyle\det[(PLP^{-1})_{i}^{i}]=\left(\sum_{j=1}^{n}\frac{\alpha_{j}}{\alpha_{i}}\right)A_{v_{i}}(\Gamma)$

######  Proof 3.11.

First note that we need $\alpha_{i}\neq 0$ in order for $P$ to be invertible.
Otherwise, column $i$ would be all 0’s. If $\alpha_{j}=0$ for all $j\neq i$,
then the statement holds trivially, because $(PLP^{-1})_{i}^{i}=L_{i}^{i}$ in
this case. So, we can assume there is some $j\neq i$ such that $\alpha_{j}\neq
0$.

Without loss of generality, let $i=1$ and $\alpha_{2}\neq 0$. We can see that
$P^{-1}$ is the identity matrix with $\frac{1}{\alpha_{1}}$ in the (1,1) entry
and $\frac{-\alpha_{i}}{\alpha_{1}}$ in the $(1,i)$ entry.
$L(\tilde{\Gamma})P^{-1}$ differs from $L(\tilde{\Gamma})$ in that the $i$th
column of $L(\tilde{\Gamma})P^{-1}$ is the $i$th column of $L(\tilde{\Gamma})$
with $\frac{\alpha_{i}}{\alpha_{1}}$ times the first column of
$L(\tilde{\Gamma})$ subtracted from it. $PL(\tilde{\Gamma})P^{-1}$ differs
from $L(\tilde{\Gamma})P^{-1}$ only in the first row. However, since we are
finding the determinant of $PL(\tilde{\Gamma})P^{-1}$ with the first row and
column removed, we are only interested in the lower-right hand
$(n-1)\times(n-1)$ submatrix and can ignore this operation.

Notice that $P$ can be factored as $P_{n}P_{n-1}...P_{2}$ where $P_{2}$ is the
identity but with $\alpha_{1}$ in the $(1,1)$ entry and $\alpha_{2}$ in the
$(1,2)$ entry and the rest of the $P_{j}$’s are the identity but with
$\alpha_{j}$ in the $(1,j)$ entry. This also gives a factorization for
$P^{-1}$. We will first focus on $P_{2}LP_{2}^{-1}$.

We may interpret $(P_{2}LP_{2}^{-1})_{1}^{1}$ as a submatrix of the Laplacian
of a different graph, which we will denote as $\Gamma^{(2)}$. We construct
$\Gamma^{(2)}$ as follows: the vertices of $\Gamma^{(2)}$ are
$v_{1}^{(2)},...,v_{n}^{(2)}$. If there is an edge $v_{r}\to v_{s}$ in
$\Gamma$, then there is an edge $v_{r}^{(2)}\to v_{s}^{(2)}$ in
$\Gamma^{(2)}$, so $\Gamma^{(2)}$ contains $\Gamma$ as a subgraph. For each
edge $e=(v_{2},v_{1})\in\Gamma$, we add an additional edge
$(v_{2}^{(2)},v_{1}^{(2)})$ to $\Gamma^{(2)}$ with weight
$\frac{\alpha_{2}}{\alpha_{1}}\wt(e)$; we call this an edge of type 1.
Furthermore, for each such $e=(v_{i},v_{1})\in\Gamma$ where $i\neq 1,2$, we
add the edge $(v_{i}^{(2)},v_{2}^{(2)})$ to $\Gamma^{(2)}$ with weight
$\frac{-\alpha_{2}}{\alpha_{1}}\wt(e)$ and the edge
$(v_{i}^{(2)},v_{1}^{(2)})$ with weight $\frac{\alpha_{2}}{\alpha_{1}}\wt(e)$.
The first of these edges will be called an edge of type 2 and the second an
edge of type 3.

We can see that $L(\Gamma^{(2)})$ is the same as $L(\Gamma)$ except that
(aside from the first row, which remains unchanged)
$\frac{\alpha_{2}}{\alpha_{1}}$ times the first column is subtracted from
first column and added to the second column.
$L_{1}^{1}(\Gamma^{(2)})=(P_{2}LP_{2}^{-1})_{1}^{1}$, so
$\det[(P_{2}LP_{2}^{-1})_{1}^{1}]$ counts the arborescences of $\Gamma^{(2)}$
rooted at $v_{1}^{(2)}$.

We will divide the arborescences of $\Gamma^{(2)}$ into four categories (See
Figure 6).

  1. (1)

Arborescences that do not contain any type 1, type 2, or type 3 edges. The
weighted sum of these arborescences is counted by $A_{v_{1}}(\Gamma)$ because
these are exactly the arborescences that use only edges in the subgraph
$\Gamma$ of $\Gamma^{(2)}$.

  2. (2)

Arborescences that contain a type 2 edge paired with arborescences that differ
from these by replacing the type 2 edge with a type 3 edge of the same weight
with opposite sign. For every type 2 edge, there is a type 3 edge of the same
weight with opposite sign. This means that for every arborescence that
contains a type 2 edge, there is an arborescence that is the same, except
instead of the type 2 edge it has a type 3 edge of the same weight with
opposite sign. The weights of these arborescences cancel out, so the weighted
sum of all of these arborescences is 0.

  3. (3)

Arborescences that contain a type 1 edge not counted in the previous category
(2). We claim that in such an arborescence, every edge lies in the subgraph
$\Gamma$ except for the unique type $1$ edge. If such an arborescence
contained an edge of type $2$, then since vertex $2^{(2)}$ flows directly to
the root the edge of type $2$ could be replaced by its corresponding type $3$
edge and still yield a valid arborescence; the same holds if we start with an
edge of type $3$. Thus, arborescences in this category correspond to
arborescences in $\Gamma$ where the edge out of 2 goes directly to 1. So, they
contribute $\frac{\alpha_{2}}{\alpha_{1}}$ times the weight of such
arborescences in $\Gamma$.

  4. (4)

Arborescences that contain an edge of type 3 that are not counted in category
(2) either. These are arborescences where removing the edge
$e=(v_{j}^{(2)},v_{1}^{(2)})$ of type 3 and replacing it with the
corresponding edge $e^{\prime}=(v_{j}^{(2)},v_{2}^{(2)})$ of type 2 does not
give an arborescence. This only happens if adding $e^{\prime}$ would create a
cycle, so we conclude that $v_{j}^{(2)}$ lies downstream from $v_{2}^{(2)}$ in
the arborescence flow. This guarantees that there exists only one type $3$
edge—if we have one type $3$ edge out of $v_{j}^{(2)}$ and another one out of
$v_{j^{\prime}}^{(2)}$, then both of these vertices lie downstream of
$v_{2}^{(2)}$ but both lead directly to $v_{1}^{(2)}$, which is a
contradiction. Furthermore, such an arborescence cannot contain an edge of
type $1$—this would immediately contradict vertex $v_{2}^{(2)}$ lying upstream
of $v_{j}^{(2)}$—or an edge of type $2$, since type $2$ edges can always be
replaced by their corresponding type $3$ edge and still yield a valid
arborescence, which would again land us in category (2).

We conclude that the only “added” edge in this arborescence is $e$ itself.
Therefore, summing over $j\neq 1,2$ we see that these arborescences in this
category correspond bijectively to arborescences in $\Gamma$ where the edge
out of $v_{2}$ does not go to $v_{1}$. This means that in our sum, they
contribute $\frac{\alpha_{2}}{\alpha_{1}}$ times the weight of such
arborescences in $\Gamma$.

The last two categories combine to contribute
$\frac{\alpha_{2}}{\alpha_{1}}A_{v_{1}}(\Gamma)$ to the arborescence count
$A_{v_{1}^{(2)}}\Gamma^{(2)}$. Adding the weighted sums of the arborescences
in these four categories, we find

$A_{v_{1}^{(2)}}(\Gamma^{(2)})=A_{v_{1}}(\Gamma)+\frac{\alpha_{2}}{\alpha_{1}}A_{v_{1}}(\Gamma)=\left(\frac{\alpha_{1}+\alpha_{2}}{\alpha_{1}}\right)A_{v_{1}}(\Gamma).$

From here, we proceed by induction—essentially, all we need to do is prove
that continuing to iterate the previous construction over vertices other than
$v_{2}$ continues to work the way we want. For $3\leq k\leq n$, we will
construct $\Gamma^{(k)}$ from $\Gamma^{(k-1)}$ in the same way we constructed
$\Gamma^{(2)}$ from $\Gamma$. However, here the weights on our new edges will
have a factor of $\frac{\alpha_{k}}{\sum_{j=1}^{k-1}\alpha_{j}}$ rather than
$\frac{\alpha_{2}}{\alpha_{1}}$. We will show that $L(\Gamma^{(k)})$ is
$L(\Gamma)$ except that (aside from the first row, which remains unchanged)
$\frac{\alpha_{j}}{\alpha_{1}}$ times the first column of $L(\Gamma)$ is
subtracted from first column and added to the $j$th column for $2\leq j\leq
k$. Note that this means that
$L_{1}^{1}(\Gamma^{(k)})=(P_{k}P_{k-1}...P_{2}LP_{2}^{-1}...P_{k-1}^{-1}P_{k}^{-1})_{1}^{1}$,
so $\det[(P_{k}P_{k-1}...P_{2}LP_{2}^{-1}...P_{k-1}^{-1}P_{k}^{-1})_{1}^{1}]$
counts the arborescences of $\Gamma^{(k)}$ rooted at $v_{1}^{(k)}$. We will
also show that

$A_{v_{1}^{(k)}}(\Gamma^{(k)})=\left(\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{1}}\right)A_{v_{1}}(\Gamma).$

We begin with the Laplacian. We can see that $L(\Gamma^{(k)})$ is
$L(\Gamma^{(k-1)})$ except that (aside from the first row, which remains
unchanged) $\frac{\alpha_{k}}{\sum_{j=1}^{k-1}\alpha_{j}}$ times the first
column of $L(\Gamma^{(k-1)})$ is subtracted from first column and added to the
$k$th column. By our inductive hypothesis,
$\frac{\alpha_{k}}{\sum_{j=1}^{k-1}\alpha_{j}}$ times the first column of
$L(\Gamma^{(k-1)})$ is
$\left(\frac{\alpha_{k}}{\sum_{j=1}^{k-1}\alpha_{j}}\right)\left(\frac{\sum_{j=1}^{k-1}\alpha_{j}}{\alpha_{1}}\right)=\frac{\alpha_{k}}{\alpha_{1}}$
times the first column of $L(\Gamma)$. This shows that $L(\Gamma^{(k)})$ is
what we want.

Now we turn to the arborescences. The same method of counting arborescences in
$\Gamma^{(2)}$ from arborescences in $\Gamma$ applies for counting
arborescences in $\Gamma^{(k)}$ from $\Gamma^{(k-1)}$. This means

$A_{v_{1}^{(k)}}(\Gamma^{(k)})=A_{v_{1}^{(k-1)}}(\Gamma^{(k-1)})+\frac{\alpha_{k}}{\sum_{j=1}^{k-1}\alpha_{j}}A_{v_{1}^{(k-1)}}(\Gamma^{(k-1)}),$

which gives us what we want by the inductive hypothesis.

Thus, we have shown that

$\det[(PLP^{-1})_{1}^{1}]=\det[(P_{n}P_{n-1}...P_{2}LP_{2}^{-1}...P_{n-1}^{-1}P_{n}^{-1})_{1}^{1}]=\left(\sum_{j=1}^{n}\frac{\alpha_{j}}{\alpha_{1}}\right)A_{v_{1}}(\Gamma).$

$L(\Gamma)=\begin{bmatrix}a+b&-a&0&-b\\\ -c&c+d&0&-d\\\ -e&-g&e+g&0\\\
0&0&-f&f\end{bmatrix},\;\;\;\;\;\;P_{2}=\begin{bmatrix}1&1&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\end{bmatrix}$

$P_{2}L(\Gamma)P_{2}^{-1}=\begin{bmatrix}a+b-c&-2a-b+2c+d&0&-b-d\\\
-c&2c+d&0&-d\\\ -e&-g+e&g+e&0\\\ 0&0&-f&f\end{bmatrix}$

Figure 5. A Laplacian matrix before and after applying the change of basis
$P_{2}$ with $\alpha_{1}=\alpha_{2}=1$. Note that $(P_{2}LP_{2}^{-1})_{1}^{1}$
matches the corresponding submatrix of the Laplacian of $\Gamma^{(2)}$ (see
Figure 6).

$3$$4$$2$$1$$3$$4$$2$$1$$a$$b$$c$$d$$e$$f$$g$$a$$b$$c$$c$$d$$e$$e$$f$$g$$-e$A
graph $\Gamma$ and the corresponding graph $\Gamma^{(2)}$.

$1$$2$$4$$3$$d$$e$$f$An arborescence of type 1.

$3$$4$$2$$1$$3$$4$$2$$1$$c$$e$$f$$c$$-e$$f$A pair of arborescences of type 2.

$3$$4$$2$$1$$c$$e$$f$An arborescence of type 3.

$3$$4$$2$$1$$e$$d$$f$An arborescence of type 4.

Figure 6. Types of arborescences for $\Gamma^{(2)}$ with
$\alpha_{1}=\alpha_{2}=1$.

Here is the next lemma we need:

######  Lemma 3.12.

Let $R$ be a commutative ring and let $M\in\mathrm{Mat}_{n}(R)$. Let $Q\in
GL_{n}(R)$ such that the $i$-th row and column are each the $i$-th unit
vector. Then

$\displaystyle\det[(QMQ^{-1})_{i}^{i}]=\det[M_{i}^{i}]$

In other words, the minor of $M$ corresponding to removing the $i$-th row and
column is invariant under base change by $Q$.

######  Proof 3.13.

Without loss of generality $i=1$. Write

$\displaystyle Q=\begin{pmatrix}1&0\\\
0&Q_{1}^{1}\end{pmatrix},\;\;\;\;M=\begin{pmatrix}*&*\\\
*&M_{1}^{1}\end{pmatrix}$

Thus,

$\displaystyle QMQ^{-1}=\begin{pmatrix}*&*\\\
*&(Q_{1}^{1})(M_{1}^{1})(Q_{1}^{1})^{-1}\end{pmatrix}.$

Then since

$\displaystyle\det[(QMQ^{-1})_{i}^{i}]$
$\displaystyle=\det[((Q_{1}^{1})(M_{1}^{1})(Q_{1}^{1})^{-1})]$
$\displaystyle=\det[(M_{1}^{1})]$ $\displaystyle=:\det[M_{1}^{1}],$

we conclude that the desired minor is the same as the corresponding minor of
$M$.

###  3.5. Proof of Theorem 1.3

######  Proof 3.14.

Let $P$ be the change of basis that maps
$v_{1}^{1}\mapsto\beta_{1}:=\sum_{s\in[k]}v_{1}^{s}$, and let $Q$ be the
change of basis that maps $v_{i}^{1}\mapsto\sum_{r\in[k]}v_{i}^{r}$ for $i>1$.
Note that $P$ satisfies the hypotheses for Lemma 3.10 with $i=1$ and $Q$
satisfies the hypotheses of Lemma 3.12 with $i=1$. Letting $S$ be the matrix
from Lemma 3.6, we have $S=QP$. Thus, by Lemmas 3.10 and 3.12,

$\displaystyle\det[U_{1}^{1}]$
$\displaystyle=\det[(QPL(\tilde{\Gamma})P^{-1}Q^{-1})_{1}^{1}]$
$\displaystyle=\det[(PL(\tilde{\Gamma})P^{-1})_{1}^{1}]$
$\displaystyle=kA_{v_{1}^{1}}(\tilde{\Gamma})$

However, from Corollary 3.9 we know that

$\displaystyle\det[U_{1}^{1}]$
$\displaystyle=A_{v_{1}}(\Gamma)\det[\mathscr{L}(\Gamma)]_{\BZ[E]}.$

Therefore,

$\displaystyle
kA_{v_{1}^{1}}(\tilde{\Gamma})=A_{v_{1}}(\Gamma)\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$

as desired.

##  4\. Vector fields and the voltage Laplacian

In this section, we discuss the connection between the voltage Laplacian and
vector fields on voltage graphs, and its implications for positivity in the
$2$-fold cover case.

###  4.1. Negative Vector Fields

######  Definition 4.1.

A _vector field_ $\gamma$ of a directed graph $\Gamma$ is a subgraph of
$\Gamma$ such that every vertex of $\gamma$ has outdegree $1$ in $\Gamma$. As
with arborescences, we define the _weight_ of a vector field to be the product
of its edge weights, that is

$\text{wt}(\gamma):=\prod_{e\in\gamma}\wt(e).$

Note that $\wt(\gamma)$ is a degree $n$ monomial with respect to the edge
weights of $\Gamma$. Write $C(\gamma)$ for the set of cycles in a vector field
$\gamma$, of which there is exactly one in each connected component. If $G$ is
abelian, and if $c$ is a cycle of $\gamma$ then we define the voltage of $c$
as $\nu(c):=\prod_{e\in c}\nu(e)$; this product is well-defined when $G$ is
abelian.

The determinant of $\mathscr{L}(\Gamma)$ counts vector fields of $\Gamma$ in
the following way:

######  Theorem 4.2 (Chaiken).

Let $G$ be an abelian group, and let $\Gamma$ be an edge-weighted $G$-voltage
graph. Then

$\displaystyle\sum_{\gamma\subseteq\Gamma}\left[\wt(\gamma)\prod_{c\in
C(\gamma)}(1-\nu(c))\right]=\det[\mathscr{L}(\Gamma)]$

where the sum ranges over all vector fields $\gamma$ of $\Gamma$.

######  Example 4.3.

Let $\Gamma$ be the $\BZ/3\BZ$-voltage graph of example 2.10. There are four
distinct vector fields of $\Gamma$ (see Figure 7).

$1$23$(b,1)$$(d,g^{2})$$(c,g^{2})$

$1$23$(a,g)$$(d,g^{2})$$(c,g^{2})$

$1$23$(b,1)$$(e,1)$$(c,g^{2})$

$1$23$(a,g)$$(e,1)$$(c,g^{2})$

Figure 7. The four vector fields of $\Gamma$

The first three of these vector fields contain one cycle; from left to right,
these unique cycles have weights $\zeta_{3},\zeta_{3},$ and $\zeta_{3}^{2}$.
The rightmost vector field has two cycles, one with weight $\zeta$ and the
other of weight $\zeta^{2}$. From Example 2.17, we have

$\displaystyle\det[\mathscr{L}(\Gamma)]=(1-\zeta_{3})bcd+(1-\zeta_{3})acd+(1-\zeta_{3}^{2})bce+(1-\zeta_{3})(1-\zeta_{3}^{2})ace$

The four terms in this expression correspond to the four vector fields of
$\Gamma$ as described by the theorem.

We briefly point out the special case $G=\BZ/2\BZ$, which is especially nice
because the coefficients in Theorem 4.2 are nonnegative integers.

######  Definition 4.4.

Suppose that $\Gamma$ is a $\BZ/2\BZ$-voltage graph, also called a _signed
graph_. A vector field $\gamma$ of $\Gamma$ is a _negative vector field_ if
every cycle $c$ of $\gamma$ has an odd number of negative edges, so that
$\nu(c)=-1$.

Denote the set of negative vector fields of signed graph $\Gamma$ by
$\mathcal{N}(\Gamma)$. Then Theorem 4.2 may be written as:

######  Corollary 4.5.

$\displaystyle\sum_{\gamma\in\mathcal{N}(\Gamma)}2^{\\#C(\gamma)}\wt(\gamma)=\det[\mathscr{L}(\Gamma)]$

Corollary 4.5 along with Corollary 1.5 has an immediate further corollary:

######  Corollary 4.6.

If $\tilde{\Gamma}$ is a $2-$fold regular cover of $\Gamma$, then the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ has positive integer
coefficients.

Positivity for general covers is still unknown; see Conjecture 1.8.

###  4.2. Proofs of Theorem 4.2

We now present two proofs of Theorem 4.2. The first is new, and the second is
essentially due to Chaiken.

The first proof proceeds by deletion-contraction, and requires the following
lemma.

######  Lemma 4.7.

Let $\Gamma$ be as in Theorem 4.2 with voltage function $\nu:E\to$, let $v$ be
any vertex of $\Gamma$, and let $g\in G$. We define a new voltage function
$\nu_{v,g}$ given by

$\displaystyle\nu_{v,g}(e)$
$\displaystyle=\begin{cases}g\nu(e):&\mathrm{if}\;e\in E_{s}(v),e\nin
E_{t}(v)\\\ g^{-1}\nu(e):&\mathrm{if}\;e\in E_{t}(v),e\nin E_{s}(v)\\\
\nu(e):&\mathrm{otherwise}\end{cases}$

Then:

  1. (a)

For any cycle $c$ of $\Gamma$, we have $\nu(c)=\nu_{v,g}(c)$.

  2. (b)

The determinant of the voltage Laplacian of $\Gamma$ with respect to the
voltage $\nu$ is equal to the determinant of the voltage Laplacian of $\Gamma$
with respect to $\nu_{v,g}$. That is,

$\displaystyle\det[\mathscr{L}(V,E,\wt,\nu)]=\det[\mathscr{L}(V,E,\wt,\nu_{v,g})]$

######  Proof 4.8.

  1. (a)

If $c$ does not contain the vertex $v$, or if $c$ is a loop at $v$, then the
voltages of all edges in $c$ remain unchanged. Otherwise, $c$ contains exactly
one ingoing edge $e$ of $v$ and one outgoing edge $f$ of $v$, so that

$\displaystyle\nu_{v,h}(c)$
$\displaystyle=\frac{\nu(c)}{\nu(e)\nu(f)}[g\nu(e)][g^{-1}\nu(f)]$
$\displaystyle=\nu(c)$

as desired.

  2. (b)

The matrix $\mathscr{L}(V,E,\wt,\nu)$ may be transformed into the matrix
$\mathscr{L}(V,E,\wt,\nu_{v,g})$ by multiplying the row corresponding to $v$
by $g$ and multiplying the column corresponding to $v$ by $g^{-1}$, so the
determinant remains unchanged.

This lemma will allow us some freedom to change the voltage of $\Gamma$ as
needed in the following proof.

######  Proof 4.9 (First proof of Theorem 4.2).

Denote the left-hand side of the theorem as

$\displaystyle\Omega(\Gamma):=\sum_{\gamma\subseteq\Gamma}\left[\wt(\gamma)\prod_{c\in
C(\gamma)}(1-\nu(c))\right]$

We proceed by deletion-contraction. The base case is when the only edges of
$\Gamma$ are loops. When this happens, $\mathscr{L}(\Gamma)$ is diagonal, with

$\displaystyle\ell_{ii}=\sum_{e=(v_{i},v_{i})\in E}(1-\nu(e))\wt(e).$

Thus we have

$\displaystyle\det[\mathscr{L}(\Gamma)]$
$\displaystyle=\prod_{i=1}^{n}\left(\sum_{\begin{subarray}{c}e=(v_{i},v_{i})\in
E\end{subarray}}\left[1-\nu(e)\right]\wt(e)\right)$

If we expand the product above, each term will correspond to a unique
combination of one loop per vertex of $\Gamma$. But such combinations are
precisely the vector fields of $\Gamma$, so we obtain

$\displaystyle\det[\mathscr{L}(\Gamma)]=\Omega(\Gamma)$

For the inductive step, assume that there exists at least one edge $e$ between
distinct vertices, and assume that the proposition holds for graphs with fewer
non-loop edges than $\Gamma$. Using the lemma, we may change the voltage of
$\Gamma$ so that $e$ has voltage $1$ without changing either $\Omega(\Gamma)$
or $\det[\mathscr{L}(\Gamma)]$. Without loss of generality, let $v_{1}=e_{s}$
and $v_{2}=e_{t}$.

If $\gamma$ is a vector field of $\Gamma$, then $\gamma$ either contains $e$
or it does not. In the latter case, $\gamma$ is also a vector field of
$\Gamma\backslash e$. Clearly all such $\gamma$ arise uniquely from a vector
field of $\Gamma\backslash e$. Therefore, there is a weight-preserving
bijection between the vector fields of $\Gamma$ not containing $e$ and the
vector fields of $\Gamma\backslash e$.

Otherwise, if $e\in\gamma$, then no other edge of the form $(v_{1},v_{j})$ is
in $\gamma$. We define a special type of contraction: let
$\Gamma/_{1}e:=(\Gamma/e)\backslash E_{s}(v_{1})$. That is, we contract along
$e$, and delete all other edges originally in $E_{s}(v_{1})$. Note that the
contraction process merges vertices $v_{1}$ and $v_{2}$ into a “supervertex,”
which we denote $v_{12}$.

Then the vector field $\gamma$ descends uniquely to a vector field on
$\Gamma/_{1}e$. Every vector field in $\Gamma/_{1}e$ corresponds uniquely to a
vector field of $\Gamma$ containing $e$, obtained by letting the unique edge
coming out the supervertex $v_{12}$ in be the unique edge coming out of the
vertex $v_{2}$ in $\gamma$, and letting $e$ be the unique edge with source at
$v_{1}$ in $\gamma$. This inverse map shows that the vector fields of $\Gamma$
containing $e$ are in bijection with the vector fields of $\Gamma/_{1}e$. This
bijection is weight-preserving up to a factor of $\wt(e)$. Finally, note that
$\gamma$ and its contraction have the same number of cycles, with the same
voltages. If a cycle contains $e$ in $\gamma$, then that cycle is made one
edge shorter in , but still has positive length since $e$ is assumed to not be
a loop. If $c$ is a cycle containing $e$ in $\Gamma$, then because $e$ has
voltage $1$, the cycle voltage $\nu(c/e)$ of the contracted version of $c$ is
equal to the cycle voltage before contraction. Thus, we may write

$\displaystyle\Omega(\Gamma)=\Omega(\Gamma\backslash
e)+\wt(e)\Omega(\Gamma/_{1}e)$

By the inductive hypothesis, since $\Gamma\backslash e$ and $\Gamma/_{1}e$
have strictly fewer non-loop edges than $\Gamma$, we have

$\displaystyle\Omega(\Gamma\backslash
e)+\wt(e)\Omega(\Gamma/_{1}e)=\det[\mathscr{L}(\Gamma\backslash
e)]+\wt(e)\det[\mathscr{L}(\Gamma/_{1}e)]$

Note that $\mathscr{L}(\Gamma\backslash e)$ is equal to $\mathscr{L}(\Gamma)$
with $\wt(e)$ deleted from both the $1,1$\- and $1,2$-entries. Therefore, via
expansion by minors, we obtain

(4) $\displaystyle\det[\mathscr{L}(\Gamma\backslash
e)]+\wt(e)\det[\mathscr{L}_{1}^{1}(\Gamma)]+\wt(e)\det[\mathscr{L}_{1}^{2}(\Gamma)]=\det[\mathscr{L}(\Gamma)]$

where $\mathscr{L}_{i}^{j}(\Gamma)$ is the submatrix of $\mathscr{L}(\Gamma)$
obtained by removing the $i$-th row and the $j$-th column.

To construct $\mathscr{L}(\Gamma/_{1}e)$ from $\mathscr{L}(\Gamma)$, we
disregard the first row of $\mathscr{L}(\Gamma)$, since the special
contraction $\Gamma/_{1}e$ simply removes the outgoing edges $E_{s}(v_{1})$.
Then, we combine the first two columns of $\mathscr{L}(\Gamma)$ by making
their sum the first column of $\mathscr{L}(\Gamma/_{1}e)$, since when we
perform a contraction that merges $v_{1}$ and $v_{2}$ into $v_{12}$, we also
have $E_{t}(v_{1})\cup E_{t}(v_{2})=E_{t}(v_{12})$. Thus
$\mathscr{L}(\Gamma/_{1}e)$ is a $(n-1)\times(n-1)$ matrix that agrees with
both $\mathscr{L}_{1}^{1}(\Gamma)$ and $\mathscr{L}_{1}^{2}(\Gamma)$ on its
last $n-2$ columns, and whose first column is the sum of the first columns of
$\mathscr{L}_{1}^{1}(\Gamma)$ and $\mathscr{L}_{1}^{2}(\Gamma)$. Therefore,

$\displaystyle\det[\mathscr{L}(\Gamma/_{1}\;e)]=\det[\mathscr{L}_{1}^{1}(\Gamma)]+\det[\mathscr{L}_{1}^{2}(\Gamma)]$

Substituting into (4), we obtain

$\displaystyle\det[\mathscr{L}(\Gamma)]$
$\displaystyle=\det[\mathscr{L}(\Gamma\backslash
e)]+\wt(e)\det[\mathscr{L}(\Gamma/_{1}\;e)]$
$\displaystyle=\Omega(\Gamma\backslash e)+\wt(e)\Omega(\Gamma/_{1}\;e)$
$\displaystyle=\Omega(\Gamma)$

as desired.

The second proof of the theorem follows a style similar to Chaiken’s proof of
the Matrix Tree Theorem in [Cha82]. Chaiken actually proves a more general
identity, which he calls the “All-Minors Matrix Tree Theorem,” that gives a
combinatorial formula for any minor of the voltage Laplacian. We do not
reproduce such generality here, but instead follow a simplified version of his
proof, more along the lines of Stanton and White’s version of Chaiken’s proof
of the Matrix Tree Theorem [SW86].

######  Proof 4.10 (Second proof of Theorem 4.2 (Chaiken)).

For simplicity, assume that $\Gamma$ has no multiple edges, since we can
always decompose $\det[\mathscr{L}(\Gamma)]$ into a sum of determinants of
voltage Laplacians of simple subgraphs of $\Gamma$, which also partitions the
sum given in the theorem. We also assume that $\Gamma$ is a complete
bidirected graph, since we can ignore edges not in $\Gamma$ by just
considering them to have edge weight $0$. Write
$\mathscr{L}(\Gamma)=(\ell_{ij})$, write $D(\Gamma)=(d_{ij})$, and write
$\mathscr{A}(\Gamma)=(a_{ij})$, so that $\ell_{ij}=\delta_{ij}d_{ii}-a_{ij}$.
Then the determinant of $\mathscr{L}(\Gamma)$ may be decomposed as

$\displaystyle\det[\mathscr{L}(\Gamma)]=\det[(\delta_{ij}d_{ii}-a_{ij})]$
$\displaystyle=\sum_{S\subseteq[n]}\left[\sum_{\pi\in
P(S)}(-1)^{\\#C(\pi)}\wt_{\nu}(\pi)\prod_{i\in[n]-S}d_{ii}\right]$

where $P(S)$ denotes the set of permutations of $S$, the set $C(\pi)$ is set
of cycles of $\pi$, and $\wt_{\nu}(\pi):=\prod_{i\in S}a_{i,\pi(i)}$. The
product of the $d_{ii}$ may be rewritten as a sum over functions
$[n]-S\to[n]$, yielding

$\displaystyle\det[\mathscr{L}(\Gamma)]$
$\displaystyle=\sum_{S\subseteq[n]}\sum_{\pi\in
P(S)}(-1)^{c(\pi)}\wt_{\nu}(\pi)\sum_{f:[n]-S\to[n]}\wt(f)$ (5)
$\displaystyle=\sum_{S\subseteq[n]}\sum_{\pi\in
P(S)}\sum_{f:[n]-S\to[n]}(-1)^{c(\pi)}\wt_{\nu}(\pi)\wt(f)$

where $\wt(f)$ denotes the _unvolted_ weight of the edge set corresponding to
the function $f$, since this part of the product ultimately comes from the
degree matrix. Thus, the determinant may be expressed as a sum of triples
$(S,\pi,f)$ of the above form—that is, we let $S$ be an arbitrary subset of
$[n]$, we let $\pi$ be a permutation on $S$, and we let $f$ be a function
$[n]-S\mapsto[n]$.

The permutation $\pi$ can always be decomposed into cycles, and $f$ will
sometimes have cycles as well—that is, sometimes we have $f^{(m)}(k)=k$ for
some $k\in\BZ$ and $k\in[n]-S$. We can “swap” cycles between $\pi$ and $f$.
Suppose $c$ is a cycle of $f$ that we want to swap into $\pi$. Let the subset
of $[n]$ on which $c$ is defined be denoted $W$. Then we may obtain from our
old triple a new triple $(S\coprod W,\pi\coprod c,f|_{[n]-S-W})$, where
$\pi\coprod c$ denotes the permutation on $S\coprod W$ given by $(\pi\coprod
c)(v)=\pi(v)$ if $v\in S$ and $(\pi\coprod c)(v)=c(v)$ if $v\in W$. That is,
we “move” $C$ from $f$ to $\pi$. Similarly, if $c$ is a cycle of $\pi$, then
we can obtain a new triple $(S-W,\pi|_{S-W},f\coprod c)$. Note that these two
operations are inverses.

This process is always weight-preserving: it does not matter whether $c$ is
considered as a part of $\pi$ or as a part of $f$, since it will always
contribute $\wt(c)$ to the product. However, one iteration of this map will
swap the sign of $(-1)^{\\#C(\pi)}$, and will also remove or add a factor from
$\wt_{\nu}(\pi)$ corresponding to the voltage of $c$. If $\pi$ and $f$ have
$k$ cycles between both of them, then there are $2^{k}$ possibilities for
swaps, yielding a free action of $(\BZ/2\BZ)^{k}$. If we start from the case
where $\pi$ is the empty partition, then the sign $(-1)^{\\#C(\pi)}$ starts at
$1$. Every time we choose to swap a cycle $c$ into $\pi$ from $f$, we flip
this sign and multiply by $\nu(c)$, effectively multiplying by $-\nu(c)$.
Thus, the sum of terms in (5) coming from the orbit of the action of
$(\BZ/2\BZ)^{k}$ on $(S,f,\pi)$ is

$\displaystyle\wt(\pi)\wt(f)\prod_{c\in C(\pi)\cup C(f)}(1-\nu(c))$

where $\wt(\pi)$ is now unvolted. This orbit class corresponds to the
contribution of one vector field $\gamma$ of $\Gamma$ to the overall sum,
where $\gamma$ is the unique vector field such that
$\wt(\gamma)=\wt(\pi)\wt(f)$. Thus, summing over all orbit classes, we obtain
the desired formula:

$\displaystyle\det[\mathscr{L}(\Gamma)]=\sum_{\gamma\subseteq\Gamma}\left[\wt(\gamma)\prod_{c\in
C(\gamma)}(1-\nu(c))\right]$

##  5\. Conjectures and Future Directions

We end our paper by a discussion of several unanswered questions and possible
future research directions.

###  5.1. Interpreting the restriction-of-scalars determinant

In the case where the voltage group $G$ is prime cyclic, Corollary 1.4 yields
a computationally nice interpretation of Theorem 1.3: the $\BZ$-determinant is
really a field norm, which may be computed in ways other than restriction of
scalars—for example, as a product of Galois conjugates. This result could be
extended if there existed an analogue to the field norm for arbitrary reduced
group algebras, or indeed for general free algebras of finite rank. A good
first step might be to consider abelian groups.

######  Problem 5.1.

Let $R$ be a commutative ring, and let $A$ be a free algebra over $R$ of
finite rank. Let $\alpha\in A$. Find an alternative expression or
interpretation of $\det_{R}[\alpha]$, where the multiplicative action of
$\alpha$ is viewed as a linear transformation on the $R$-module $A$, analogous
to a field norm. Useful special cases include $R=\BZ$ or $\BQ$, when $A$ is
commutative, and/or when $A$ is the group algebra or reduced group algebra of
some finite group $G$.

###  5.2. Positivity of the ratio and possible combinatorial expression using
vector fields

By Corollary 1.6, the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ is a homogeneous
polynomial with integer coefficients. We further conjecture that these
coefficients are positive. In more detail:

Let $\Gamma$ be a directed graph, $\tilde{\Gamma}$ a $k$-cover of $\Gamma$,
$v$ a vertex of $\Gamma$ and $\tilde{v}$ a lift of $v$ in $\tilde{\Gamma}$. If
the edge weights of $\Gamma$ are indeterminates then the polynomial
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ has positive
coefficients. Corollary 4.6 gives positivity for regular $2$-fold cover, and
the following proposition gives a way to extend that result to all regular
covers by $2$-groups. However, in the case of general regular covers, we do
not have a concrete combinatorial interpretation of
$\det[\mathscr{L}(\Gamma)]_{\BZ[E]}$. Such an interpretation would probably be
the cleanest way to prove Conjecture 1.8.

######  Proposition 5.2.

Suppose we have the exact sequence of groups $1\to N\to G\to H\to 1$, where
$N$ and $H$ have the property that every regular $N$\- (resp. $H$-) cover
satisfies the positivity conjecture. Then every regular $G$-cover satisfies
the positivity conjecture.

######  Proof 5.3.

Let $\Gamma$ be a graph, let $\Gamma_{G}$ be a regular $G$-cover of $\Gamma$,
and let $\Gamma_{H}$ be the image of $\Gamma_{G}$ under the projection map
$G\to H$. We will show that both the covers $\Gamma_{H}\to\Gamma$ and
$\Gamma_{G}$ to $\Gamma_{H}$ are regular, and therefore that those
arborescence ratios are positive. Therefore, the arborescence ratio for the
cover $\Gamma_{G}\to\Gamma$ is the product of these ratios, and therefore
positive as well.

Since $G$ is a group extension of $H$ by $N$, we will write elements of $G$ as
ordered pairs $(h,n),h\in H,n\in n$, where $n\mapsto(h,n)\mapsto h$ under our
exact sequence. Multiplication of these elements involves Schreier theory:

$(h_{1},n_{1})\cdot(h_{2},n_{2})=(h_{1}h_{2},f(h_{1},h_{2},n_{1})n_{2}),$

where $f(h_{1},h_{2},n_{1})$ is an element of $N$ that is independent of
$n_{2}$ (see, for example, [Mor]).

To show that a given cover is regular, we need to demonstrate voltages for the
edges of the base graph that give us the desired cover. First, we show that
$\Gamma_{H}$ is regular over $\Gamma$.

Let $e:v\to w$ be an edge in $\Gamma$, with $G$-voltage $g=(h_{g},n_{g})$.
Then $e$ lifts to the set of edges $\\{e^{g^{\prime}}:v^{g^{\prime}}\to
w^{gg^{\prime}}\\}$ in $\Gamma_{G}$, and these edges project to the set
$\\{e^{h}:v^{h}\to w^{h_{g}h}\\}$ in $\Gamma_{H}$. Therefore, in the cover
$\Gamma_{H}\to\Gamma$, we can set the voltage of $e$ to be $h_{g}$, and this
gives a regular $H$-cover.

Now we show that $\Gamma_{G}$ is a regular $N$-cover of $\Gamma_{H}$. This is
more challenging since $H$ is not necessarily a subgroup of $G$. Consider the
edge $e$ of $\Gamma$ from above, and let $h\in H$. The edge $e^{h}:v^{h}\to
w^{h_{g}h}$ in $\Gamma_{H}$ is covered by the edges $\\{e^{(h,n)}|n\in N\\}$
in $\Gamma_{G}$. Computations in $G$ tell us that

$e^{(h,n)}:v^{(h,n)}\to
w^{(h_{g},n_{g})\cdot(h,n)}=w^{(h_{g}h,f(h_{g},hn_{g})n)}.$

Set the voltage on $e_{h}$ to be $f(h_{g}hn_{g})\in N$. Then

$(e^{h})^{n}:(v^{h})^{n}\to(w^{h_{g}h})^{f(h_{g}hn_{g})n},$

so identifying $(e^{h})^{n}$ with $e^{(h,n)}$ and likewise for vertices gives
us $\Gamma_{G}$ as a regular cover of $\Gamma_{H}$.

######  Corollary 5.4.

Let $G$ be a 2-group. Then every regular $G$-cover satisfies the positivity
conjecture.

######  Proof 5.5.

By Corollary 4.6, this result holds in the case of $\mathbb{Z}/2\mathbb{Z}$.
Since $G$ is a 2-group, $\mathbb{Z}/2\mathbb{Z}$ is a normal subgroup, and so
the proposition can be applied inductively.

######  Problem 5.6.

Find a combinatorial interpretation of the polynomial
$\frac{1}{k}\det[\mathscr{L}(\Gamma)]_{\BZ[E]}=\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$,
assuming Conjecture 1.8 is true.

Vector fields are a potential source of a combinatorial interpretation for the
arborescence ratio. We observed that in a $k$-fold cover, the ratio
$\frac{A_{\tilde{v}}(\tilde{\Gamma})}{A_{v}(\Gamma)}$ always appears to be a
product of $(k-1)$ weighted sums of vector fields.

######  Conjecture 5.7.

Let $\tilde{\Gamma}$ be a $k$-fold cover of $\Gamma$, then

$\frac{A_{\tilde{v}}{(\tilde{\Gamma})}}{A_{\tilde{v}}{(\Gamma)}}=\sum_{(\gamma_{1},\cdots,\gamma_{k-1})\in\mathcal{V}^{k-1}}f(\gamma_{1},\cdots,\gamma_{k-1})\prod_{i=1}^{k-1}\wt(\gamma_{i})$

where $\mathcal{V}$ is the set of vector fields of $\Gamma$, and $f$ is an
$\mathbb{Z}_{\geq 0}$-valued function.

Moreover, as we look over all possible $k$-fold cover $\tilde{\Gamma}$, the
ratios exhaust all possible $(k-1)$-tuples of vector fields of the base graph,
which is only known in the $2$-fold case. This observation motivates the
following conjecture stated in terms of random covers.

######  Conjecture 5.8.

Let $\Gamma=(E,V)$ be a graph, fix a vertex $v$ with non-trivial arborescence.
Let $\Gamma^{\prime}$ be a random $k$-fold cover of $\Gamma$, assuming uniform
distribution. Then the expected value of the ratio of arborescence is

$\mathbb{E}\left[\frac{\mathcal{A}_{v^{\prime}}(\Gamma^{\prime})}{\mathcal{A}_{v}(\Gamma)}\right]=\frac{1}{k}\left(\sum_{\gamma\in\mathcal{V}}\wt(\gamma)\right)^{k-1}=\frac{1}{k}\prod_{w\in
V}\left(\sum_{\alpha\in E_{s}(w)}\wt(\alpha)\right)^{k-1}$

where $\mathcal{V}$ is the set of vector fields of $\Gamma$.

Conjecture 5.8 is an alternative approach to positivity via a ‘pigeon-hole’
like argument: assuming the ratio of some covering graph has a negative
coefficient, some cancellation shall happen as we sum over all possible
covers; this might cause the expected value to not be ‘large enough’ to match
Conjecture 5.8.

## Acknowledgements

This research was carried out as part of the 2019 Combinatorics REU program at
the University of Minnesota, Twin Cities, supported by NSF RTG grant
DMS-1148634. We would like to thank Vic Reiner for his expertise in the
relevant literature, and for our discussions with him on generalizing the main
result. We would also like to thank Pavlo Pylyavskyy for providing us with the
original version of conjecture, and for his suggestions on how we might
initially proceed.

## References

  * [Cha82] Seth Chaiken.  A combinatorial proof of the all minors matrix tree theorem.  SIAM Journal of Algebraic and Discrete Methods, 3(3):35–42, 1982\.
  * [FS99] Sergey Fomin and Richard Stanley.  Enumerative Combinatorics Volume 2.  Cambridge University Press, 1999.
  * [FZ02] Sergey Fomin and Andrei Zelevinsky.  Cluster algebras i: foundations.  Journal of the American Mathematical Society, 15(2):497–529, 2002\.
  * [GM89] Gary Gordon and Elizabeth McMahon.  A greedoid polynomial which distinguishes rooted arborescences.  Proceedings of the American Mathematical Society, 107(2), 1989.
  * [GP19] Pavel Galashin and Pavlo Pylyavskyy.  $R$-systems.  Selecta Math. (N.S.), 25(2), 2019.
  * [GT75] Jonathan Gross and Thomas Tucker.  Generating all graph coverings by permutation voltage assignments.  Discrete Mathematics, pages 273–283, Aug 1975.
  * [KV06] Bernhard Korte and Jens Vygen.  Combinatorial Optimization: Theory and Algorithms.  Springer, 3 edition, 2006.
  * [Mor] Patrick Morandi.  Group extensions and $h^{3}$.  http://sierra.nmsu.edu/morandi/notes/GroupExtensions.pdf.
  * [RT14] Victor Reiner and Dennis Tseng.  Critical groups of covering, voltage, and signed graphs.  Discrete Math., 318:10–40, 2014.
  * [Sil00] John R. Silvester.  Determinants of block matrices.  The Mathematical Gazette, 84(501):460–467, 2000.
  * [SW86] Dennis Stanton and Dennis White.  Constructive Combinatorics.  Springer-Verlag, 1986.
  * [vAEdB51] T. van Aardenne-Ehrenfest and N. G. de Bruijn.  Circuits and trees in oriented linear graphs.  Simon Stevin, 28:203–217, 1951.
  * [Ver21] Kaustubh Verma.  Double covers of flower graphs and tutte polynomials.  Minnesota Journal of Undergraduate Mathematics, 6(1), 2021.