On Resilience of Connectivity in the Evolution of Random Graphs

Source abstract

In this note we establish a resilience version of the classical hitting time result of Bollobás and Thomason regarding connectivity. A graph $G$ is said to be $\alpha$-resilient with respect to a monotone increasing graph property $\mathcal{P}$ if for every spanning subgraph $H \subseteq G$ satisfying $\deg_H(v) \leqslant \alpha \deg_G(v)$ for all $v \in V(G)$, the graph $G - H$ still possesses $\mathcal{P}$. Let $\{G_i\}$ be the random graph process, that is a process where, starting with an empty graph on $n$ vertices $G_0$, in each step $i \geqslant 1$ an edge $e$ is chosen uniformly at random among the missing ones and added to the graph $G_{i - 1}$. We show that the random graph process is almost surely such that starting from $m \geqslant (\tfrac{1}{6} + o(1)) n \log n$, the largest connected component of $G_m$ is $(\tfrac{1}{2} - o(1))$-resilient with respect to connectivity. The result is optimal in the sense that the constants $1/6$ in the number of edges and $1/2$ in the resilience cannot be improved upon. We obtain similar results for $k$-connectivity.