Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Rigorous Result for ...
Conference paper

Rigorous Result for the CHKNS Random Graph Model

Rick Durrett (1)
(1) École normale supérieure - Paris
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2002
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Proceedings
DOI
10.46298/dmtcs.3345
License
https://about.hal.science/hal-authorisation-v1
Indicators
869
Views
1124
Downloads

Rigorous Result for the CHKNS Random Graph Model

Rick Durrett (1)
(1) École normale supérieure - Paris
Abstract
We study the phase transition in a random graph in which vertices and edges are added at constant rates. Two recent papers in Physical Review E by Callaway, Hopcroft, Kleinberg, Newman, and Strogatz, and Dorogovstev, Mendes, and Samukhin have computed the critical value of this model, shown that the fraction of vertices in finite clusters is infinitely differentiable at the critical value, and that in the subcritical phase the cluster size distribution has a polynomial decay rate with a continuously varying power. Here we sketch rigorous proofs for the first and third results and a new estimates about connectivity probabilities at the critical value.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • random graph
  • clusterization
  • Brownian motion
  • singularity analysis
Cited by

Source: OpenCitations

  • Phase Transitions in Dynamical Random Graphs

    Journal of Statistical Physics

    Authors : Tatyana S. Turova ORCID

    Journal reference : Volume 123, 2006, pp. 1007-1032

    DOI : 10.1007/s10955-006-9101-3

  • Max $\kappa$-cut and the inhomogeneous Potts spin glass

    The Annals of Applied Probability

    Authors : Aukosh Jagannath, Justin Ko ORCID, Subhabrata Sen ORCID

    Journal reference : Volume 28, 2018, pp.

    DOI : 10.1214/17-aap1337

  • Random Graphs and Branching Processes

    Bolyai Society mathematical studies

    Authors : Béla Bollobás ORCID, Oliver Riordan ORCID

    Journal reference : Volume , 2008, pp. 15-115

    DOI : 10.1007/978-3-540-69395-6_1

  • Thek-Core and Branching Processes

    arXiv (Cornell University)

    Authors : OLIVER RIORDAN ORCID

    Journal reference : Volume 17, 2007, pp. 111-136

    DOI : 10.1017/s0963548307008589

  • Evolution of a Modified Binomial Random Graph by Agglomeration

    LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas)

    Authors : Mihyun Kang ORCID, Angelica Pachon ORCID, Pablo M. Rodríguez ORCID

    Journal reference : Volume 170, 2017, pp. 509-535

    DOI : 10.1007/s10955-017-1940-6

  • Susceptibility in Inhomogeneous Random Graphs

    The Electronic Journal of Combinatorics

    Authors : Svante Janson ORCID, Oliver Riordan ORCID

    Journal reference : Volume 19, 2012, pp.

    DOI : 10.37236/2035

  • The Phase Transition and Connectedness in Uniformly Grown Random Graphs

    Lecture notes in computer science

    Authors : Béla Bollobás ORCID, Oliver Riordan ORCID

    Journal reference : Volume , 2004, pp. 1-18

    DOI : 10.1007/978-3-540-30216-2_1

  • Continuity of the percolation threshold in randomly grown graphs.

    Electronic Journal of Probability

    Authors : Tatyana Turova ORCID

    Journal reference : Volume 12, 2007, pp.

    DOI : 10.1214/ejp.v12-436

  • The Phase Transition in the Erdős-Rényi Random Graph Process

    Bolyai Society mathematical studies

    Authors : Béla Bollobás ORCID, Oliver Riordan ORCID

    Journal reference : Volume , 2013, pp. 59-110

    DOI : 10.1007/978-3-642-39286-3_3
Preview
Loading PDF preview...