Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

The evolution of random graphs


Author: Béla Bollobás
Journal: Trans. Amer. Math. Soc. 286 (1984), 257-274
MSC: Primary 05C80; Secondary 60C05
MathSciNet review: 756039
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: According to a fundamental result of Erdös and Rényi, the structure of a random graph $ {G_M}$ changes suddenly when $ M \sim n/2$: if $ M = \left\lfloor {cn} \right\rfloor $ and $ c < \frac{1}{2}$ then a.e. random graph of order $ n$ and since $ M$ is such that its largest component has $ O(\log n)$ vertices, but for $ c > \frac{1}{2}$ a.e. $ {G_M}$ has a giant component: a component of order $ (1-{\alpha _c}+o(1))n$ where $ {\alpha _c} < 1$. The aim of this paper is to examine in detail the structure of a random graph $ {G_M}$ when $ M$ is close to $ n/2$. Among others it is proved that if $ M = n/2 + s$, $ s = o(n)$ and $ s \geq {(\log n)^{1/2}}{n^{2/3}}$ then the giant component has $ (4 + o(1))s$ vertices. Furthermore, rather precise estimates are given for the order of the $ r$th largest component for every fixed $ r$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C80, 60C05

Retrieve articles in all journals with MSC: 05C80, 60C05


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1984-0756039-5
PII: S 0002-9947(1984)0756039-5
Article copyright: © Copyright 1984 American Mathematical Society