Remote Access Transactions of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9947-1984-0756039-5
MathSciNet review: 756039
Full-text PDF

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?)

  • [1] A. D. Barbour, Poisson convergence and random graphs, Math. Proc. Cambridge Philos. Soc. 92 (1982), 349-359. MR 671189 (84d:05141)
  • [2] B. Bollobás, Graph theory--An introductory course, Graduate Texts in Math., Springer-Verlag, New York, Heidelberg and Berlin, 1979. MR 536131 (80j:05053)
  • [3] -, Random graphs, Combinatorics (H. N. V. Temperley, ed.), London Math. Soc. Lecture Notes Series, vol. 52, Cambridge Univ. Press, New York, 1981, pp. 80-102. MR 633650 (83e:05039)
  • [4] -, The evolution of sparse graphs, Graph Theory and Combinatorics (B. Bollobás, ed.), Academic Press, London, 1984. MR 777163 (86i:05119)
  • [5] P. Erdös and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290-297. MR 0120167 (22:10924)
  • [6] -, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61. MR 0125031 (23:A2338)
  • [7] -, On the evolution of random graphs, Bull. Inst. Internat. Statist. Tokyo 38 (1961), 343-347. MR 0148055 (26:5564)
  • [8] C. W. Ford and G. E. Uhlenbeck, Combinatorial problems in the theory of graphs, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 163-167. MR 0086033 (19:113d)
  • [9] L. Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26 (1955), 512-517. MR 0070869 (17:48a)
  • [10] A. Rényi, On connected graphs. I, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 385-387. MR 0126842 (23:A4136)
  • [11] E. M. Wright, Asymptotic enumeration of connected graphs, Proc. Roy. Soc. Edinburgh Sect. A 68 (1968/69), 298-308. MR 0266820 (42:1723)
  • [12] -, The number of connected sparsely-edged graphs. II: Smooth graphs and blocks, J. Graph Theory 2 (1978), 299-305. MR 0505805 (58:21801)
  • [13] -, The number of connected sparsely-edged graphs. III: Asymptotic results, J. Graph Theory 4 (1980), 393-407. MR 595607 (82d:05070)

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: https://doi.org/10.1090/S0002-9947-1984-0756039-5
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society