×

The rank of random regular digraphs of constant degree. (English) Zbl 1392.05100

Summary: Let \(d\) be a (large) integer. Given \(n \geq 2 d\), let \(A_n\) be the adjacency matrix of a random directed \(d\)-regular graph on \(n\) vertices, with the uniform distribution. We show that the rank of \(A_n\) is at least \(n - 1\) with probability going to one as \(n\) grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of \(A_n\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Basak, A.; Rudelson, M., Invertibility of sparse non-Hermitian matrices, Adv. Math., 310, 426-483, (2017) · Zbl 1406.60013
[2] Bordenave, C.; Chafaï, D., Around the circular law, Probab. Surv., 9, 1-89, (2012) · Zbl 1243.15022
[3] Bordenave, C.; Lelarge, M.; Salez, J., The rank of diluted random graphs, Ann. Probab., 39, 3, 1097-1121, (2011) · Zbl 1298.05283
[4] Bourgain, J.; Vu, V. H.; Wood, P. M., On the singularity probability of discrete random matrices, J. Funct. Anal., 258, 2, 559-603, (2010) · Zbl 1186.60003
[5] Cook, N. A., On the singularity of adjacency matrices for random regular digraphs, Probab. Theory Related Fields, 167, 1, 143-200, (2017) · Zbl 1365.05260
[6] N.A. Cook, The circular law for random regular digraphs, preprint, arXiv:1703.05839; N.A. Cook, The circular law for random regular digraphs, preprint, arXiv:1703.05839 · Zbl 1370.05078
[7] Costello, K. P.; Tao, T.; Vu, V., Random symmetric matrices are almost surely nonsingular, Duke Math. J., 135, 2, 395-413, (2006) · Zbl 1110.15020
[8] Costello, K. P.; Vu, V., The rank of random graphs, Random Structures Algorithms, 33, 3, 269-285, (2008) · Zbl 1194.05083
[9] Frieze, A., Random structures and algorithms, (Proceedings ICM, Vol. 1, (2014)), 311-340 · Zbl 1373.05177
[10] Kahn, J.; Komlós, J.; Szemerédi, E., On the probability that a random \(\pm 1\)-matrix is singular, J. Amer. Math. Soc., 8, 1, 223-240, (1995) · Zbl 0829.15018
[11] Komlós, J., On the determinant of \((0, 1)\) matrices, Studia Sci. Math. Hungar., 2, 7-21, (1967) · Zbl 0153.05002
[12] J. Komlós, Circulated Manuscript, Available online at http://math.rutgers.edu/ komlos/01short.pdf; J. Komlós, Circulated Manuscript, Available online at http://math.rutgers.edu/ komlos/01short.pdf
[13] Litvak, A. E.; Lytova, A.; Tikhomirov, K.; Tomczak-Jaegermann, N.; Youssef, P., Anti-concentration property for random digraphs and invertibility of their adjacency matrices, C. R. Math. Acad. Sci. Paris, 354, 2, 121-124, (2016), MR3456885 · Zbl 1388.60039
[14] Litvak, A. E.; Lytova, A.; Tikhomirov, K.; Tomczak-Jaegermann, N.; Youssef, P., Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl., 445, 2, 1447-1491, (2017), MR3545253 · Zbl 1344.05126
[15] A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, Circular law for sparse random regular digraphs, submitted for publication, arXiv:1801.05576; A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, Circular law for sparse random regular digraphs, submitted for publication, arXiv:1801.05576 · Zbl 1388.60039
[16] A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, Structure of eigenvectors of random regular digraphs, submitted for publication, arXiv:1801.05575; A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, Structure of eigenvectors of random regular digraphs, submitted for publication, arXiv:1801.05575 · Zbl 1344.05126
[17] A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, The smallest singular value of a shifted \(d\) arXiv:1707.02635; A.E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, P. Youssef, The smallest singular value of a shifted \(d\) arXiv:1707.02635 · Zbl 1392.05100
[18] McKay, B. D., Subgraphs of random graphs with specified degrees, Congr. Numer., 33, 213-223, (1981)
[19] Nguyen, H. H., Inverse Littlewood-offord problems and the singularity of random symmetric matrices, Duke Math. J., 161, 545-586, (2012) · Zbl 1276.15019
[20] Nguyen, H. H., On the singularity of random combinatorial matrices, SIAM J. Discrete Math., 27, 447-458, (2013) · Zbl 1314.60029
[21] Tao, T.; Vu, V. H., On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc., 20, 3, 603-628, (2007) · Zbl 1116.15021
[22] Vershynin, R., Invertibility of symmetric random matrices, Random Structures Algorithms, 44, 135-182, (2014) · Zbl 1291.15088
[23] Vu, V., (Random Discrete Matrices, Horizons of Combinatorics, Bolyai Soc. Math. Stud., vol. 17, (2008), Springer Berlin), 257-280 · Zbl 1154.15024
[24] Vu, V., Combinatorial problems in random matrix theory, (Proceedings ICM, Vol. 4, (2014)), 489-508 · Zbl 1373.05201
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.