Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T00:01:46.766Z Has data issue: false hasContentIssue false
  • English
  • Français

A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution

Published online by Cambridge University Press:  01 July 2007

SVANTE JANSON  and
JOEL SPENCER
SVANTE JANSON
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se, http://www.math.uu.se/~svante/)
JOEL SPENCER
Affiliation:
Courant Institute, 251 Mercer St., New York, NY 10012, USA (e-mail: spencer@cs.nyu.edu, http://www.cs.nyu.edu/cs/faculty/spencer/)
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 study a point process describing the asymptotic behaviour of sizes of the largest components of the random graph G(n, p) in the critical window, that is, for p = n−1 + λn−4/3, where λ is a fixed real number. In particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small ϵ (a scaled version of the number of vertices in components of size greater than εn2/3) is almost constant.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 4 , July 2007 , pp. 631 - 658
Copyright
Copyright © Cambridge University Press 2007

References

[1]Aldous, D. (1997) Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 812–854.CrossRefGoogle Scholar
[2]Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Oxford University Press, Oxford.CrossRefGoogle Scholar
[3]Billingsley, P. (1968) Convergence of Probability Measures, Wiley, New York.Google Scholar
[4]Bollobás, B. (1985) Random Graphs, Academic Press, London.Google Scholar
[5]Chassaing, P. and Janson, S. (2004) The center of mass of the ISE and the Wiener index of trees. Electron. Comm. Probab., 9 # 20, 178–187.Google Scholar
[6]Gut, A. (2005) Probability: A Graduate Course, Springer, New York.Google Scholar
[7]Janson, S. (1993) Multicyclic components in a random graph process. RSA 4 71–84.Google Scholar
[8]Janson, S. (1997) Gaussian Hilbert Spaces, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
[9]Janson, S. (2003) Cycles and unicyclic components in random graphs. CPC 12 27–52.Google Scholar
[10]Janson, S. (2003) The Wiener index of simply generated random trees. RSA 22 337–358.Google Scholar
[11]Janson, S., Knuth, D. E., Łuczak, T. and Pittel, B. (1993) The birth of the giant component. RSA 3 233–358.Google Scholar
[12]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley, New York.CrossRefGoogle Scholar
[13]Kallenberg, O. (1983) Point Processes, Akademie-Verlag, Berlin.Google Scholar
[14]Kallenberg, O. (2002) Foundations of Modern Probability, 2nd edn, Springer, New York.CrossRefGoogle Scholar
[15]Leadbetter, M. R., Lindgren, G. and Rootzén, H. (1983) Extremes and Related Properties of Random Sequences and Processes, Springer, New York.CrossRefGoogle Scholar
[16]Louchard, G. (1984) Kac's formula, Lévy's local time and Brownian excursion. J. Appl. Probab. 21 479–499.CrossRefGoogle Scholar
[17]Louchard, G. (1984) The Brownian excursion area: A numerical analysis. Comput. Math. Appl. 10 413–417. Erratum: Comput. Math. Appl. Part A 12 (1986) 375.CrossRefGoogle Scholar
[18]Łuczak, T., Pittel, B. and Wierman, J. C. (1994) The structure of a random graph near the point of the phase transition. Trans. Amer. Math. Soc. 341 721–748.CrossRefGoogle Scholar
[19]Otter, R. (1949) The multiplicative process. Ann. Math. Statist. 20 206–224.CrossRefGoogle Scholar
[20]Peres, Y. (2005) Personal communication.Google Scholar
[21]Pitman, J. (1998) Enumerations of trees and forests related to branching processes and random walks. In Microsurveys in Discrete Probability: Princeton, NJ, 1997, Vol. 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, pp. 163–180.CrossRefGoogle Scholar
[22]Pittel, B. (1990) On tree census and the giant component in sparse random graphs. RSA 1 311–342.Google Scholar
[23]Pittel, B. and Wormald, N. C. (2005) Counting connected graphs inside-out. J. Combin. Theory Ser. B 93 127–172.CrossRefGoogle Scholar
[24]Spencer, J. (1997) Enumerating graphs and Brownian motion. Comm. Pure Appl. Math. 50 291–294.3.0.CO;2-6>CrossRefGoogle Scholar
[25]Wright, E. M. (1977) The number of connected sparsely edged graphs. J. Graph Theory 1 317–330.CrossRefGoogle Scholar