Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-05T05:42:50.496Z Has data issue: false hasContentIssue false
  • English
  • Français

The Largest Eigenvalue of Sparse Random Graphs

Published online by Cambridge University Press:  28 January 2003

MICHAEL KRIVELEVICH  and
BENNY SUDAKOV
MICHAEL KRIVELEVICH
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@math.tau.ac.il)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: bsudakov@math.princeton.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 12 , Issue 1 , January 2003 , pp. 61 - 72
Copyright
2003 Cambridge University Press