Diane Christine Alar^a , Jonathan Celaya^b , Luis David Garc´ıa Puente^c , Micah Henson^d , Ashley K. Wheeler^∗e

christine@math.ucsb.edu, lgarciapuente@coloradocollege.edu, mhenson2@uw.edu, wheeler@math.gatech.edu

The majority of graphs whose sandpile groups are known are either regular or simple. We give an explicit formula for a family of non-regular multi-graphs called thick cycles. A thick cycle graph is a cycle where multi-edges are permitted. Its sandpile group is the direct sum of cyclic groups of orders given by quotients of greatest common divisors of minors of its Laplacian matrix. We show these greatest common divisors can be expressed in terms of monomials in the graph's edge multiplicities.

Keywords: sandpile group, critical group, Jacobian group, thick cycles

Mathematics Subject Classification: 05C25

DOI: 10.5614/ejgta.2022.10.2.20

1. Introduction

The Abelian Sandpile Model was first conceived in 1987 by the physicists Bak, Tang, and Wiesenfeld [2], who developed a cellular automaton model for natural systems with a critical point as an attractor. In 1990, Dhar [21] generalized their model to run on a graph with a distinguished vertex called a sink. The collection of critical stable configurations in the model form a group, the sandpile group of a graph. The sandpile group is also called the critical group (in the chip-firing game [7, 8, 9]), or, in other contexts, the Picard group or the Jacobian group (when regarding

Received: 8 February 2022, Revised: 9 October 2022, Accepted: 12 October 2022.

^aDepartment of Mathematics, University of California, Santa Barbara

^bR&D Operations Research, Penn State University

^cDepartment of Mathematics and Computer Science, Colorado College

^dDepartment of Applied Mathematics, University of Washington

^eSchool of Mathematics, Georgia Institute of Technology

^∗corresponding author

the graph as a discrete analogue of a Riemann surface [3]), the group of bicycles (a way to count spanning trees [5]), the tree group (also related to spanning trees [6]), and the group of components (on arithmetical graphs [28]).

Explicit formulae for the sandpile groups of several families of graphs are known. These include complete graphs \(K_n\) [7, 29], complete bipartite graphs \(K_{m,n}\) [29], complete multipartite graphs \(K_{\vec{n}}\) [25], cycles \(C_n\) [31], generalized de Bruijn graphs [12], line graphs of graphs [4], Möbius ladders \(M_n\) [14, 20], regular trees [37], threshold graphs [18], square cycles \(C_n^2\) [15], twisted bracelets [34], and wheel graphs \(W_n\) [19]. Sandpile groups of certain Cartesian products of graphs are also known [13, 16, 24, 27, 35, 38, 39]. However, there are only a few families of non-simple graphs for which the sandpile groups are known; these include thick tree graphs [17], wired tree graphs \(\bar{T}_n\) [26], and (q, t)-wheel graphs \(W_k(q, t)\) [32].

We provide a general formula for the sandpile group of a family of non-regular multi-graphs called thick cycles (or thick n-cycles). A thick cycle graph is a cycle with multi-edges. The authors would like to thank a referee for pointing out our formula can be recovered from a result due to Wagner [40]. Wagner proved the sandpile group of a graph only depends on its graphic matroid. Whitney's 2-isomorphism theorem then shows that 2-vertex connected graphs (like thick cycles) have the same matroid if only one can perform a sequence of 2-isomorphisms to get from one graph to another. One can pass between any two thick cycles that have the same edges multiplicities via a sequence of 2-isomorphisms. Our result is an independent derivation of the formula for the sandpile group of a thick cycle graph, and it is the first known general formula for the sandpile group of any family of non-regular multi-graphs.

Section 2 of this paper consists of the necessary background information on sandpile groups. In Section 3 we prove the following:

Theorem (3.1). The sandpile group of a thick n-cycle \(C_{\vec{a}}\) with multiplicity vector \(\vec{a} = (a_1, \dots, a_n)\) is

