The distribution of sandpile groups of random regular graphs
HTML articles powered by AMS MathViewer
- by András Mészáros PDF
- Trans. Amer. Math. Soc. 373 (2020), 6529-6594 Request permission
Abstract:
We study the distribution of the sandpile group of random $d$-regular graphs. For the directed model, we prove that it follows the Cohen-Lenstra heuristics, that is, the limiting probability that the $p$-Sylow subgroup of the sandpile group is a given $p$-group $P$, is proportional to $|\mathrm {Aut}(P)|^{-1}$. For finitely many primes, these events get independent in the limit. Similar results hold for undirected random regular graphs, where for odd primes the limiting distributions are the ones given by Clancy, Leake, and Payne.
This answers an open question of Frieze and Vu whether the adjacency matrix of a random regular graph is invertible with high probability. Note that for directed graphs this was recently proved by Huang. It also gives an alternate proof of a theorem of Backhausz and Szegedy.
References
- Miklós Abért, Graph convergence, Luck approximation mod p and the entropy of cellular automata, Growth, symbolic dynamics and combinatorics of words in groups, June 2, 2015, ENS, Paris, video available at https://www.youtube.com/watch?v=wRRFOGPnaJY
- Ágnes Backhausz and Balázs Szegedy, On large-girth regular graphs and random processes on trees, Random Structures Algorithms 53 (2018), no. 3, 389–416. MR 3854040, DOI 10.1002/rsa.20769
- Rémi Bardenet and Odalric-Ambrym Maillard, Concentration inequalities for sampling without replacement, Bernoulli 21 (2015), no. 3, 1361–1385. MR 3352047, DOI 10.3150/14-BEJ605
- Manjul Bhargava, Daniel M. Kane, Hendrik W. Lenstra Jr., Bjorn Poonen, and Eric Rains, Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves, Camb. J. Math. 3 (2015), no. 3, 275–321. MR 3393023, DOI 10.4310/CJM.2015.v3.n3.a1
- Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662, DOI 10.1007/978-1-4612-0653-8
- Béla Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), no. 4, 311–316. MR 595929, DOI 10.1016/S0195-6698(80)80030-8
- Julien Clancy, Timothy Leake, and Sam Payne, A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs, Exp. Math. 24 (2015), no. 1, 1–7. MR 3305035, DOI 10.1080/10586458.2014.917443
- Julien Clancy, Nathan Kaplan, Timothy Leake, Sam Payne, and Melanie Matchett Wood, On a Cohen-Lenstra heuristic for Jacobians of random graphs, J. Algebraic Combin. 42 (2015), no. 3, 701–723. MR 3403177, DOI 10.1007/s10801-015-0598-x
- H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62. MR 756082, DOI 10.1007/BFb0099440
- Thomas M. Cover and Joy A. Thomas, Elements of information theory, Wiley Series in Telecommunications, John Wiley & Sons, Inc., New York, 1991. A Wiley-Interscience Publication. MR 1122806, DOI 10.1002/0471200611
- Jordan S. Ellenberg, Akshay Venkatesh, and Craig Westerland, Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields, Ann. of Math. (2) 183 (2016), no. 3, 729–786. MR 3488737, DOI 10.4007/annals.2016.183.3.1
- Matthew Farrell and Lionel Levine, CoEulerian graphs, Proc. Amer. Math. Soc. 144 (2016), no. 7, 2847–2860. MR 3487219, DOI 10.1090/proc/12952
- William Feller, An introduction to probability theory and its applications. Vol. II. , 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
- Eduardo Friedman and Lawrence C. Washington, On the distribution of divisor class groups of curves over a finite field, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 227–239. MR 1024565
- Alan Frieze, Random structures and algorithms, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. 1, Kyung Moon Sa, Seoul, 2014, pp. 311–340. MR 3728474
- D. R. Heath-Brown, The size of Selmer groups for the congruent number problem. II, Invent. Math. 118 (1994), no. 2, 331–370. With an appendix by P. Monsky. MR 1292115, DOI 10.1007/BF01231536
- Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR 2477390, DOI 10.1007/978-3-7643-8786-0_{1}7
- Jiaoyang Huang, Invertibility of adjacency matrices for random d-regular directed graphs, arXiv:1806.01382
- Jiaoyang Huang, Invertibility of adjacency matrices for random d-regular graphs, arXiv:1807.06465
- Svante Janson, Random regular graphs: asymptotic distributions and contiguity, Combin. Probab. Comput. 4 (1995), no. 4, 369–405. MR 1377557, DOI 10.1017/S0963548300001735
- Antal A. Járai, Sandpile models, Probab. Surv. 15 (2018), 243–306. MR 3857602, DOI 10.1214/14-PS228
- Shaked Koplewitz, Sandpile groups and the coeulerian property for random directed graphs, Adv. in Appl. Math. 90 (2017), 145–159. MR 3666713, DOI 10.1016/j.aam.2017.05.002
- Lionel Levine and James Propp, What is $\dots$ a sandpile?, Notices Amer. Math. Soc. 57 (2010), no. 8, 976–979. MR 2667495
- Jessie MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly 76 (1969), 152–164. MR 238870, DOI 10.2307/2317262
- Brendan D. McKay, Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149–160. MR 705968, DOI 10.1016/S0195-6698(83)80045-6
- M. S. O. Molloy, H. Robalewska, R. W. Robinson, and N. C. Wormald, $1$-factorizations of random regular graphs, Random Structures Algorithms 10 (1997), no. 3, 305–321. MR 1606218, DOI 10.1002/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-
- Hoi H. Nguyen and Melanie Matchett Wood, Cokernels of adjacency matrices of random $r$-regular graphs, arXiv:1806.10068
- Serguei Norine and Peter Whalen, Jacobians of nearly complete and threshold graphs, European J. Combin. 32 (2011), no. 8, 1368–1376. MR 2838022, DOI 10.1016/j.ejc.2011.04.003
- Russell Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), no. 4, 491–522. MR 2160416, DOI 10.1017/S096354830500684X
- Walter Rudin, Principles of mathematical analysis, 2nd ed., McGraw-Hill Book Co., New York, 1964. MR 0166310
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Van Vu, Random discrete matrices, Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Springer, Berlin, 2008, pp. 257–280. MR 2432537, DOI 10.1007/978-3-540-77200-2_{1}3
- Melanie Matchett Wood, The distribution of sandpile groups of random graphs, J. Amer. Math. Soc. 30 (2017), no. 4, 915–958. MR 3671933, DOI 10.1090/jams/866
- Melanie Matchett Wood, Random integral matrices and the Cohen-Lenstra heuristics, Amer. J. Math. 141 (2019), no. 2, 383–398. MR 3928040, DOI 10.1353/ajm.2019.0008
- Melanie Matchett Wood, Personal communication, 2018
Additional Information
- András Mészáros
- Affiliation: Department of Mathematics and its Applications, Central European University, Budapest; and Department of Combinatorics and Discrete Mathematics, Alfréd Rényi Institute of Mathematics, Budapest
- Email: Meszaros_Andras@phd.ceu.edu
- Received by editor(s): October 17, 2018
- Received by editor(s) in revised form: December 16, 2019, and January 27, 2020
- Published electronically: July 3, 2020
- Additional Notes: The author was partially supported by the ERC Consolidator Grant 648017 and the Hungarian National Research, Development and Innovation Office, NKFIH grant K109684.
- © Copyright 2020 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 373 (2020), 6529-6594
- MSC (2010): Primary 05C80, 15B52, 60B20
- DOI: https://doi.org/10.1090/tran/8127
- MathSciNet review: 4155185