The critical random graph, with martingales
By Asaf Nachmias, Yuval Peres. 2005
61 citations recorded by the source corpus.
We give a short proof that the largest component C1 of the random graph G(n, 1/n) is of size approximately n2/3. The proof gives explicit bounds for the probability that the ratio is very large or very small. In particular, the probability that n−2/3|C1| exceeds A is at most $${e^{ - c{A^3}}}$$ for some c > 0.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/e3f196a3ef4b6eab48db45933ac616d4869af68b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
- Remco van der Hofstad
- R. Durrett
- Louigi Addario-Berry
- Christina Goldschmidt
- Yuval Peres
- Nicolas Broutin
- Asaf Nachmias
- Mathew D. Penrose
In Mathematical Physics
- Remco van der Hofstad
- Asaf Nachmias
- R. Durrett
- Louigi Addario-Berry
- Nicolas Broutin
- Christina Goldschmidt
- Yuval Peres
- Zhan Shi
Citations in the corpus
- Random Graphs and Complex Networks (2016, result): “Add results and proof of NacPer05 [161] on critical random graph.”
- The continuum limit of critical random graphs (2009, background): “For our purposes, the latter bounds are most usefully stated by Nachmias and Peres [42] (see also [44, 50]).”
- Random Graph Dynamics: References (2006, background): “This was introduced by Fortuin and Kastelyn (1972) but Aizenman, Chayes, Chayes, and Newman (1988) were the first use this connection to prove rigorous results.”
- Critical random graphs: Diameter and mixing time (2007, background): “2 and the following fact, first proved in [10] (see also [1], [18] and [21]): In G(n, 1+λn −1/3 n ), lim inf n P(|C1| > βn) → 1 , as β → 0 .”