The distribution of sandpile groups of random graphs

By Melanie Matchett Wood. 2014

127 citations recorded by the source corpus.

We determine the distribution of the sandpile group (a.k.a. Jacobian) of the Erd\H{o}s-R\'enyi random graph G(n,q) as n goes to infinity. Since any particular group appears with asymptotic probability 0 (as we show), it is natural ask for the asymptotic distribution of Sylow p-subgroups of sandpile groups. We prove the distributions of Sylow p-subgroups converge to specific distributions conjectured by Clancy, Leake, and Payne. These distributions are related to, but different from, the Cohen-Lenstra distribution. Our proof involves first finding the expected number of surjections from the sandpile group to any finite abelian group (the "moments" of a random variable valued in finite abelian groups). To achieve this, we show a universality result for the moments of cokernels of random symmetric integral matrices that is strong enough to handle dependence in the diagonal entries. We then show these moments determine a unique distribution despite their p^{k^2}-size growth.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/4786f58c0288d9e6140a84da73dee60d685f17a6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Random integral matrices and the Cohen-Lenstra heuristics (2015, methodology): “t too concentrated). To prove our main result, we ﬁrst determine the moments of the cokernel distributions, and from that determine the distributions themselves. Our speciﬁc approach was developed in [Woo14a] for the case of symmetric matrices. In this paper, we are able to use a much simpliﬁed vers”
The distribution of sandpile groups of random regular graphs (2018, methodology): “The statements of (i) can be obtained by slightly modifying the argument of Wood [20][Theorem 8.”
Random integral matrices: universality of surjectivity and the cokernel (2018, methodology): “Our works builds on methods from previous work, including that of Tao and Vu [28–30], the first author and Vu [20], Maples [17], the second author [31,32], and the first author and Paquette [19].”
On a Cohen–Lenstra heuristic for Jacobians of random graphs (2014, background): “The classification of symmetric bilinear forms over Q2 is more complicated, so we treat this case separately at the end of the section.”