\[\mathbb{S}(C_{\vec{a}}) \cong \mathbb{Z}_{g_1} \oplus \mathbb{Z}_{\frac{g_2}{g_1}} \oplus \cdots \oplus \mathbb{Z}_{\frac{g_{n-2}}{g_{n-3}}} \oplus \mathbb{Z}_{\frac{|\mathbb{S}(C_{\vec{a}})|}{g_{n-2}}},\]

where \(g_t = \gcd(a_{i_1} \cdots a_{i_t} \mid 1 \le i_1 < \cdots < i_t \le n)\) for \(t = 1, \dots, n-2\) (gcd denotes the greatest common divisor).

Theorem 3.1 implies the sandpile groups of thick cycles are isomorphic when their multiplicity vectors' entries are permutations of each other. In Section 4 we list a brief proof of this corollary and a few more consequences. An explicit formula for the sandpile group of a thick cycle simultaneously gives a formula for the sandpile group of its dual [19]. Thus we have formulae for subdivided banana graphs and we recover and generalize the formula for book graphs given by Emig, et al. [22]. A formula for the sandpile group of a thick cycle also provides more insight into the study of bilinear pairings on graphs. We suggest future directions of research to pursue in Section 5.

2. Preliminaries

Definition 2.1. A thick cycle of order n (or a thick n-cycle), denoted \(C_{\vec{a}}\), is a multi-graph consisting of an n-cycle with edge multiplicities given by the multiplicity vector \(\vec{a} = (a_1, a_2, \dots, a_n)\).

The sandpile group of a thick cycle graph | Diane Christine Alar et al.

Figure 1. Thick 5-cycle with multiplicity vector ⃗a = (3, 2, 4, 2, 3).

For convention, we label a thick cycle with vertices v1, . . . , vⁿ and multiplicity vector ⃗a = (a1, . . . , an) such that aⁱ is the multiplicity of the edge joining vⁱ and vi+1, indices modulo n. Figure 1 is an example of a thick 5-cycle with multiplicity vector ⃗a = (3, 2, 4, 2, 3). Thick cycles are undirected graphs. Recall that an undirected edge can be presented as two opposite directed edges. We note here that the broader sandpile group theory is on directed graphs; however, we shall only consider undirected graphs, in which case the theory is somewhat simplified.

2.1. The sandpile group

The Laplacian of a(n undirected) graph Γ is the matrix

\[L = L(\Gamma) = (L_{ij}) = \begin{cases} -\operatorname{wt}(v_i, v_j), & i \neq j, \\ d_i, & i = j, \end{cases}\]

where wt(vⁱ , v^j ) denotes the number of edges joining the vertices vⁱ and v^j , and dⁱ denotes the degree of the vertex vⁱ . Each of the entries in a given row sum to zero, and so L has rank at most n − 1. Suppose we distinguish a vertex s = vⁱ in Γ. We define the reduced transposed Laplacian ∆˜ ^s as the submatrix of L obtained by omitting the ith row and column (the Laplacian is symmetric for undirected graphs, but not necessarily for directed graphs). The sandpile group of Γ with distinguished vertex s is given by

\[S(\Gamma, s) \cong \mathbb{Z}^{n-1}/\tilde{\Delta}_s \mathbb{Z}^{n-1} = \operatorname{coker}(\tilde{\Delta}_s),\]

the cokernel of the matrix ∆˜ ^s. Surprisingly, it turns out the sandpile group of an undirected graph is independent of the choice of distinguished vertex [19]. Thus we simply write S(Γ) = S(Γ, s).

2.2. Known results used

A well-known result in the theory of sandpile groups gives a way to determine the order of S(Γ):

