CoChat

The Largest Eigenvalue of Sparse Random Graphs

Open access
KRIVELEVICH, MICHAEL, SUDAKOV, BENNY · 2003 · Combinatorics, Probability and Computing

The 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

Crossref · 10.1017/s0963548302005424

Cites

15 of 15 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 0 Not valid · 7 Not checked · 10 Own results and interpretations

10 more claims

Create a free account to see all 17 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 1
  • It may state two separate claims as one. 1

Create a free account to see these claims.

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.

1 of 1

Citations

Cites

Show all 15 references

Research works printed but not linked: 1

  1. [13][13] M. L. Mehta, Random matrices , Academic Press, New York, 1991.

Cited by

See all 213

Metadata

Authors
KRIVELEVICH, M., & SUDAKOV, B.
Affiliations
Tel Aviv University (IL)
Venue
Combinatorics, Probability and Computing
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
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.