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*}$$