Theorem (Kirchhoff's Matrix-Tree Theorem). Suppose \(\Gamma\) is an undirected graph. Then for any distinguished vertex s in \(\Gamma\), the number of spanning trees of \(\Gamma\) is

\[\kappa(\Gamma) = |\det(\tilde{\Delta}_s)|,\]

where \(\tilde{\Delta}_s\) is the reduced transposed Laplacian for \(\Gamma\).

It follows that the reduced transposed Laplacian has rank exactly n-1.

Now recall that an \(n \times n\) matrix M is \(\mathbb{Z}\)-equivalent to a matrix M' if M' can be obtained from M by some sequence of the following row (or column) operations: (1) adding an integer multiple of one row (column) to another, (2) multiplying a row (column) by -1, or (3) deleting row i and column j if column j is the standard basis vector \(\mathbf{e}_i\). In addition, given a matrix M, we call the nonzero entries on D, the diagonal \(\mathbb{Z}\)-equivalent matrix of M, the invariant factors of M. We also recall the Invariant Factors Theorem:

Theorem (Invariant Factors Theorem). Suppose M is an \(n \times n\) integer matrix of rank r. Then M is \(\mathbb{Z}\)-equivalent to a diagonal matrix

\[D = \begin{bmatrix} f_1 & & & \\ & \ddots & & \\ & & f_r & \\ & & & \mathbf{0} \end{bmatrix} \tag{1}\]

and

\[f_1 = m_1, \ f_2 = \frac{m_2}{m_1}, \ \dots, \ f_r = \frac{m_r}{m_{r-1}},\]

where for \(1 \le t \le r\), \(m_t\) denotes the greatest common divisor (gcd) of the t-minors of M.

The diagonal matrix D is the Smith normal form of M. The non-unit integers among \(f_1, \ldots, f_r\) are the invariant factors of M and of the finitely generated abelian group

\[\operatorname{coker}(D) \cong \mathbb{Z}_{f_1} \oplus \cdots \oplus \mathbb{Z}_{f_r} \oplus \mathbb{Z}^{n-r} \cong \operatorname{coker}(M).\]

Thus to compute \(S(\Gamma, s)\), we compute the Smith normal form of \(\tilde{\Delta}_s\) (so it is enough to compute the Smith normal form of the Laplacian). Similar matrices have the same determinant and so \(|\det(\tilde{\Delta}_s)| = |S(\Gamma)|\) is the product of the invariant factors for \(\tilde{\Delta}_s\).

3. Main Results

Proposition 3.1. Given a thick n-cycle \(C_{\vec{a}}\) with multiplicity vector \(\vec{a} = (a_1, \ldots, a_n)\), the order of the sandpile group \(S(C_{\vec{a}})\) is given by the formula

\[|\mathcal{S}(C_{\vec{a}})| = \sum_{i=1}^{n} \frac{a_1 \cdots a_n}{a_i}.\]

Proof. By Kirchhoff's Matrix-Tree Theorem, the number of spanning trees on a graph is equal to the order of its sandpile group. To generate a spanning tree for \(C_{\vec{a}}\), we remove the edges between two adjacent vertices and then choose a single edge from each set of edges left. This creates a connected subgraph with n vertices and n-1 edges. The number of spanning trees will therefore be the number of ways we can choose n-1 edges in this manner. Let \(\Gamma_i\) denote the subgraph of \(C_{\vec{a}}\) obtained by removing the edges between \(v_i\) and \(v_{i+1}\). The product of all \(a_j\) for \(1 \le j \le n\), \(j \ne i\) yields the number of spanning trees on \(\Gamma_i\),

\[\kappa(\Gamma_i) = \prod_{j=1, j \neq i}^n a_j.\]

The total number of spanning trees on \(C_{\vec{a}}\) is the sum of the number of spanning trees of the subgraphs \(\Gamma_i\).

\[|\mathcal{S}(C_{\vec{a}})| = \sum_{i=1}^{n} \kappa(\Gamma_i) = \sum_{i=1}^{n} \prod_{j=1, j \neq i}^{n} a_j = \sum_{i=1}^{n} \frac{a_1 \cdots a_n}{a_i}.\]

Theorem 3.1 (Sandpile Group of a Thick Cycle). The sandpile group of a thick n-cycle \(C_{\vec{a}}\) with multiplicity vector \(\vec{a} = (a_1, \dots, a_n)\) is

\[S(C_{\vec{a}}) \cong \mathbb{Z}_{g_1} \oplus \mathbb{Z}_{\frac{g_2}{g_1}} \oplus \cdots \oplus \mathbb{Z}_{\frac{g_{n-2}}{g_{n-3}}} \oplus \mathbb{Z}_{\frac{|S(C_{\vec{a}})|}{g_{n-2}}}\]

where \[g_t = \gcd(a_{i_1} \cdots a_{i_t} \mid 1 \le i_1 < \cdots < i_t \le n)\] for \(t = 1, \dots, n-2\).

Proof. Unless stated otherwise, when performing arithmetic on any indices we work modulo n. Given the Laplacian matrix \(L = L(C_{\vec{a}})\), let L' denote the matrix resulting from permuting the jth column of L to the (j+1)th column:

\[L' = \begin{bmatrix} -a_1 & 0 & \cdots & 0 & -a_n & a_n + a_1 \\ a_1 + a_2 & -a_2 & \ddots & \ddots & 0 & -a_1 \\ -a_2 & \ddots & \ddots & \ddots & \vdots & 0 \\ \ddots & \ddots & \ddots & -a_{n-2} & 0 & \vdots \\ \ddots & \ddots & -a_{n-2} & a_{n-2} + a_{n-1} & -a_{n-1} & 0 \\ 0 & \cdots & 0 & -a_{n-1} & a_{n-1} + a_n & -a_n \end{bmatrix}\]

Up to row and column indices, L' and L have the same Smith normal form and the same minors. Thus the invariant factors of \(S(C_{\vec{a}})\) are

\[f_1 = m_1, \ f_2 = \frac{m_2}{m_1}, \ \dots, \ f_{n-1} = \frac{m_{n-1}}{m_{n-2}},\]

where \(m_t\) denotes the greatest common divisor of the t-minors of L' (t = 1, ..., n - 1); in fact, \(m_{n-1} = |S(C_{\vec{a}})|\). We claim all nonzero t-minors of L' are sums of square-free degree t monomials,

up to sign, in the multiplicities \(a_1, \ldots, a_n\). Granting the claim and using the fact that for integers a, b,

\[\gcd(a, a + b) = \gcd(\pm a, \pm b),\]

if for every t-subset \(\{i_1, \ldots, i_t\}\) of distinct indices \((t = 1, \ldots, n-2)\) L' has a minor equal to \(\pm a_{i_1} \cdots a_{i_t}\), then it follows that \(m_t = g_t\).

It is clear the size t minors are homogeneous of degree t in the \(a_i\)s because the nonzero entries of L' are all linear in the \(a_i\)s. Assume there is a minor with a term that is not square-free. Then in particular there is a size 2 subminor where an \(a_i\) appears either on both diagonal entries or on both anti-diagonal entries. However, by construction of L' the only such 2-minors are of the form

\[\mu = \begin{vmatrix} a_{i-1} + a_i & -a_i \\ -a_i & a_i + a_{i+1} \end{vmatrix},\]

in which case the square terms cancel.

We now show that for a fixed t-subset \(I = \{i_1, \ldots, i_t\}\) of distinct indices, L' has a minor equal to \(\pm a_{i_1} \cdots a_{i_t}\). First, reorder the elements in I so that \(i_1 < \cdots < i_t \le n\). We shall construct a \(t \times t\) matrix M similar to a submatrix of L', such that M is block upper triangular, each of its diagonal blocks are either upper or lower triangular, and its main diagonal entries are \(-a_{i_1}, \ldots, -a_{i_t}\). Then \(\det M = \pm a_{i_1} \cdots a_{i_t}\) is equal to some t-minor of L'.

Step 1. Let M' denote the submatrix of L' given by the row and column indices from I. The main diagonal of M' consists of the entries \(-a_{i_1},\ldots,-a_{i_t}\) from the main diagonal of L'. We claim that if there exists \(i \in I\) such that in M', \(-a_i\) is the only nonzero entry in either its row or column, then we may put M = M' and then we are done. Indeed, if \(-a_i\) is the only nonzero entry in its row then \(i-1, i-2 \notin I\) and we can decompose M' as a block upper triangular matrix

\[M' = \begin{bmatrix} A & C \\ \mathbf{0} & B \end{bmatrix},\tag{2}\]

such that \(-a_i\) is the upper leftmost entry of B, and both blocks A and B are lower triangular. Then \(\det M = \det A \det B\). On the other hand, if \(-a_i\) is the only nonzero entry in its column then \(i+1, i+2 \notin I\). Thus we can decompose M' as in (2), but with \(-a_i\) as the lower rightmost entry of A. Again, both blocks A and B are lower triangular and the result follows.

Step 2. Given this decomposition, suppose M' has no row or column containing exactly one nonzero entry, i.e., for every \(i \in I\), we must have at least one element from each of the sets \(\{i-1,i-2\},\{i+1,i+2\}\) also contained in I. It is not clear whether M' has the desired determinant. We instead use the following algorithm to construct a submatrix of L' whose determinant is \(\pm a_{i_1} \cdots a_{i_t}\). Let \(R = (R_1, \ldots, R_t)\) and \(C = (C_1, \ldots, C_t)\) denote ordered, indexed sets. We initialize by setting \(R = C = (i_1, \ldots, i_t)\) and putting k = t. At each step, let M denote the submatrix of L' whose rows are indexed by R and columns are indexed by R. If \(R_k - R_{k-1} = 2\) then replace \(R_k \mapsto R_k + 1\), \(C_k \mapsto C_k - 1\), and \(k \mapsto k - 1\). The algorithm ends when k = 1.

In the algorithm, if the initial consecutive row indices \(R_k\), \(R_{k-1}\) differ by 2, it follows that the kth column of M consists of \(-a_{i_k}\) on the main diagonal with \(-a_{i_{k+1}}\) directly below, and this

Table 1. Index condition from Example 1. For each index \(i_k \in I = \{1, 2, 3, 5, 6, 7, 9, 10\}\), we check that at least one element from each of the sets \(\{i_k - 1, i_k - 2\}, \{i_k + 1, i_k + 2\}\) is contained in I.

prevents any decomposition into a block upper triangular matrix. Incrementing \(R_k\) by one and decrementing \(C_k\) by one alters the indices so that the entry \(-a_{i_k}\) on the main diagonal of M comes from the lowermost diagonal of L'. This may cause C to have repeated entries. However, if that is the case, it means that \(R_{k-1}, R_{k-2}\) also differ by 2, so again we reselect indices to pick the entry \(-a_{k-1}\) from the lowermost diagonal of L'. When the algorithm ends, the resulting matrix M is block upper triangular, with blocks alternating between lower and upper triangular, and its main diagonal consists of the entries \(-a_{i_1}, \ldots, a_{i_t}\). Therefore \(\det M = \pm a_{i_1} \cdots a_{i_t}\).

Example 1. Here we provide an example of how to utilize the algorithm in the proof of Theorem 3.1. Suppose n = 10 and we wish to find the minor of the Laplacian L equal to \(\pm a_1 a_2 a_3 a_5 a_6 a_7 a_9 a_{10}\).

Step 1. The index set is \(I = \{1, 2, 3, 5, 6, 7, 9, 10\}\) and we have

\[M' = \begin{bmatrix} -a_1 & 0 & 0 & 0 & 0 & 0 & -a_{10} & a_{10} + a_1 \\ a_1 + a_2 & -a_2 & 0 & 0 & 0 & 0 & 0 & 0 & -a_1 \\ -a_2 & a_2 + a_3 & -a_3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -a_4 & -a_5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & a_5 + a_6 & -a_6 & 0 & 0 & 0 \\ 0 & 0 & 0 & -a_6 & a_6 + a_7 & -a_7 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -a_8 & -a_9 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & a_9 + a_{10} & -a_{10} \end{bmatrix}.\]

However, M' has no row or column consisting of exactly one nonzero entry. Indeed, Table 1 verifies the necessary and sufficient condition on the indices, namely, that for each k, at least one element from each of the sets \(\{i_k - 1, i_k - 2\}, \{i_k + 1, i_k + 2\}\) is contained in I. Thus we must proceed to Step 2.

Step 2. Table 2 shows each iteration of the algorithm that will modify the indices appearing in R and C until the desired matrix M is obtained. The bold entries indicate each change in R and

Table 2. Each iteration of the algorithm in Step 2 of Theorem 3.1, applied to Example 1.

C. The resulting matrix with row indices R=(1,2,3,6,7,8,9,10) and column indices C=(1,2,3,4,5,6,9,10) is

\[M = \begin{bmatrix} -\mathbf{a_1} & 0 & 0 & 0 & 0 & 0 & -a_{10} & a_{10} + a_1 \\ a_1 + a_2 & -\mathbf{a_2} & 0 & 0 & 0 & 0 & 0 & 0 & a_1 \\ -a_2 & a_2 + a_3 & -\mathbf{a_3} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -\mathbf{a_5} & a_5 + a_6 & -a_6 & 0 & 0 \\ 0 & 0 & 0 & 0 & -\mathbf{a_6} & a_6 + a_7 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -\mathbf{a_7} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -\mathbf{a_9} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -a_9 + a_{10} \end{bmatrix}.\]

The bold entries are the desired factors of the determinant, while the shaded regions are the triangular blocks on the diagonal. Since below the blocks are zeros the determinant of M is equal to the product of the determinants of the blocks.

4. Consequences

In this section, we discuss some consequences of Theorem 1.

4.1. Permutations of thick cycle multiplicities

We consider the implication of our result to thick cycles whose edge multiplicities are permutations of each other. That is, we consider when the edge multiplicity vectors of two thick cycles are equivalent up to permutation.

We note that the invariant factors of a thick cycle graph's sandpile group are dependent solely dependent upon the edge multiplicities. Thus, the order in which the edge multiplicities are arranged in our graph has no influence on them. Hence, any permutation of the n edges in an n-thick cycle graph will yield the same sandpile group.

Corollary 4.1. Given a thick cycle \(C_{\vec{a}}\), the sandpile group \(S(C_{\vec{a}})\) is equal to the sandpile group \(S(C_{\vec{b}})\), where \(\vec{b}\) is any permutation of the components of \(\vec{a}\).

4.2. Sandpile groups of dual graphs

A dual graph Γ ′ of a planar graph Γ is constructed by placing a vertex of the dual in every face of Γ and creating edges by connecting vertices of Γ ′ across edges of Γ. We note that under this definition, a planar graph Γ may have many different duals, depending on its embedding. Dual graphs are a generalization of dual tessellations and of dual polyhedra, the latter of which are used in linear and integer programming. R. Cori and D. Rossin showed in 1990 [19] that the sandpile groups of a graph and any of its dual are isomorphic.

As an example, recall that the book graph, B(n, k), is the graph Cartesian product of the star graph Sn+1 and the path graph Pk. It has been proved by Emig, et al [22] that B(n, k) is a dual of the subfamily of thick cycle graphs, the thick (k + 1)-cycles C(1,n−1,...,n−1). Hence, by computing the sandpile group for the general thick cycle graph, we recover and indeed generalize the formula for the sandpile group of book graphs.

Corollary 4.2. The sandpile group of a book graph B(n, k), with k n-cycle pages, is equal to

\[S(B(n,k)) = \mathbb{Z}_{n-1}^{k-2}.\]

Additionally, consider the so-called subdivided banana graphs as in [23]. A subdivided banana graph is any graph which can be constructed in the following manner: consider two nodes a and b with k edges between them. On each of the edges 1 ≤ l ≤ k, we introduce s^l new nodes, subdividing the edge from a to b into a path of length l + 2. This yields the subdivided banana B^s1+1,s2+1,...,sk+1. D. Lorenzini [30] computed the order of specific elements in the sandpile group for subdivided banana graphs. The thick cycle graph C⃗a is a planar dual to the subdivided banana graph B⃗s, where ⃗a = ⃗s. Our result is consistent with the formulae in [11].

4.3. Bilinear pairings

In this paper, as in Shokreih [36], we consider a bilinear pairing to be a well-defined, symmetric, non-degenerate map ⟨·, ·⟩ : M × N → K, where M, N and K are groups. We note that the exact specifications of bilinear maps may vary by field (for example, in cryptography the map may be defined over R−Modules, or require M and N to have prime order).

On any graph Γ, the sandpile group S(Γ) comes with a bilinear pairing of the form

\[\langle \cdot, \cdot \rangle : \mathcal{S}(\Gamma) \times \mathcal{S}(\Gamma) \to \mathbb{Q}/\mathbb{Z}\]

with ⟨·, ·⟩ specifically described by [36]. This map is called the monodromy pairing (introduced as early as 1997 in [1] in the context of graphs and later in [10]). Shokrieh uses the monodromy pairing to study the discrete logarithm problem on the Jacobian of finite graphs. In addition, L. Gaudet, et al. [23] have previously used thick cycle graphs to study bilinear pairings as they arise from the sandpile groups of various classes of graphs.

5. Future Work

Thick cycles are one of the first families of multi-graphs, and the first family of non-regular multi-graphs, to have their sandpile group computed. The methods and results in this paper can

hopefully be utilized in computing the sandpile groups of more families of non-regular multigraphs. One such particularly interesting family are the series parallel graphs, of which thick cycles are a subfamily. Series parallel graphs are widely studied in electrical networks and are also researched in computational complexity theory. Thick cycles have already proved useful in studying this wider class of graphs [33]. In addition, thick cycle graphs will be of even more use in studying bilinear forms, now that a general formula for their sandpile groups has been computed.

Acknowledgements

This work was conducted during the 2016 Mathematical Sciences Research Institute Undergraduate Program (MSRI-UP), which is supported by the National Science Foundation (grant No. DMS-1156499) and the National Security Agency (grant No. H98230-116-1-0033). Special thanks to on-site program director Dr. Suzanne Weekes of Worcester Polytechnic Institute.

References

• [1] R. Bacher, P. de la Harpe, and T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France. 125(2) (1997).
• [2] P. Bak, C. Tang, and K. Wiesenfeld, Self-organized criticality: An esplanation of the 1/f noise, Phys. Rev. Lett. 59 (1987), 381-384.
• [3] M. Baker and S. Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215(2) (2007), 766–788.
• [4] A. Berget, A. Manion, M. Maxwell, A. Potechin, and V. Reiner, The critical group of a line graph, Ann. Comb. 16(3) (2012), 449–488.
• [5] K.A. Berman, Bicycles and spanning trees, SIAM J. Algebraic Discrete Methods 7(1) (1986), 1–12.
• [6] N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29(6) (1997), 641–682.
• [7] N.L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9(1) (1999), 25–45.
• [8] A. Bojrner and L. Lov ˝ asz, Chip-firing games on directed graphs, ´ J. Algebraic Combin. 1(4) (1992), 305–328.
• [9] A. Bojrner, L. Lov ˝ asz, and P.W. Shor, Chip-firing games on graphs, ´ European J. Combin. 12(4) (1991), 283–291.
• [10] S. Bosch and D, Lorenzini, Grothendieck's pairing on component groups of Jacobians, Invent. Math. 148(2) (2002), 353-396.

• [11] S. Bosch, W. Lutkebohmert, and M. Raynaud, Neron Models ´ , Springer-Verlag (1990).
• [12] S.H. Chan, H.D.L. Hollmann, and D.V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, J. Algebra 421 (2015), 268–295.
• [13] P. Chen and Y. Hou, On the sandpile group of P⁴ × Cn, European J. Combin. 29(2) (2008), 532–534.
• [14] P. Chen, Y. Hou, and C. Woo, On the critical group of the Mobius ladder graph, ˝ Australas. J. Combin. 36 (2006), 133–142.
• [15] P. Chen, Y. Hou, and C. Woo, On the sandpile group of the square cycle C 2 ⁿ, Linear Algebra Appl. 418(2-3) (2006), 457–467.
• [16] P.G. Chen and Y.P. Hou, The critical group of the graph Pⁿ × C3, J. Nat. Sci. Hunan Norm. Univ. 28(4) (2005), p.05.
• [17] W. Chen and T. Schedler, Concrete and abstract structure of the sandpile group for thick trees with loops, preprint, arXiv:math/0701381 (2007).
• [18] H. Christianson and V. Reiner, The critical group of a threshold graph, Linear Algebra Appl. 349 (2002), 233–244.
• [19] R. Cori and D, Rossin, On the sandpile group of dual graphs, European J. Combin. 21(4) (2000), 447–459.
• [20] M. Deryagina and I. Mednykh, On the Jacobian group for Mobius ladder and prism graphs. ˝ In: Geometry, integrability and quantization XV, Avangard Prima, Sofia (2014), 117 –126.
• [21] D. Dhar, Self-organized critical state of sandpile automation models, Phys. Rev. Lett. 64 (1990). 1613-1616.
• [22] K. Emig, J. Herring, E. Meza, C. Neiuwoudt, and L. Garc´ıa Puente, Sandpile groups of book graphs, 2012 Pacific Undergraduate Research Experience and 2011-2012 Long Undergraduate Research Experience technical reports.
• [23] L. Gaudet, D. Jensen, D. Ranganathan, N. Wawrykow, and T. Weisman, Realization of groups with pairing as jacobians of finite graphs, preprint, arXiv:math/1410.5144 (2014).
• [24] Y. Hou, T. Lei, and C. Woo, On the sandpile group of the graph K³ × Cn. Linear Algebra Appl. 428(8-9) (2008), 1886–1898.
• [25] B. Jacobson, A. Niedermaier, and V. Reiner, Critical groups for complete multipartite graphs and Cartesian products of complete graphs. J. Graph Theory 44(3) (2003), 231–250.
• [26] L. Levine, The sandpile group of a tree, European J. Combin. 30(4) (2009), 1026–1035.

• [27] H. Liang, Y.L. Pan, and J. Wang, The critical group of K^m × Pn, Linear Algebra Appl. 428(11-12) (2008), 2723– 2729.
• [28] D.J. Lorenzini, Arithmetical graphs, Math. Ann. 285(3) (1989), 481–501.
• [29] D.J. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91(3) (1991), 277–282.
• [30] D.J. Lorenzini, Arithmetical properties of Laplacians of graphs, Linear and Multilinear Algebra. 47(4) (2000), 281-306.
• [31] R. Merris, Unimodular equivalence of graphs, Linear Algebra Appl. 173 (1992), 181–189.
• [32] G. Musiker, The critical groups of a family of graphs and elliptic curves over finite fields, J. Algebraic Combin. 30(2) (2009), 255–276.
• [33] S.D. Noble, and G.F. Royle, The Merino-Welsh conjecture holds for series-parallel graphs, European J. Combin. 38 (2014), 24–35.
• [34] J. Shen and Y. Hou, On the sandpile group of 3 × n twisted bracelets, Linear Algebra Appl. 429(8-9) (2008), 1894–1904.
• [35] W.N. Shi, Y.L. Pan, and J. Wang, The critical groups for K^m ∨ Pⁿ and P^m ∨ Pn, Australas. J. Combin. 50 (2011), 113–125.
• [36] F. Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol. 4(1) (2010), 43–56. http://dx.doi.org/10.1515/JMC.2010.002
• [37] E. Toumpakari, On the sandpile group of regular trees, European J. Combin. 28(3) (2007), 822–842.
• [38] J. Wang and Y.L. Pan, The critical group of C⁴ × Cn, Ars Combin. 96 (2010), 129–143.
• [39] J. Wang, Y.L. Pan, and J.M. Xu, The critical group ofK^m × Cn, Acta Math. Sin. (Engl. Ser.) 27(1) (2011), 169–184.
• [40] D.G. Wagner, The critical group of a directed graph. arxiv:0010241 (2000).