Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

"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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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