Sandpile groups of random graphs: 2. Erdős–Rényi model

First, let's consider the following question:

Question. What is the distribution of the number $N_{\Gamma}$ of the spanning trees of a random graph $\Gamma$?

Of course, we need to make sense of what "random" means in the above question. One way to generate random graphs is to use the Erdős–Rényi model. That is, given $n \in \mathbb{Z}_{\geq 2}$ and a real number $0 < q < 1$, we first fix $n$ vertices and choose a graph with these vertices at random by requiring that for each pair of vertices, the probability that the two chosen vertices are connected by an edge is $q.$ We write $G(n, q)$ to mean the set of all graphs with $n$ vertices without self-loops and double edges with the probability measure given by the Erdős–Rényi model. We note that $G(n, q)$ is a finite set of graphs, each of which has the $n$ given vertices with

• no self-loops;
• no double edges;
• and $M$ edges ($0 \leq M \leq {n \choose 2}$),

and each graph in $G(n, q)$ with $M$ edges occurs with the probability $q^{M}(1 - q)^{{n \choose 2} - M}.$ Hence, the probability that the number of edges of an Erdős–Rényi random graph is equal to $M$ is ${{n \choose 2} \choose M}q^{M}(1 - q)^{{n \choose 2} - M}.$ That is, the distribution of the number of edges of a random $\Gamma \in G(n, q)$ follows the binomial distribution with parameters $q$ and ${n \choose 2}.$ In particular, the average number of the edges in a graph randomly chosen in $G(n, q)$ is ${n \choose 2}q.$

Cayley's formula says that the total number of spanning trees on given $n$ vertices is $n^{n-2},$ and the probability that each spanning tree occurs in a random graph in $G(n, q)$ is $q^{n-1}.$ Hence, given $0 \leq m \leq n^{n-2},$ we have $$\underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(N_{\Gamma} = m) = {n^{n-2} \choose m} (q^{n-1})^{m}(1 - q^{n-1})^{n^{n-2} - m}.$$ That is, the number $N_{\Gamma}$ of a random graph $\Gamma \in G(n, q)$ follows the binomial distribution with parameters $q$ and $n^{n-2}.$ In particular, the average number of spanning trees of $\Gamma$ is $n^{n-2}q^{n-1}.$

Now, we know completely what the distribution of the number of spanning trees of $\Gamma$ randomly chosen from $G(n, q).$ In the last posting, we discussed how Kirchhoff's theorem tells us that the number $N_{\Gamma}$ of spanning trees of a graph $\Gamma$ is the product of the non-negative invariant factors of its sandpile group $S_{\Gamma}.$

Question. What is the distribution of the sandpile group $S_{\Gamma}$ of $\Gamma$ randomly chosen in $G(n, q)$?

It turns out from a paper of Wood (Corollary 9.3) that for any finite abelian group $A,$ we have $$\lim_{n \rightarrow \infty}\underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(S_{\Gamma} \simeq A) = 0.$$ We already know that the expected number $$n^{n-2}q^{n-1} = \frac{(nq)^{n-1}}{n}$$ of $N_{\Gamma}$ is large (which is in particular nonzero) when $n$ is large, so we expect $S_{\Gamma}$ to be a finite group. More precisely, we have $$\underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(S_{\Gamma} \text{ is infinite}) = \underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(N_{\Gamma} = 0) = (1 - q^{n-1})^{n^{n-2}}.$$ If $0 < q < 1$ is fixed, then this implies that $$\lim_{n \rightarrow \infty}\underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(S_{\Gamma} \text{ is infinite}) = 0.$$ Hence, the fact that the probability that $S_{\Gamma}$ is isomorphic to a specific finite abelian group is small for large $n$ has to do with that the events we are considering are too fine.

Remark. This is a strange phenomenon. Heuristically, one may say that there are too many candidates for $S_{\Gamma}$ when we take a random $\Gamma \in G(n, q),$ which makes it less likely if we try to specify the isomorphism class of $S_{\Gamma},$ but there are other similar instances, where we choose from many finitely abelian groups but the probability does not converge to $0.$ For example, see this paper of Nguyen and Wood (Theorem 1.1 with $u = 1$).

It also turns out that given a prime $p,$ the $p$-part $S_{\Gamma}[p^{\infty}]$ of the sanpile group of a random graph $\Gamma \in G(n, q)$ has a nontrivial distribution. The following theorem is from a paper of Wood (Theorem 1.1):

Theorem (Wood). Let $p$ be a prime and $G$ a finite abelian $p$-group so that $$G \simeq \mathbb{Z}/p^{\lambda_{1}}\mathbb{Z} \times \mathbb{Z}/p^{\lambda_{2}}\mathbb{Z} \times \cdots \mathbb{Z}/p^{\lambda_{l}}\mathbb{Z}$$ with $\lambda_{1} \geq \lambda_{2} \geq \cdots \geq \lambda_{l} \geq 0.$ Let $(\mu_{1}, \mu_{2}, \dots)$ be the transpose of the partition $(\lambda_{1}, \lambda_{2}, \dots, \lambda_{l}).$ Then $$\begin{align*}\lim_{n \rightarrow \infty} & \underset{\Gamma \in G(n, q)}{\mathrm{Prob}}(S_{\Gamma}[p^{\infty}] \simeq G) \\ &= \frac{p^{-\sum_{r \geq 1} \mu_{r}(\mu_{r}+1)/2}\prod_{i=1}^{\lambda_{1}}\prod_{j=1}^{\lfloor (\mu_{i} - \mu_{i+1})/2 \rfloor} (1 - p^{-2j})^{-1}}{|G||\mathrm{Aut}(G)|}\prod_{k \geq 0} (1 - p^{-2k-1}).\end{align*}$$

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?