On resilience of connectivity in the evolution of random graphs

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 ${\mathrm{deg}}_H(v)\le \alpha \cdot {\mathrm{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\ge 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\ge (\frac{1}{6}+o(1))n\log n$, the largest connected component of $G_m$ is $(\frac{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.

arXiv comment13 pages; update after reviewers' reports