4
$\begingroup$

This is a request for reference. Where can I find discussion of the Erdős–Rényi random graph in the regime between "giant-component" and "fully connected"? e.g. a detailed picture for say, $p_n=\frac{(\log n)^\gamma}{n}$, with $0<\gamma<1$

$\endgroup$

2 Answers 2

2
$\begingroup$

This may not satisfy your needs, but this recent (Fall 2012) paper, or its references might help:

"Lack of Hyperbolicity in Asymptotic Erdös-Renyi Sparse Random Graphs," by Onuttom Narayan, Iraj Saniee, Gabriel H. Tucci. (arXiv link).

Among other results, they have a new proof that

the giant component of $G(n,c/n)$ when $c>1$ has zero spectral gap almost surely as $n\to\infty$.

Random graphs in the $p = c/n$ (middle) regime are not $\delta$-hyperbolic [in the sense of Gromov], in the sense that they contain $\delta$-fat triangles for arbitrary large $\delta$, almost surely as $n\to\infty$:


 RandomGraph

$\endgroup$
1
$\begingroup$

"Random Graphs" by Bollobas has an extensive discussion of the thresholds at which various properties appear in the Erdos-Renyi model, for example the appearance of the first cycles. It's quite well-written, too. I'm familiar with the first edition, which is a little behind the times, but I see a new edition was published in 2001, which should be fairly up-to-date (the field has cooled down in the last decade).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.