The Maximum Block Size of Critical Random Graphs

Abstract

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+\lambda n^{-1/3})$, where $\lambda$ 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 $\lambda$.