Mixing time of near-critical random graphs

Details Mixing time of near-critical random graphs Mixing time of near-critical random graphs

2009-08-26

arxiv.org/abs/0908.3870v1

Mathematics

Probability

29 pages

Scientific paper

Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is bounded, Nachmias and Peres proved that the mixing time on $C_1$ is of order $n$. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of $C_1$ in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper we show that for $p=(1+\epsilon)/n$ with $\lambda=\epsilon^3 n\to\infty$ and $\lambda=o(n)$, the mixing time on $C_1$ is with high probability of order $(n/\lambda)\log^2 \lambda$. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime (i.e., $p=(1-\epsilon)/n$ with $\lambda$ as above).

Affiliated with

Also associated with

No associations

Rating

Mixing time of near-critical random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Mixing time of near-critical random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixing time of near-critical random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-625649