The distribution of sandpile groups of random regular graphs. (English) Zbl 1475.05156
Summary: 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 \(\vert\text{Aut}(P)\vert^{-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 J. Clancy et al. [Exp. Math. 24, No. 1, 1–7 (2015; Zbl 1310.05121)].
This answers an open question of A. Frieze [in: Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. I: Plenary lectures and ceremonies. Seoul: KM Kyung Moon Sa. 311–340 (2014; Zbl 1373.05177)] and V. Vu [Bolyai Soc. Math. Stud. 17, 257–280 (2008; Zbl 1154.15024)] whether the adjacency matrix of a random regular graph is invertible with high probability. Note that for directed graphs this was recently proved by J. Huang [“Invertibility of adjacency matrices for random d-regular directed graphs”, Preprint, arXiv:1806.01382]. It also gives an alternate proof of a theorem of Backhausz and B. Szegedy [Random Struct. Algorithms 53, No. 3, 389–416 (2018; Zbl 1401.05267)].
This answers an open question of A. Frieze [in: Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. I: Plenary lectures and ceremonies. Seoul: KM Kyung Moon Sa. 311–340 (2014; Zbl 1373.05177)] and V. Vu [Bolyai Soc. Math. Stud. 17, 257–280 (2008; Zbl 1154.15024)] whether the adjacency matrix of a random regular graph is invertible with high probability. Note that for directed graphs this was recently proved by J. Huang [“Invertibility of adjacency matrices for random d-regular directed graphs”, Preprint, arXiv:1806.01382]. It also gives an alternate proof of a theorem of Backhausz and B. Szegedy [Random Struct. Algorithms 53, No. 3, 389–416 (2018; Zbl 1401.05267)].
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 15B52 | Random matrices (algebraic aspects) |
| 60B20 | Random matrices (probabilistic aspects) |
References:
| [1] | Abert Mikl\'os Ab\'ert, 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 · Zbl 1363.05118 |
| [2] | Backhausz, \'{A}gnes; Szegedy, Bal\'{a}zs, On large-girth regular graphs and random processes on trees, Random Structures Algorithms, 53, 3, 389-416 (2018) · Zbl 1401.05267 · doi:10.1002/rsa.20769 |
| [3] | Bardenet, R\'{e}mi; Maillard, Odalric-Ambrym, Concentration inequalities for sampling without replacement, Bernoulli, 21, 3, 1361-1385 (2015) · Zbl 1388.60055 · doi:10.3150/14-BEJ605 |
| [4] | Bhargava, Manjul; Kane, Daniel M.; Lenstra, Hendrik W., Jr.; Poonen, Bjorn; Rains, Eric, Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves, Camb. J. Math., 3, 3, 275-321 (2015) · Zbl 1329.14071 · doi:10.4310/CJM.2015.v3.n3.a1 |
| [5] | Bhatia, Rajendra, Matrix analysis, Graduate Texts in Mathematics 169, xii+347 pp. (1997), Springer-Verlag, New York · Zbl 0863.15001 · doi:10.1007/978-1-4612-0653-8 |
| [6] | Bollob\'{a}s, B\'{e}la, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin., 1, 4, 311-316 (1980) · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8 |
| [7] | Clancy, Julien; Leake, Timothy; Payne, Sam, A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs, Exp. Math., 24, 1, 1-7 (2015) · Zbl 1310.05121 · doi:10.1080/10586458.2014.917443 |
| [8] | Clancy, Julien; Kaplan, Nathan; Leake, Timothy; Payne, Sam; Wood, Melanie Matchett, On a Cohen-Lenstra heuristic for Jacobians of random graphs, J. Algebraic Combin., 42, 3, 701-723 (2015) · Zbl 1325.05146 · doi:10.1007/s10801-015-0598-x |
| [9] | Cohen, H.; Lenstra, H. W., Jr., Heuristics on class groups of number fields. Number theory, Noordwijkerhout 1983, Noordwijkerhout, 1983, Lecture Notes in Math. 1068, 33-62 (1984), Springer, Berlin · Zbl 0558.12002 · doi:10.1007/BFb0099440 |
| [10] | Cover, Thomas M.; Thomas, Joy A., Elements of information theory, Wiley Series in Telecommunications, xxiv+542 pp. (1991), John Wiley & Sons, Inc., New York · Zbl 0762.94001 · doi:10.1002/0471200611 |
| [11] | Ellenberg, Jordan S.; Venkatesh, Akshay; Westerland, Craig, Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields, Ann. of Math. (2), 183, 3, 729-786 (2016) · Zbl 1342.14055 · doi:10.4007/annals.2016.183.3.1 |
| [12] | Farrell, Matthew; Levine, Lionel, CoEulerian graphs, Proc. Amer. Math. Soc., 144, 7, 2847-2860 (2016) · Zbl 1334.05025 · doi:10.1090/proc/12952 |
| [13] | Feller, William, An introduction to probability theory and its applications. Vol. II., Second edition, xxiv+669 pp. (1971), John Wiley & Sons, Inc., New York-London-Sydney · Zbl 0219.60003 |
| [14] | Friedman, Eduardo; Washington, Lawrence C., On the distribution of divisor class groups of curves over a finite field. Th\'{e}orie des nombres, Quebec, PQ, 1987, 227-239 (1989), de Gruyter, Berlin · Zbl 0693.12013 |
| [15] | Frieze, Alan, Random structures and algorithms. Proceedings of the International Congress of Mathematicians-Seoul 2014. Vol. 1, 311-340 (2014), Kyung Moon Sa, Seoul · Zbl 1373.05177 |
| [16] | Heath-Brown, D. R., The size of Selmer groups for the congruent number problem. II, Invent. Math., 118, 2, 331-370 (1994) · Zbl 0815.11032 · doi:10.1007/BF01231536 |
| [17] | Holroyd, Alexander E.; Levine, Lionel; M\'{e}sz\'{a}ros, Karola; Peres, Yuval; Propp, James; Wilson, David B., Chip-firing and rotor-routing on directed graphs. In and out of equilibrium. 2, Progr. Probab. 60, 331-364 (2008), Birkh\"{a}user, Basel · Zbl 1173.82339 · doi:10.1007/978-3-7643-8786-0\_17 |
| [18] | Huang Jiaoyang Huang, Invertibility of adjacency matrices for random d-regular directed graphs, 1806.01382 · Zbl 1390.15121 |
| [19] | Huang2 Jiaoyang Huang, Invertibility of adjacency matrices for random d-regular graphs, 1807.06465 |
| [20] | Janson, Svante, Random regular graphs: asymptotic distributions and contiguity, Combin. Probab. Comput., 4, 4, 369-405 (1995) · Zbl 0846.05076 · doi:10.1017/S0963548300001735 |
| [21] | J\'{a}rai, Antal A., Sandpile models, Probab. Surv., 15, 243-306 (2018) · Zbl 1409.60144 · doi:10.1214/14-PS228 |
| [22] | Koplewitz, Shaked, Sandpile groups and the coeulerian property for random directed graphs, Adv. in Appl. Math., 90, 145-159 (2017) · Zbl 1366.05048 · doi:10.1016/j.aam.2017.05.002 |
| [23] | Levine, Lionel; Propp, James, What is \(\dots\) a sandpile?, Notices Amer. Math. Soc., 57, 8, 976-979 (2010) · Zbl 1203.82061 |
| [24] | MacWilliams, Jessie, Orthogonal matrices over finite fields, Amer. Math. Monthly, 76, 152-164 (1969) · Zbl 0186.33702 · doi:10.2307/2317262 |
| [25] | McKay, Brendan D., Spanning trees in regular graphs, European J. Combin., 4, 2, 149-160 (1983) · Zbl 0517.05043 · doi:10.1016/S0195-6698(83)80045-6 |
| [26] | Molloy, M. S. O.; Robalewska, H.; Robinson, R. W.; Wormald, N. C., \(1\)-factorizations of random regular graphs, Random Structures Algorithms, 10, 3, 305-321 (1997) · Zbl 0974.05062 · doi:10.1002/(SICI)1098-2418(199705)10:\(3 |
| [27] | ngwood Hoi H. Nguyen and Melanie Matchett Wood, Cokernels of adjacency matrices of random \(r\)-regular graphs, 1806.10068 |
| [28] | Norine, Serguei; Whalen, Peter, Jacobians of nearly complete and threshold graphs, European J. Combin., 32, 8, 1368-1376 (2011) · Zbl 1230.05160 · doi:10.1016/j.ejc.2011.04.003 |
| [29] | Lyons, Russell, Asymptotic enumeration of spanning trees, Combin. Probab. Comput., 14, 4, 491-522 (2005) · Zbl 1076.05007 · doi:10.1017/S096354830500684X |
| [30] | Rudin, Walter, Principles of mathematical analysis, Second edition, ix+270 pp. (1964), McGraw-Hill Book Co., New York · Zbl 0148.02903 |
| [31] | Schrijver, Alexander, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, xii+471 pp. (1986), John Wiley & Sons, Ltd., Chichester · Zbl 0970.90052 |
| [32] | Vu, Van, Random discrete matrices. Horizons of combinatorics, Bolyai Soc. Math. Stud. 17, 257-280 (2008), Springer, Berlin · Zbl 1154.15024 · doi:10.1007/978-3-540-77200-2\_13 |
| [33] | Wood, Melanie Matchett, The distribution of sandpile groups of random graphs, J. Amer. Math. Soc., 30, 4, 915-958 (2017) · Zbl 1366.05098 · doi:10.1090/jams/866 |
| [34] | Wood, Melanie Matchett, Random integral matrices and the Cohen-Lenstra heuristics, Amer. J. Math., 141, 2, 383-398 (2019) · Zbl 1446.11170 · doi:10.1353/ajm.2019.0008 |
| [35] | personal Melanie Matchett Wood, Personal communication, 2018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
