Sandpile groups of random graphs -- 1 Preliminaries

In this posting, we start discussing the topic of random sandpile groups.

1 Preliminaries

Let $n \in \mathbb{Z}_{\geq 1}$ and $\Gamma$ a graph (undirected) with verticies $1, 2, \dots, n.$ Given $1 \leq i \neq j \leq n,$ define $\deg(i, j)$ to be the number of edges between vertex $i$ and vertex $j.$ We define $\deg(i)$ to be the number of edges between vertex $i$ and any other vertices. Define the adjacency matrix $A(\Gamma)$ of $\Gamma$ to be the $n \times n$ matrix whose $(i, j)$ entry is $\deg(i, j).$ We define the Laplacian of $\Gamma$ as

$$L(\Gamma) := \mathrm{diag}(\deg(1), \deg(2), \dots, \deg(n)) - A(\Gamma).$$

Remark. Note that $L(\Gamma)$ cannot tell whether there are self-loops on any vertex of the graph $\Gamma.$

Because of the way we defined the degree of each vertex, it is always the case that

• each row of $L(\Gamma)$ sums to $0$ and
• each column of $L(\Gamma)$ sums to $0.$

Denote by $L_{ij}$ the $(i, j)$-entry of $L = L(\Gamma).$ Then

$$L\begin{bmatrix} k_{1} \\ \vdots \\ k_{n} \end{bmatrix} = \begin{bmatrix} L_{11}k_{1} + \cdots + L_{1n}k_{n} \\ \vdots \\ L_{n1}k_{1} + \cdots + L_{nn}k_{n} \end{bmatrix},$$

so if we add all the entries of the last $n \times 1$ matrix, we have

$$(L_{11} + \cdots + L_{n1})k_{1} + \cdots + (L_{1n} + \cdots + L_{nn})k_{n} = 0,$$

since each column of $L = L(\Gamma)$ sums to $0.$ That is, the image $\mathrm{im}(L)$ of $L = L(\Gamma)$ always sits inside

$$(\mathbb{Z}^{n})_{0} := \{(r_{1}, \dots, r_{n}) \in \mathbb{Z}^{n} : r_{1} + \cdots + r_{n} = 0\}.$$

The sandpile group of $\Gamma$ is defined as $S_{\Gamma} := (\mathbb{Z}^{n})_{0}/\mathrm{im}(L).$

Question. When we choose $\Gamma$ at random, how are the sandpile groups $S_{\Gamma}$ distributed?

Of course, this question needs to be polished a bit. 

Lemma. We have

$$\ker(L(\Gamma)) = \bigoplus\mathbb{Z}(e_{i_{1}} + \cdots + e_{i_{k}}),$$

where the direct sum is over the subsets $\{i_{1}, \dots, i_{k}\}$ of the vertex set $\{1, 2, \dots, n\}$ of $\Gamma$, each of which consists of vertices from a connected component of $\Gamma.$ In particular, we see that $\ker(L(\Gamma))$ is a free $\mathbb{Z}$-submodule of $\mathbb{Z}^{n}$ with rank equal to the number of connected components of $\Gamma.$

Remark. It follows from Lemma that $\mathrm{im}(L(\Gamma)) \simeq \mathbb{Z}^{n}/\ker(L(\Gamma))$ is a free $\mathbb{Z}$-module with rank $n - |\pi_{0}(\Gamma)|,$ where we denote by $\pi_{0}(\Gamma)$ the set of connected components of $\Gamma.$ Thus, we note that the sandpile group $S_{\Gamma} = (\mathbb{Z}^{n})_{0}/\mathrm{im}(L(\Gamma))$ is a free $\mathbb{Z}$-module with rank $|\pi_{0}(\Gamma)| - 1.$ In particular, we have

Corollary. The sandpile group $S_{\Gamma}$ of a graph $\Gamma$ is finite if and only if $\Gamma$ is connected.

Proof of Lemma. Note that the elements $e_{i_{1}} + \cdots + e_{i_{k}}$ we consider are $\mathbb{Z}$-linearly independent because the subsets $\{i_{1},  \dots, i_{k}\}$ of $\{1, 2, \dots, n\}$ we consider are disjoint.

We write $L = L(\Gamma)$ for convenience. Let $i_{1} < \cdots < i_{k}$ be the vertices of a connected component of $\Gamma.$ We have 

$$L(e_{i_{1}} + \cdots + e_{i_{k}}) = L(e_{i_{1}}) + \cdots + L(e_{i_{k}}) = \begin{bmatrix} L_{1,i_{1}} + \cdots + L_{1,i_{k}} \\ L_{2,i_{1}} + \cdots + L_{2,i_{k}} \\ \vdots \\ L_{n,i_{1}} + \cdots + L_{n,i_{k}}\end{bmatrix}.$$

Now, for each $1 \leq i \leq n,$ we know that if $i$ does not belong to the connected component, then $L_{i,i_{1}} = \cdots = L_{i,i_{k}} = 0.$ Otherwise (if $i$ belongs to the connected component), we have $i = i_{j}$ for some $1 \leq j \leq k$ and

$$L_{i_{j},i_{1}} + \cdots + L_{i_{j},i_{k}} = L_{i_{j},1} + \cdots + L_{i_{j},n} = 0.$$ Hence, we must have that $L(e_{i_{1}} + \cdots + e_{i_{k}}) = 0$ in $\mathbb{Z}^{n},$ so $$e_{i_{1}} + \cdots + e_{i_{k}} \in \ker(L).$$ This shows that

$$\ker(L) \supset \bigoplus\mathbb{Z}(e_{i_{1}} + \cdots + e_{i_{k}}),$$

