The distribution of sandpile groups of random graphs

DOI10.1090/JAMS/866zbMATH Open1366.05098arXiv1402.5149OpenAlexW1955801390MaRDI QIDQ5280066FDOQ5280066

Authors: Melanie Matchett Wood 

Publication date: 20 July 2017

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Abstract: We determine the distribution of the sandpile group (a.k.a. Jacobian) of the ErdH{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.

Full work available at URL: https://arxiv.org/abs/1402.5149

Recommendations

• The distribution of sandpile groups of random regular graphs
• Sandpile groups of random bipartite graphs
• On the sandpile group of a family of graphs
• Sandpile groups and the coeulerian property for random directed graphs
• On a Cohen-Lenstra heuristic for Jacobians of random graphs

zbMATH Keywords

Cohen-Lenstra distributionLittlewood-Offord theorems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Spectral analysis of large dimensional random matrices
• Random matrices: universality of ESDs and the circular law
• Chip-firing and the critical group of a graph
• Chip firing and the Tutte polynomial
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Self-organized criticality
• Title not available (Why is that?)
• Self-organized critical state of sandpile automaton models
• Title not available (Why is that?)
• Chip-firing games on graphs
• Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields
• On the distribution of class groups of number fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristics on Tate-Shafarevitch Groups of Elliptic Curves Defined over Q
• A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs
• Cohen-Lenstra heuristic and roots of unity
• On a Cohen-Lenstra heuristic for Jacobians of random graphs
• Smith normal form and Laplacians
• Harmonic Morphisms and Hyperelliptic Graphs
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Invertibility of symmetric random matrices
• Random symmetric matrices are almost surely nonsingular.
• Arithmetical graphs
• Chip-Firing and Rotor-Routing on Directed Graphs
• The monodromy pairing and discrete logarithm on the Jacobian of finite graphs
• Title not available (Why is that?)
• Algebraic Potential Theory on Graphs
• Orthogonal Matrices Over Finite Fields
• A finite group attached to the laplacian of a graph
• A Unimodality Result in the Enumeration of Subgroups of a Finite Abelian Group
• Title not available (Why is that?)
• On the 4-rank of class groups of quadratic number fields
• On the distribution of the roots of certain symmetric matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• Title not available (Why is that?)
• Circular law
• Limit Theorems for Spectra of Random Matrices with Martingale Structure
• RANDOM MATRICES: THE CIRCULAR LAW
• On the sandpile group of the cone of a graph
• Circular law, extreme singular values and potential theory
• The circular law for random matrices
• The size of Selmer groups for the congruent number problem. II. With an appendix by P. Monsky.
• On random ±1 matrices: Singularity and determinant
• The density of discriminants of quartic rings and fields
• On the density of discriminants of cubic fields. II
• The Strong Circular Law. Twenty years later. Part II
• Title not available (Why is that?)
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Grothendieck's pairing on component groups of Jacobians.
• The asymptotic probability that a random biased matrix is invertible
• Title not available (Why is that?)
• Densities for Ranks of Certain Parts of p-Class Groups
• Quantum unique ergodicity for random bases of spectral projections
• What are zeta functions of graphs and what are they good for?
• Automorphisms of Finite Abelian Groups
• Arithmetical properties of laplacians of graphs
• Jacobians of nearly complete and threshold graphs
• Singularity probabilities for random matrices over finite fields
• The rank of sparse random matrices over finite fields
• The Smith and critical groups of Paley graphs
• Extension of conjectures of Cohen and Lenstra
• Algorithmic Number Theory
• Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves
• Determinants and ranks of random matrices over \({\mathbb{Z}}_ m\)
• Title not available (Why is that?)
• Integer invariants of abelian Cayley graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (55)

• The local weak limit of \(k\)-dimensional hypertrees
• Random amenable C^*-algebras
• Some new results in random matrices over finite fields
• Finite quotients of 3-manifold groups
• A heuristic for boundedness of ranks of elliptic curves
• Random partitions and Cohen-Lenstra heuristics
• Random integral matrices: universality of surjectivity and the cokernel
• Graphs with few trivial characteristic ideals
• The free group on \(n\) generators modulo \(n + u\) random relations as \(n\) goes to infinity
• On a Cohen-Lenstra heuristic for Jacobians of random graphs
• The distribution of sandpile groups of random regular graphs
• Semistable types of hyperelliptic curves
• Polynomial equations for matrices over integers modulo a prime power and the cokernel of a random matrix
• Generalizations of results of Friedman and Washington on cokernels of random \(p\)-adic matrices
• Topology and geometry of random 2-dimensional hypertrees
• Joint distribution of the cokernels of random \(p\)-adic matrices
• The structure of sandpile groups of outerplanar graphs
• Cohen-Lenstra heuristics for torsion in homology of random complexes
• The rank of the sandpile group of random directed bipartite graphs
• On the distribution of equivalence classes of random symmetric p‐adic matrices
• Abelian groups from random hypergraphs
• Moments and interpretations of the Cohen-Lenstra-Martinet heuristics
• Smith normal form in combinatorics
• Codeterminantal graphs
• Surjectivity of near-square random matrices
• Mixed moments and the joint distribution of random groups
• The critical polynomial of a graph
• Universality for cokernels of random matrix products
• Cohen-Lenstra distributions via random matrices over complete discrete valuation rings with finite residue fields
• Recent progress in combinatorial random matrix theory
• The sandpile group of a polygon flower
• Cohen–Lenstra heuristics for étale group schemes and symplectic pairings
• Realization of groups with pairing as Jacobians of finite graphs
• Tensor product Markov chains
• Cohen-Lenstra heuristics and local conditions
• Universality of the cokernels of random 𝑝-adic Hermitian matrices
• Small clique number graphs with three trivial critical ideals
• A natural stochastic extension of the sandpile model on a graph
• Sandpile groups and the coeulerian property for random directed graphs
• Problems in arithmetic topology
• Two-vertex generators of Jacobians of graphs
• Chip-firing games and critical groups
• Probability theory for random groups arising in number theory
• Sandpile groups of supersingular isogeny graphs
• Integral flow and cycle chip-firing on graphs
• Sandpile groups of random bipartite graphs
• Nonabelian Cohen-Lenstra moments
• Publisher correction to: ``Finite quotients of 3-manifold groups
• Joint distribution of the cokernels of random \(p\)-adic matrices. II
• On the distribution of eigenvalues in families of Cayley graphs
• Local limits in \(p\)-adic random matrix theory
• Sandpile groups for cones over trees
• The distribution of sandpile groups of random graphs with their pairings
• Coboundary expansion for the union of determinantal hypertrees
• On the proportion of metric matroids whose Jacobians have nontrivial \(p\)-torsion

This page was built for publication: The distribution of sandpile groups of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280066)