Proceedings of the American Mathematical Society

Vol. 146, num. 8, p. 3321-3332

DOI: 10.1090/proc/14021

Date of publication: 2018-03-20

Abstract:

We show that for all $ d\in \{3,\ldots ,n-1\}$ the size of the largest component of a random $ d$-regular graph on $ n$ vertices around the percolation threshold $ p=1/(d-1)$ is $ \Theta (n^{2/3})$, with high probability. This extends known results for fixed $ d\geq 3$ and for $ d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $ d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method

First published in Proc. Amer. Math. Soc. 146 (2018), 3321-3332, published by the American Mathematical Society]]>

Proceedings of the American Mathematical Society

Vol. 143, num. 3, p. 925-936

Date of publication: 2015-03-01

Abstract:

Let G(n, M) be the uniform random graph with n vertices and M edges. Erdos and Renyi (1960) conjectured that the limiting probability; lim(n ->infinity) Pr{G(n, n/2) is planar}; exists and is a constant strictly between 0 and 1. Luczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Luczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting probability of a random graph being planar near the critical point M = n/2. For each lambda, we find an exact analytic expression for; p(lambda) = lim(n ->infinity) Pr {G (n, n/2 (1 + lambda(n-1/3))) is planar}.; In particular, we obtain p(0) approximate to 0.99780. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of G(n, n/2) being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.]]>