so it remains to show the opposite inclusion.

Let $x = \begin{bmatrix}x_{1} \\ \vdots \\ x_{n}\end{bmatrix} \in \ker(L) \subset \mathbb{Z}^{n}.$ We have

$$0 = x^{T}Lx = \sum_{1 \leq i, j \leq n}L_{ij}x_{i}x_{j} = \sum (x_{i} - x_{j})^{2},$$ where the last sum is over $1 \leq i, j \leq n$ such that $v_{i}$ and $v_{j}$ are connected by an edge. (This is by definition of $L = L(\Gamma).$) This implies that for any connected component $\{i_{1}, \dots, i_{k}\},$ we have $x_{i_{1}} = \cdots = x_{i_{k}}$, and these are only relations among $x_{1}, \dots, x_{n}.$ Hence, we see that $x$ is a $\mathbb{Z}$-linear combination of elements of the form $e_{i_{1}} + \cdots + e_{i_{k}}$ in $\mathbb{Z}^{n},$ where $\{i_{1}, \dots, i_{k}\}$ vary in connected components of $\Gamma.$ This finishes the proof. $\Box$

Lemma. Let $n \in \mathbb{Z}_{\geq 2}.$ Given any graph $\Gamma$ with $n$ vertices, its sandpile group $S_{\Gamma}$ is isomorphic to the cokernel of any $(n - 1) \times (n - 1)$ submatrix of $L(\Gamma).$ In particular, the cokernels of $(n - 1) \times (n - 1)$ submatrice of $L(\Gamma)$ are isomorphic to each other.

Proof. We write $L = L(\Gamma).$ Since all the entries of any row or column sum to $0,$ given any $1 \leq i, j \leq n,$ we may add all the other rows to the $i$-th row and then all the other columns to the $j$-th column and replace all the entries of the $i$-th row and the $j$-th column into $0$'s. Since these operations are elementary row operations over $\mathbb{Z},$ this does not change the cokernel of $L$ up to isomorphisms. Denote by $L^{(i,j)},$ the new $n \times n$ matrix. Then we have

$$\mathrm{cok}(L) \simeq \mathbb{Z}^{n}/\mathrm{im}(L^{(i,j)}).$$ Note that $$\mathrm{im}(L^{(i,j)}) \subset \mathbb{Z}e_{1} \oplus \cdots \oplus \mathbb{Z}e_{j-1} \oplus \mathbb{Z}e_{j+1} \oplus \cdots \oplus \mathbb{Z}e_{n}.$$ This implies that $$S_{\Gamma} = (\mathbb{Z}^{n})_{0}/\mathrm{im}(L) \simeq (\mathbb{Z}e_{1} \oplus \cdots \oplus \mathbb{Z}e_{j-1} \oplus \mathbb{Z}e_{j+1} \oplus \cdots \oplus \mathbb{Z}e_{n})/\mathrm{im}(L^{(i,j)}).$$ Let $L_{(i,j)}$ be the $(n-1) \times (n-1)$ matrix given by erasing the $i$-th row and the $j$-th column of $L.$ Then we have $$\begin{align*}(\mathbb{Z}^{n})_{0}/\mathrm{im}(L) &\simeq (\mathbb{Z}e_{1} \oplus \cdots \oplus \mathbb{Z}e_{j-1} \oplus \mathbb{Z}e_{j+1} \oplus \cdots \oplus \mathbb{Z}e_{n})/\mathrm{im}(L^{(i,j)}) \\ &\simeq \mathbb{Z}^{n-1}/\mathrm{im}(L_{(i,j)}) \\ &= \mathrm{cok}(L_{(i,j)}),\end{align*}$$ so $S_{\Gamma} \simeq \mathrm{cok}(L_{(i,j)}),$ as desired. $\Box$

Theorem (Kirchhoff). Let $n \in \mathbb{Z}_{\geq 2}.$ The number of spanning trees of a graph $\Gamma$ with $n$ vertices is equal to the determinant of any $(n-1) \times (n-1)$ submatrix of $L(\Gamma).$ In particular, if $\Gamma$ is connected, then this number is equal to the size of the sandpile group $S_{\Gamma}.$

Remark. Let $L$ be the Laplacian of a graph $\Gamma$ with $n$ vertices with $n \geq 2,$ and $L'$ the $(n-1) \times (n-1)$ submatrix of $L$ given by erasing the last row and the last columns. Then there are always $P, Q \in \mathrm{GL}_{n-1}(\mathbb{Z})$ such that

$$PL'Q = \mathrm{diag}(\lambda_{1}, \dots, \lambda_{n-1})$$ with $\lambda_{1} \geq \cdots \geq \lambda_{n-1} \geq 0$ in $\mathbb{Z}.$ Hence, we have $$S_{\Gamma} \simeq \mathrm{cok}(L') \simeq \mathbb{Z}/\lambda_{1}\mathbb{Z} \times \cdots \times \mathbb{Z}/\lambda_{n-1}\mathbb{Z},$$ and Kirchohoff's theorem tells us that $$\det(L') = \lambda_{1} \cdots \lambda_{n-1}$$ is the number of spanning trees of $\Gamma.$ That is, Kirchohoff's theorem says that the number $N_{\Gamma}$ of spanning trees of $\Gamma$ is equal to the product of (non-negative) invariant factors of its sandpile group $S_{\Gamma}.$

A vague question. If we choose $\Gamma$ at random, what does the distribution of $N_{\Gamma}$ look like? More generally, what does the distribution of $S_{\Gamma}$ look like?