The Largest Eigenvalue of Sparse Random Graphs
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index; none of the 6 sources its claims cite is checked for support yet.
Abstract
We prove that, for all values of the edge probability $p(n)$ , the largest eigenvalue of the random graph $G(n, p)$ satisfies almost surely $\lambda_1(G)=(1+o(1))\max\{\sqrt{\Delta}, np\}$ , where Δ is the maximum degree of $G$ , and the o (1) term tends to zero as $\max\{\sqrt{\Delta}, np\}$ tends to infinity.
Overview
CoChat Summary
TL;DR
The paper proves that for a random graph \(G(n,p)\), the largest eigenvalue satisfies almost surely \(\lambda_1(G)=(1+o(1))\max\{\sqrt{\Delta},np\}\), where \(\Delta\) is the maximum degree and the \(o(1)\) term tends to zero as \(\max\{\sqrt{\Delta},np\}\) tends to infinity. The proof matches the natural lower bound from stars and average degree with a corresponding upper bound.
Key findings
- Main theorem: for all edge probabilities \(p(n)\), almost surely \(\lambda_1(G(n,p))=(1+o(1))\max\{\sqrt{\Delta},np\}\), where \(\Delta\) is the maximum degree of \(G(n,p)\).
- The lower bound follows because \(G\) contains a star \(S_\Delta\), giving \(\lambda_1(G)\ge \sqrt{\Delta}\), and because \(\lambda_1(G)\) is at least the average degree; for \(p\gg 1/n^2\), the number of edges is a.s. \((1+o(1))n^2p/2\), giving \(\lambda_1(G)\ge (1+o(1))np\).
- Lemma 2.1 records sparse random graph structure: the maximum degree is a.s. \((1+o(1))\Delta_p\); if \(np\to 0\), \(G\) is a.s. a forest; if \(p\le e^{-(\log\log n)^2}/n\), all connected components are a.s. of size at most \((1+o(1))\Delta_p\); and if \(p\le \log^{1/2}n/n\), every vertex is a.s. in at most one cycle of length \(\le 4\).
- The paper also derives a corollary for the case \(p=c/n\), though the displayed formula is not decoded in the provided text.
Methods
- Theoretical probabilistic and combinatorial proof for the random graph \(G(n,p)\), using the adjacency matrix, graph eigenvalues, and spectral graph theory.
- The proof uses technical lemmas on sparse random graph structure, including \(\Delta_p\), maximum degree, forests, short cycles, and high-degree vertex sets, together with Proposition 3.1 bounds on \(\lambda_1\) for graphs, forests, and bipartite graphs.
- For the upper bound, the graph is partitioned into subgraphs \(G_1,\dots,G_6\), and \(\lambda_1(G)\) is bounded by summing or maximizing the largest eigenvalues of these subgraphs. No empirical data or simulations are used.
Limitations
- The paper states that obtaining more accurate estimates on the error term in Theorem 1.1 is an interesting open problem.
- The paper states that its proof methods do not allow locating the expectation of \(\lambda_1\) with high precision or obtaining a limit distribution, unlike the constant-\(p\) case of Füredi and Komlós.
- The paper lists further open questions: multiplicity and structure of the first eigenvector, the Laplacian spectrum of random graphs, and the spectral radius of dilute random matrices. Evident from the text: the main result is asymptotic, with an unquantified \(o(1)\) error term.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 0 Not valid · 7 Not checked · 10 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We prove that for all values of the edge probability p ( n ) the largest eigenvalue of a random graph G ( n, p ) satisfies almost surely: λ 1 ( G ) = (1 + o (1)) max { √ ∆ , np } , where ∆ is a maximal degree of G , and the o (1) term tends to zero as max { √ ∆ , np } tends to infinity.”
boostedstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Consider the case p = c/n , for a constant c > 0. Performing direct calculations similar to those of Section 2 of the present paper, one can show that in this case G ( n, p ) contains almost surely an unbounded collection of vertices of degree ∆( G )(1 -o (1)) at distance at least three from each other.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 2.2 Let p ≥ e -(log log n ) 2 /n and let X be the set of vertices of random graph G = G ( n, p ) with degree larger than np (1 + 1 / log log n ) + ∆ 1 / 3 p . Then”
- Also stated in: § 2 Some properties of sparse random graphs · p. 4 · plain
“( ii ) Almost surely every vertex in G has less than ∆ 7 / 8 p neighbors in X .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § 2 Some properties of sparse random graphs · p. 4 · plain
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 2.3 Let G = G ( n, p ) be a random graph with e -(log log n ) 2 /n ≤ p ≤ log 1 / 2 n/n . Then a.s. G contains no vertex which has at least ∆ 1 / 3 p other vertices of G with degree ≥ ∆ 3 / 4 p within distance at most two.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“( iii ) If p ≤ e -(log log n ) 2 /n , then almost surely all connected components of G are of size at most (1 + o (1))∆ p .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
10 more claims
Create a free account to see all 17 claims and every source verdict.
- Probably not a substantial claim. 1
- It may state two separate claims as one. 1
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 4 Concluding remarks · p. 11
“the spectral norm of the dilute random matrix is asymptotically equal to 2 √ np in the case p ( n ) ≫ log n/n (under some additional technical assumptions)”
§ 4 Concluding remarks · p. 11
“and it asymptotically much larger than √ np for p ( n ) ≪ log n .”
Citations
Cites
Bollobás, B. (1985) · Cited by 6,196
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524 · cited 1×
“dern Graph Theory. A serious effort has been invested in establishing connections between spectral characteristics of a graph and its other parameters. An interested reader can consult monographs [5], [4] for a detailed account of known results. The ability to compute graph eigenvalues efficiently (both from theoretical…”
ResultSpencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
Łuczak, T., Janson, S., & Ruciński, A. (2000) · Cited by 2,192
Spectra of graphs : theory and application
Cvetković, D., Doob, M., & Sachs, H. (1995) · Cited by 2,127
Janson, S., Łuczak, T., & Rucinski, A. (2000) · Wiley eBooks · doi:10.1002/9781118032718 · Cited by 1,545
cacute, C., Vs, M., Doob, M., & Sachs, H. (1980) · Cited by 1,478
Combinatorial Problems and Exercises
(1993) · Elsevier eBooks · doi:10.1016/c2009-0-09109-0 · Cited by 1,312
The eigenvalues of random symmetric matrices
Füredi, Z., & Komlós, J. (1981) · Combinatorica · doi:10.1007/bf02579329 · Cited by 633 · cited 2×
“In fact, much more is known for large enough values of p(n), Füredi and Komlós proved in [6] that for a constant p, λ1(G(n, p)) has asymptotically a normal distribution with expectation (n − 1)p + (1 − p) and variance 2p(1 − p).”
BackgroundMethodOn the concentration of eigenvalues of random symmetric matrices
Alon, N., Krivelevich, M., & Vu, V. H. (2002) · Israel Journal of Mathematics · doi:10.1007/bf02785860 · Cited by 133
Self-citation
Research works printed but not linked: 1
- [13][13] M. L. Mehta, Random matrices , Academic Press, New York, 1991.
Cited by
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
“However, in an uncorrelated random complex network, the maximum eigenvalue λmax is determined by the cutoff qcut(N) of the degree distribution, λmax ≈ q cut (N) (Chung et al., 2003; Dorogovtsev et al., 2003; Krivelevich and Sudakov, 2003).”
BackgroundThresholds for Epidemic Spreading in Networks
Castellano, C., & Pastor-Satorras, R. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.218701 · Cited by 721
Spectral redemption in clustering sparse networks
Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., & Zhang, P. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1312486110 · Cited by 638
“[18] Krivelevich M and Sudakov B (2003).”
BackgroundDorogovtsev, S. N., Goltsev, A. V., Mendes, J. F. F., & Samukhin, A. N. (2003) · Physical Review E · doi:10.1103/physreve.68.046109 · Cited by 280
Spectral Measure of Structural Robustness in Complex Networks
Wu, J., Barahona, M., Tan, Y.-J., & Deng, H.-Z. (2011) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/tsmca.2011.2116117 · Cited by 254
“It is well known that the largest eigenvalue λ1 of GN,p is almost surely Np[1 + o(1)] provided that Np ≥ lnN [45], [46].”
Background
Metadata
- Authors
- KRIVELEVICH, M., & SUDAKOV, B.
- Affiliations
- Tel Aviv University (IL)
- Venue
- Combinatorics, Probability and Computing
- Publisher
- Cambridge University Press (CUP)
- Published
- 2003-01
- Volume
- 12
- Issue
- 1
- Pages
- 61-72
- ISSN
- 0963-5483 (ISSN-L)
- 1469-2163
- OpenAlex
- W2003134180
- Cited by
- 207
- References
- 14
- Citations by year
- 2026: 9 · 2025: 6 · 2024: 11 · 2023: 9 · 2022: 39 · 2021: 14 · 2020: 10 · 2019: 13 · 2018: 3 · 2017: 12 · 2016: 9 · 2015: 8 · 2014: 4 · 2013: 8 · 2012: 10
- FWCI
- 10.01
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Combinatorics Probability Computing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (9987845, 0106589)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Keywords
- largest eigenvalue, sparse random graphs, edge probability, maximum degree, spectral radius, almost sure asymptotics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-10-29, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-29 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Largest Eigenvalue of Sparse Random Graphs. https://app.cochat.ai/papers/10.1017/s0963548302005424
- The paper
- KRIVELEVICH, M., & SUDAKOV, B. (2003). The Largest Eigenvalue of Sparse Random Graphs. Combinatorics, Probability and Computing. https://doi.org/10.1017/s0963548302005424
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.