Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs. (English) Zbl 1504.05261
Summary: We consider an inhomogeneous Erdős-Rényi random graph \(G_N\) with vertex set \([N] = \{1,\dots ,N\}\) for which the pair of vertices \(i,j \in [N], i\ne j\), is connected by an edge with probability \(r(\tfrac{i}{N},\tfrac{j}{N})\), independently of other pairs of vertices. Here, \(r:\,[0,1]^2 \rightarrow (0,1)\) is a symmetric function that plays the role of a reference graphon. Let \(\lambda_N\) be the maximal eigenvalue of the adjacency matrix of \(G_N\). It is known that \(\lambda_N/N\) satisfies a large deviation principle as \(N \rightarrow \infty \). The associated rate function \(\psi_r\) is given by a variational formula that involves the rate function \(I_r\) of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of \(\psi_r\), specially when the reference graphon is of rank 1.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C35 | Extremal problems in graph theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 60F10 | Large deviations |
| 46L54 | Free probability and free operator algebras |
Keywords:
inhomogeneous Erdős-Rényi random graph; adjacency matrix; largest eigenvalue; large deviation principle; rate function; graphonReferences:
| [1] | F. Augeri. Large deviations principle for the largest eigenvalue of Wigner matrices without Gaussian tails. Electron. J. Probab., 21:Paper No. 32, 49, 2016. 10.1214/16-EJP4146. URL doi:10.1214/16-EJP4146 · Zbl 1338.60010 |
| [2] | Augeri, F.; Guionnet, A.; Husson, J., Large deviations for the largest eigenvalue of sub-Gaussian matrices, Commun. Math. Phys., 383, 997-1050 (2021) · Zbl 1479.60011 · doi:10.1007/s00220-021-04027-9 |
| [3] | M. Bauer and O. Golinelli. Random incidence matrices: moments of the spectral density. J. Statist. Phys., 103(1-2):301-337, 2001. ISSN 0022-4715. 10.1023/A:1004879905284. URL doi:10.1023/A:1004879905284 · Zbl 0999.82035 |
| [4] | G. Ben Arous and A. Guionnet. Large deviations for Wigner’s law and Voiculescu’s non-commutative entropy. Probab. Theory Related Fields, 108(4):517-542, 1997. ISSN 0178-8051. https://doi.org/10.1007/s004400050119. URL doi:10.1007/s004400050119 · Zbl 0954.60029 |
| [5] | G. Ben Arous, A. Dembo, and A. Guionnet. Aging of spherical spin glasses. Probab. Theory Related Fields, 120(1):1-67, 2001. ISSN 0178-8051. doi:10.1007/PL00008774. URL doi:10.1007/PL00008774 · Zbl 0993.60055 |
| [6] | F. Benaych-Georges, C. Bordenave, and A. Knowles. Largest eigenvalues of sparse inhomogeneous Erdős-Rényi random graphs. Ann. Probab., 47(3):1653-1676, 2019. ISSN 0091-1798. doi:10.1214/18-AOP1293. URL doi:10.1214/18-AOP1293 · Zbl 1447.60017 |
| [7] | S. Bhamidi, S. N. Evans, and A. Sen. Spectra of large random trees. J. Theoret. Probab., 25(3):613-654, 2012. ISSN 0894-9840. 10.1007/s10959-011-0360-9. URL doi:10.1007/s10959-011-0360-9 · Zbl 1255.05114 |
| [8] | C. Bordenave and P. Caputo. A large deviation principle for Wigner matrices without Gaussian tails. Ann. Probab., 42(6):2454-2496, 2014. ISSN 0091-1798. 10.1214/13-AOP866. URL doi:10.1214/13-AOP866 · Zbl 1330.60012 |
| [9] | C. Bordenave and M. Lelarge. Resolvent of large random graphs. Random Structures Algorithms, 37(3):332-352, 2010. ISSN 1042-9832. 10.1002/rsa.20313. URL doi:10.1002/rsa.20313 · Zbl 1209.05222 |
| [10] | A. Chakrabarty, R. S. Hazra, F. den Hollander, and M. Sfragara. Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs. Random Matrices: Theory and Applications,Vol. 10, No. 01, 2150009 (2021) URL doi:10.1142/S201032632150009X · Zbl 1478.05133 |
| [11] | Chakrabarty, A.; Chakraborty, S.; Hazra, RS, Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs, J. Stat. Phys., 181, 1746-1780 (2020) · Zbl 1460.05169 · doi:10.1007/s10955-020-02644-7 |
| [12] | Chatterjee, S.: Large Deviations for Random Graphs. Lecture Notes in Mathematics, vol. 2197. Springer, Cham (2017) · Zbl 1375.60009 |
| [13] | S. Chatterjee and S. R. S. Varadhan. The large deviation principle for the Erdős-Rényi random graph. European J. Combin., 32(7):1000-1017, 2011. ISSN 0195-6698. URL doi:10.1016/j.ejc.2011.03.014 · Zbl 1230.05259 |
| [14] | Deimling, K.: Nonlinear Functional Analysis. Springer-Verlag, Berlin (1985) · Zbl 0559.47040 |
| [15] | A. Dembo and E. Lubetzky. Empirical spectral distributions of sparse random graphs. arXiv preprint arXiv:1610.05186, 2016 · Zbl 1473.05282 |
| [16] | F. den Hollander. Large Deviations, volume 14 of Fields Institute Monographs. American Mathematical Society, Providence, RI, 2000. ISBN 0-8218-1989-5 · Zbl 0949.60001 |
| [17] | S. Dhara and S. Sen. Large deviation for uniform graphs with given degrees. arXiv preprint arXiv:1904.07666, 2019 · Zbl 1525.05168 |
| [18] | X. Ding and T. Jiang. Spectral distributions of adjacency and Laplacian matrices of random graphs. Ann. Appl. Probab., 20(6):2086-2117, 2010. ISSN 1050-5164. 10.1214/10-AAP677. URL doi:10.1214/10-AAP677 · Zbl 1231.05236 |
| [19] | M. Disertori, F. Merkl, and S. W. W. Rolles. Localization for a nonlinear sigma model in a strip related to vertex reinforced jump processes. Comm. Math. Phys., 332(2):783-825, 2014. ISSN 0010-3616. 10.1007/s00220-014-2102-1. URL doi:10.1007/s00220-014-2102-1 · Zbl 1307.82013 |
| [20] | I. Dumitriu and S. Pal. Sparse regular random graphs: spectral density and eigenvectors. Ann. Probab., 40(5):2197-2235, 2012. ISSN 0091-1798. 10.1214/11-AOP673. URL doi:10.1214/11-AOP673 · Zbl 1255.05173 |
| [21] | Farkas, IJ; Derényi, I.; Barabási, A-L; Vicsek, T., Spectra of ?real-world? graphs: Beyond the semicircle law, Phys. Rev. E, 64, 2, 026704 (2001) · doi:10.1103/PhysRevE.64.026704 |
| [22] | T. Jiang. Empirical distributions of Laplacian matrices of large dilute random graphs. Random Matrices Theory Appl., 1(3):1250004, 20, 2012a. ISSN 2010-3263. 10.1142/S2010326312500049. URL doi:10.1142/S2010326312500049 · Zbl 1252.05199 |
| [23] | T. Jiang. Low eigenvalues of Laplacian matrices of large random graphs. Probab. Theory Related Fields, 153(3-4):671-690, 2012b. ISSN 0178-8051. 10.1007/s00440-011-0357-4. URL doi:10.1007/s00440-011-0357-4 · Zbl 1251.05098 |
| [24] | O. Khorunzhy, M. Shcherbina, and V. Vengerovsky. Eigenvalue distribution of large weighted random graphs. J. Math. Phys., 45(4):1648-1672, 2004. ISSN 0022-2488. 10.1063/1.1667610. URL doi:10.1063/1.1667610 · Zbl 1068.05062 |
| [25] | J. O. Lee and K. Schnelli. Local law and Tracy-Widom limit for sparse random matrices. Probab. Theory Related Fields, 171(1-2):543-616, 2018. ISSN 0178-8051. doi:10.1007/s00440-017-0787-8 · Zbl 1429.60012 |
| [26] | L. Lovász. Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012. ISBN 978-0-8218-9085-1. 10.1090/coll/060. URL doi:10.1090/coll/060 · Zbl 1292.05001 |
| [27] | E. Lubetzky and Y. Zhao. On replica symmetry of large deviations in random graphs. Random Structures Algorithms, 47(1):109-146, 2015. ISSN 1042-9832. 10.1002/rsa.20536. URL doi:10.1002/rsa.20536 · Zbl 1348.05195 |
| [28] | M. J. R. Markering. The large deviation principle for inhomogeneous Erdős-Rényi random graphs. Bachelor thesis Leiden University, May 2020 · Zbl 1515.05161 |
| [29] | F. Sauvigny. Partial Differential Equations. 2. Universitext. Springer-Verlag London, Ltd., London, 2012. ISBN 978-1-4471-2983-7. 10.1007/978-1-4471-2984-4. URL doi:10.1007/978-1-4471-2984-4. Functional analytic methods, With consideration of lectures by E. Heinz, Second revised and enlarged edition of the 2006 translation · Zbl 1198.35002 |
| [30] | L. V. Tran, V. H. Vu, and K. Wang. Sparse random graphs: eigenvalues and eigenvectors. Random Structures Algorithms, 42(1):110-134, 2013. ISSN 1042-9832. 10.1002/rsa.20406. URL doi:10.1002/rsa.20406 · Zbl 1257.05089 |
| [31] | Y. Zhu. A graphon approach to limiting spectral distributions of Wigner-type matrices. Random Structures Algorithms, 56(1):251-279, 2020. ISSN 1042-9832. 10.1002/rsa.20894. URL doi:10.1002/rsa.20894 · Zbl 1442.05214 |
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.
