The Maximum Block Size of Critical Random Graphs

Let $G(n,\, M)$ be the uniform random graph with $n$ vertices and $M$ edges. Let $B_n$ be the maximum block-size of $G(n,\, M)$ or the maximum size of its maximal $2$-connected induced subgraphs. We determine the expectation of $B_n$ near the critical point $M=n/2$. As $n-2M \gg n^{2/3}$, we find a constant $c_1$ such that $c_1 = \lim_{n \rightarrow \infty} \left(1 - \frac{2M}{n} \right) \, E B_n \, .$ Inside the window of transition of $G(n,\, M)$ with $M=\frac{n}{2}(1+λn^{-1/3})$, where $λ$ is any real number, we find an exact analytic expression for $c_2(λ) = \lim_{n \rightarrow \infty} \frac{E B_n} {n^{1/3}} \, .$ This study relies on the symbolic method and analytic tools coming from generating function theory which enable us to describe the evolution of $n^{-1/3} \, E B_n$ as a function of $λ$.

No reviews yet.

No comments yet.