Recent progress in combinatorial random matrix theory. (English) Zbl 1531.60012
This is a survey on combinatorial matrix theory from one of the masters of the subject. Combinatorial random matrices arise in applications such as of construction of low-density-parity-check codes, and are an interesting topic of in their own right. The field has a long and rich history whereas the survey focuses on recent developments. The author does not shy away from expressing his intuition and personal opinions which makes the text an enjoyable read.
The text is structured around two models of discrete random matrices created by Erdős-Rényi graphs and random regular graphs. Models are considered in symmetric and non-symmetric cases.
The structure of the text is as follows:
(1) Singularity probability of discrete random matrices, where the author discusses the long history of the problem and the recent proof of Tikhomirov.
(2) Singular probability: symmetric case: here author’s own results and related works are discussed in the symmetric case.
(3) Ranks and co-ranks: here the regime in Erdős-Rényi graphs are very sparse which makes the singularity question not so meaningful thus the main concern is obtaining bounds for rank and co-rank of random sparse matrices. This area has seen some important growth even in the last three years after the publication of the survey.
(4) Random regular graphs: this brief section gives a quick overall summary alongside with a theorem and a conjecture.
(5) Determinant and permanent: this part is relatively rich with several theorems and conjectures showcasing authors’ mastery of the matter.
(6) Spectral results: these consist of two very nice sections on spectrum of random graphs and its relation to structural properties.
(7) Sandpile groups and random graphs and miscellany. I personally find the conjectures presented in this part very interesting and would recommend them to anyone who is looking for a good problem to work on.
The text is structured around two models of discrete random matrices created by Erdős-Rényi graphs and random regular graphs. Models are considered in symmetric and non-symmetric cases.
The structure of the text is as follows:
(1) Singularity probability of discrete random matrices, where the author discusses the long history of the problem and the recent proof of Tikhomirov.
(2) Singular probability: symmetric case: here author’s own results and related works are discussed in the symmetric case.
(3) Ranks and co-ranks: here the regime in Erdős-Rényi graphs are very sparse which makes the singularity question not so meaningful thus the main concern is obtaining bounds for rank and co-rank of random sparse matrices. This area has seen some important growth even in the last three years after the publication of the survey.
(4) Random regular graphs: this brief section gives a quick overall summary alongside with a theorem and a conjecture.
(5) Determinant and permanent: this part is relatively rich with several theorems and conjectures showcasing authors’ mastery of the matter.
(6) Spectral results: these consist of two very nice sections on spectrum of random graphs and its relation to structural properties.
(7) Sandpile groups and random graphs and miscellany. I personally find the conjectures presented in this part very interesting and would recommend them to anyone who is looking for a good problem to work on.
Reviewer: Alperen Ali Ergur (Pittsburgh)
MSC:
| 60B20 | Random matrices (probabilistic aspects) |
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
| 60-02 | Research exposition (monographs, survey articles) pertaining to probability theory |
| 05C80 | Random graphs (graph-theoretic aspects) |
Keywords:
Erdős-Rényi graphs; random regular graphs; probabilistic combinatorics; combinatorial random matrix theory; random sparse matricesReferences:
| [1] | L. Addario-Berry and L. Eslava, Hitting time theorems for random matrices, Combinatorics, Probability and Computing 23 (2014), 635-669. · Zbl 1310.15068 |
| [2] | O. Ahmadi, N. Alon, I. Blake, and I. Shparlinski, Graphs with integral spectrum, Linear Algebra and its Applications 430 (2009), 547-552. · Zbl 1178.05060 |
| [3] | N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83-96. · Zbl 0661.05053 |
| [4] | N. Alon and J. Spencer, The probabilistic method, 3rd ed., John Wiley & Sons Inc., Hoboken, NJ, 2008. · Zbl 1148.05001 |
| [5] | R. Arratia and S. DeSalvo, On the singularity of random Bernoulli matrices: Novel integer partitions and lower bound expansions, Ann. Comb. 17 (2013), no. 2, 251-274. · Zbl 1320.60020 |
| [6] | Z. Bai and J. Silverstein, Spectral analysis of large dimensional random matrices. Second edition. Springer Series in Statistics. Springer, New York, 2010. · Zbl 1301.60002 |
| [7] | L. Babai, D. Grigoryev, and D. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 310-324 (1982). |
| [8] | A. Basak and M. Rudelson, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs, arXiv:1809.08454. · Zbl 1468.05275 |
| [9] | B. Bollobás, Random graphs. Second edition, Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. · Zbl 0979.05003 |
| [10] | C. Bordenave, M. Lelarge, and J. Salez, The rank of diluted random graphs, Ann. Probab. 39 (2011), no. 3, 1097-1121. · Zbl 1298.05283 |
| [11] | C. Bordenave, A new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts. To appear in Annales Scientifiques de l’Ecole Normale Supérieure, arxiv:1502.04482. · Zbl 1462.05324 |
| [12] | P. Bourgade and K. Mudy, Gaussian fluctuations of the determinant of Wigner Matrices, Electronic Journal of Probability 24 (2019), no. 96. · Zbl 1448.60017 |
| [13] | J. Bourgain, V. Vu and P. M. Wood, On the singularity probability of discrete random matrices, J. Funct. Anal. 258 (2010), no. 2, 559-603. · Zbl 1186.60003 |
| [14] | M. Campos, L. Mattos, R. Morris, and N. Morrison, On the singularity of random symmetric matrices, arXiv:1904.11478. |
| [15] | F. Chung, R. Graham, and R. Wilson, Quasi-random graphs. Combinatorica 9 (1989), no. 4, 345-362. · Zbl 0715.05057 |
| [16] | F. Chung, Spectral graph theory, CBMS Series, no. 92 (1997). · Zbl 0867.05046 |
| [17] | J. Clancy, T. Leake, N. Kaplan, S. Payne, and M. Matchett Wood, On a Cohen-Lenstra heuristic for Jacobians of random graphs, J. Algebraic Combin. 42 (2015), no. 3, 701-723. · Zbl 1325.05146 |
| [18] | A. Coja-Oghlan, A. Ergür, P. Gao, S. Hetterich, and M. Rolvien, The rank of sparse random matrices, arXiv:1906.05757. · Zbl 07304058 |
| [19] | N. Cook. On the singularity of adjacency matrices for random regular digraphs, Probab. Theory Related Fields 167 (2017) 143-200. · Zbl 1365.05260 |
| [20] | K. Costello, Bilinear and quadratic variants on the Littlewood-Offord problem, Israel J. Math. 194 (2013), no. 1, 359-394. · Zbl 1317.60051 |
| [21] | K. Costello and V. Vu, The ranks of random graphs. Random Structures and Algorithm. 33 (2008), 269-285. · Zbl 1194.05083 |
| [22] | K. Costello and V. Vu, The rank of sparse random matrices, Combin. Probab. Comput. 19 (2010), no. 3, 321-342. · Zbl 1204.15042 |
| [23] | K. Costello, T. Tao, and V. Vu, Random symmetric matrices are almost surely singular, Duke Math. J. 135 (2006), no. 2, 395-413. · Zbl 1110.15020 |
| [24] | K. Costello and P. Williams, On the number of integral graphs, Linear Algebra and its Applications 493 (2016), 447-454. · Zbl 1329.05186 |
| [25] | Y. Dekel, J. R. Lee, and N. Linial, Eigenvectors of random graphs: Nodal domains, Random Structures and Algorithms 39 (2011), no. 1, 39-58. · Zbl 1223.05275 |
| [26] | A. Deneanu and V. Vu, Random matrices: Probability of normality, Advances of Mathematics 346 (2019), 887-907. · Zbl 1448.60020 |
| [27] | A. Edelman, E. Kostlan, and M. Shub, How many eigenvalues of a random matrix are real? J. Amer. Math. Soc. 7 (1994), no. 1, 247-267. · Zbl 0790.15017 |
| [28] | P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902. · Zbl 0063.01270 |
| [29] | A. Ferber and V. Jain, Singularity of random symmetric matrices: a combinatorial approach to improved bounds, Forum of Mathematics, Sigma, accepted for publication. · Zbl 1423.60016 |
| [30] | A. Ferber, V. Jain, and Y. Zhao, On the number of Hadamard matrices via anti-concentration, arXiv:1808.07222. |
| [31] | A. Ferber, K. Luh, and G. McKinley, Resilience of the rank of random matrices, arXiv:1910.03619. · Zbl 1467.15031 |
| [32] | J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Technical Report CX-TR-172-88, Princeton University, August 1988. |
| [33] | J. Fiedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100 pp. · Zbl 1177.05070 |
| [34] | J. Friedman and D. E. Kohler, The relativized second eigenvalue conjecture of Alon, arXiv:1403.3462. |
| [35] | A. Frieze, Random structures and algorithms. In: Proceedings of the International Congress of Mathematicians, Seoul 2014. Vol. 1, pages 311-340. Kyung Moon Sa, Seoul, 2014. · Zbl 1373.05177 |
| [36] | V. L. Girko, A refinement of the central limit theorem for random determinants. (Russian) Teor. Veroyatnost. i Primenen. 42 (1997), no. 1, 63-73; translation in Theory Probab. Appl. 42 (1997), no. 1, 121-129 (1998). · Zbl 0923.60027 |
| [37] | V. L. Girko, A central limit theorem for random determinants. Teor. Veroyatnost. i Mat. Statist. 21 (1979), 35-39, 164. · Zbl 0412.60033 |
| [38] | G. Halász, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197-211. · Zbl 0336.10050 |
| [39] | J. Huang, Invertibility of adjacency matrices for random d-regular graphs, arXiv:1807.06465 (2018). |
| [40] | J. Huang, Invertibility of adjacency matrices for random d-regular directed graphs, arXiv:1806.01382 (2018). |
| [41] | H. Huang and M. Rudelson, Size of nodal domains of the eigenvectors of a \[G(n,p)\] graph, arXiv:1905.00447. · Zbl 1453.05060 |
| [42] | S. Ge, PhD Thesis, UCLA 2017, https://escholarship.org/content/qt1n54260. |
| [43] | A. Irmatov, Singularity of \[\pm 1\]-matrices and asymptotics of the number of threshold functions, arXiv:2004.03400. |
| [44] | J. Kahn and E. Szemerédi, STOC 1989. |
| [45] | J. Kahn, J. Komlós, and E. Szemerédi, On the probability that a random \[\pm 1\] matrix is singular, J. Amer. Math. Soc. 8 (1995), 223-240. · Zbl 0829.15018 |
| [46] | J. Komlós, On the determinant of \[(0,1)\] matrices, Studia Sci. Math. Hungar. 2 (1967), 7-22. · Zbl 0153.05002 |
| [47] | J. Komlós, On the determinant of random matrices,Studia Sci. Math. Hungar. 3 (1968), 387-399. · Zbl 0226.60048 |
| [48] | M. Krivelevich and B. Sudakov, Pseudo-random graphs. In: More Sets, Graphs and Numbers, 199-262, Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006. · Zbl 1098.05075 |
| [49] | B. Landon, P. Sosoe, and H.-T. Yau, Fixed energy universality of Dyson Brownian motion, arXiv:1609.09011 (2016). · Zbl 1417.82019 |
| [50] | A. Litvalk and K. Tikhomirov, Singularity of random sparse Bernoulli matrices, arXiv:2004.03131. |
| [51] | A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef, Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl. 445 (2017), 1447-1491. · Zbl 1344.05126 |
| [52] | A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef, The rank of random regular digraphs of constant degree, Journal of Complexity 48 (2018), 103-110. · Zbl 1392.05100 |
| [53] | A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef, The smallest singular value of a shifted \(d\)-regular random square matrix, Prob. Th. Rel. Fields 173 (2019), 1301-1347. · Zbl 1411.60015 |
| [54] | A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8(3) (1988), 261-277. · Zbl 0661.05035 |
| [55] | J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III, Rec. Math. [Mat. Sbornik] N.S. 12 (1943), 277-286. · Zbl 0061.01801 |
| [56] | K. Luh and S. O’Rourke, Eigenvectors and controllability of non-Hermitian random matrices and directed graphs, arXiv:2004.10543. |
| [57] | K. Maples, Singularity of random matrices over finite fields, arXiv:1012.2372 (2010). |
| [58] | K. Maples, Cokernels of random matrices satisfy the Cohen-Lenstra heuristics, arXiv:1301.1239 (2013). |
| [59] | A. Marcus, D. Spielman, and N. Srivastava, Interlacing families I: bipartite Ramanujan graphs of all degrees, Ann. of Math. 182 (2015), no. 1, 307-325. · Zbl 1316.05066 |
| [60] | G. A. Margulis, Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators, Problemy Peredachi Informatsii 24 (1988), 51-60 [in Russian]. · Zbl 0708.05030 |
| [61] | A. Mészáros. The distribution of sandpile groups of random regular graphs, arXiv:1806.03736 (2018). · Zbl 1475.05156 |
| [62] | S. Miller, T. Novikoff, and A. Sabelli, The distribution of the largest non-trivial eigenvalues in families of random regular graphs, arXiv:math/0611649. |
| [63] | H. Nguyen, On the least singular value of random symmetric matrices, Electron. J. Probab. 17 (2012), no. 53. · Zbl 1251.15014 |
| [64] | H. Nguyen, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Math. J. 161 (2012), no. 4, 545-586. · Zbl 1276.15019 |
| [65] | H. Nguyen, T. Tao, and V. Vu, Random matrices: tail bounds for gaps between eigenvalues, Probability Theory and Related Fields 167 (2017), no. 3, 777-816. · Zbl 1391.15111 |
| [66] | H. Nguyen and V. Vu, Small probability, inverse theorems, and applications, In: Erdos’ 100th Anniversary Proceeding, Bolyai Society Mathematical Studies, vol. 25 (2013). · Zbl 1293.05037 |
| [67] | H. Nguyen and V. Vu, Random matrices: Law of the determinant, Annals of Probability 42 (2014), no. 1, 146-167. · Zbl 1299.60005 |
| [68] | H. Nguyen and M. M. Wood, Random integral matrices: universality of surjectivity and the cokernel, https://people.math.osu.edu/nguyen.1261/cikk/CL-Laplacian.pdf. |
| [69] | S. O’Rourke, V. Vu, K. Wang, Eigenvectors of random matrices: A survey, Journal of Combinatorial Theory, Series A 144 (2016), 361-442. · Zbl 1347.15044 |
| [70] | D. Puder, Expansion of random graphs: new proofs, new results, Inventiones Mathematicae 201 (2015), 845-908. · Zbl 1320.05115 |
| [71] | M. Rudelson and R. Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600-633. · Zbl 1139.15015 |
| [72] | A. Sárközy and E. Szemerédi, Uber ein Problem von Erdös und Moser, Acta Arithmetica 11 (1965) 205-208. · Zbl 0134.27801 |
| [73] | B. Sudakov and V. Vu, Local resilience of graphs, Random Structures Algorithms 33 (2008), no. 4, 409-433. · Zbl 1182.05114 |
| [74] | T. Tao and V. Vu, A central limit theorem for the determinant of a Wigner matrix, Adv. Math. 231 (2012), no. 1, 74-101. · Zbl 1248.60011 |
| [75] | T. Tao and V. Vu, On random \[\pm 1\] matrices: Singularity Determinant, Random Structures Algorithms 28 (2006), no. 1, 1-23. · Zbl 1086.60008 |
| [76] | T. Tao and V. Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603-628. · Zbl 1116.15021 |
| [77] | T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Math. 169 (2009), 595-632. · Zbl 1250.60023 |
| [78] | T. Tao and V. Vu, On the permanent of random Bernoulli matrices, Advances in Mathematics 220 (2009), 657-669. · Zbl 1229.05265 |
| [79] | T. Tao and V. Vu, Random matrices: universality of local spectral statistics of non-Hermitian matrices, Annals of Probability 43 (2015), no. 2, 782-874. · Zbl 1316.15042 |
| [80] | T. Tao and V. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. · Zbl 1127.11002 |
| [81] | T. Tao and V. Vu, Random matrices have simple spectrum, Combinatorica 37 (2017), 539-553. · Zbl 1399.60008 |
| [82] | K. Tikhomirov, Singularity of random Bernoulli matrices, Annals of Mathematics 191 (2020), 593-634. · Zbl 1458.15023 |
| [83] | L. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (1979), no. 2, 189-201. · Zbl 0415.68008 |
| [84] | R. Vershynin, Invertibility of symmetric random matrices, Random Structures and Algorithms 44 (2014), 135-182. · Zbl 1291.15088 |
| [85] | V. Vu, Random discrete matrices. In: Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, pages 257-280. Springer, Berlin, 2008. · Zbl 1154.15024 |
| [86] | V. Vu, Combinatorial problems in random matrix theory. In: Proceedings of the International Congress of Mathematicians, Seoul 2014, vol. IV, pages 489-508. Kyung Moon Sa, Seoul, 2014. · Zbl 1373.05201 |
| [87] | M. M. Wood, The distribution of sandpile groups of random graphs, Journal of the A.M.S. 30 (2017), 915-958. · Zbl 1366.05098 |
| [88] | M. M. Wood, Random integral matrices and the Cohen-Lenstra Heuristics, to appear in American Journal of Mathematics, arXiv:1504.04391. · Zbl 1446.11170 |
| [89] | N. C. Wormald, Models of random regular graphs. In: Surveys in Combinatorics, 1999, J. D. Lamb and D. A. Preece (eds.), pages 239-298. · Zbl 0935.05080 |
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.
