On resilience of connectivity in the evolution of random graphs (Q2415088)

Summary: In this note we establish a resilience version of the classical hitting time result of \textit{B. Bollobás} and \textit{A. Thomason} [Ann. Discrete Math. 28, 47--97 (1985; Zbl 0588.05040)] 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.