Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs
DOI:
https://doi.org/10.15407/mag18.03.382Анотація
Скориставшись результатами про концентрацiю найбiльшого власного значення i максимального степеня вершини великих випадкових графiв, ми доводимо, що нескiнченна послiдовнiсть випадкових графiв Ердоша–Реньї G(n,ρn/n) така, що ρn/log n нескiнченно зростає, коли n→∞, задовольняє версiю гiпотези Рiмана для теорiї графiв.
Mathematical Subject Classification 2010: 05C80,11M50,15B52,60B20
Ключові слова:
випадковi графи, випадковi матрицi, дзета функцiя Iхари, гiпотеза Рiмана для теорiї графiвПосилання
N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83-96. https://doi.org/10.1007/BF02579166
H. Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717-797. https://doi.org/10.1142/S0129167X92000357
F. Benaych-Georges, C. Bordenave, and A. Knowles, Spectral radii of sparse random matrices, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 3, 2141-2161. https://doi.org/10.1214/19-AIHP1033
B. Bollobaś, Random graphs, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2001.
C. Bordenave, M. Lelarge,and L. Massoulié, Nonbacktracking spectrum of random graphs: community detection and nonregular ramanujan graphs, Ann. Probab. 46 (2018), 1-71. https://doi.org/10.1214/16-AOP1142
S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: a nonasymptotic theory of independence, Oxford University Press, Oxford, 2013. https://doi.org/10.1093/acprof:oso/9780199535255.001.0001
D. Chafai, Singular values of random matrices, available from: https://djalil.chafai.net/docs/sing.pdf
F.R.K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (1989), 187-196. https://doi.org/10.1090/S0894-0347-1989-0965008-X
S. Coste and Y. Zhu, Eigenvalues of the non-backtracking operator detached from the bulk, Random Matrices Theory Appl. 10 (2021), 2150028. https://doi.org/10.1142/S2010326321500283
P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290-297. https://doi.org/10.5486/PMD.1959.6.3-4.12
Expanding graphs (Ed. J. Friedman), DIMACS Series on Discrete Math. and Theor. Comput. Sci., 10, Amer. Math. Soc., Providence, RI, 1993.
D. Foata and D. Zeilberger, A combinatorial proof of Bass's evaluations of the Ihara-Selberg zeta function for graphs, Trans. Amer. Math. Soc. 351 (1999), 2257-2274. https://doi.org/10.1090/S0002-9947-99-02234-5
J. Friedman, On the second eigenvalue and random walks in random d-regular graphs, Combinatorica 11 (1991), 331-362. https://doi.org/10.1007/BF01275669
J. Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), 910. https://doi.org/10.1090/memo/0910
Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), 233-241. https://doi.org/10.1007/BF02579329
K. Hashimoto, Zeta functions of finite graphs and representation of p-adic groups, Adv. Stud. Pure Math. 15 (1989), 211-280. https://doi.org/10.2969/aspm/01510211
R.A. Horn and C.R. Johnson, Matrix analysis, Cambridge University Press, 1985. https://doi.org/10.1017/CBO9780511810817
M.D. Horton, H.M. Stark, and A.A. Terras, What are zeta functions of graphs and what are they good for? Contemporary Mathematics 415 (2006), 173-190. https://doi.org/10.1090/conm/415/07868
Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math. Soc. Japan 18 (1966) 219-235. https://doi.org/10.2969/jmsj/01830219
O. Khorunzhiy, On eigenvalue distribution of random matrices of Ihara zeta function of large random graphs, J. Math. Phys. Anal. Geom. 13 (2017), 268-282. https://doi.org/10.15407/mag13.03.268
O. Khorunzhiy, On asymptotic properties of Bell polynomials and concentration of vertex degree of large random graphs, J. Theor. Probab. 35 (2022), 20-51. https://doi.org/10.1007/s10959-020-01025-w
M. Krivelevich and B. Sudakov, The largest eigenvalue of sparse random graphs, Combin. Probab. Comput. 12 (2003), 61-72. https://doi.org/10.1017/S0963548302005424
A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277. https://doi.org/10.1007/BF02126799
A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in combinatorics, London Math. Soc. Lecture Notes 18 (1995), 155-189. https://doi.org/10.1017/CBO9780511662096.008
G. Lugosi, S. Mendelson, and N. Zhivotovsky, Concentration of the spectral norm of Erdős-Rényi random graphs, Bernoulli, 26 (2020), 2253-2274. https://doi.org/10.3150/19-BEJ1192
M. Ram Murty, Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003), 1-20.
G. Quenell, Spectral diameter estimates for k-regular graphs, Advances in Math. 106 (1994) 122-148. https://doi.org/10.1006/aima.1994.1052
H.M. Stark and A.A. Terras, Zeta Functions of Finite Graphs and Coverings, Adv. Math. 121 (1996), 124-165. https://doi.org/10.1006/aima.1996.0050
T. Tao, Eigenvalues and sums of Hermitian matrices, 254A, Notes 3a, available from: https://terrytao.wordpress.com/tag/weyl-inequalities/.
A. Terras, Zeta functions of graphs: a stroll through the garden, Cambridge Studies in Advanced Mathematics, 128, Cambridge University Press, Cambridge, 2011. https://doi.org/10.1017/CBO9780511760426
K. Wang and P.M. Wood, Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi graph, preprint, https://arxiv.org/abs/1710.11015
