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 α-resilient with respect to a monotone increasing graph property P if for every spanning subgraph H⊆G satisfying degH(v)⩽αdegG(v) for all v∈V(G), the graph G−H still possesses P. Let {Gi} be the random graph process, that is a process where, starting with an empty graph on n vertices G0, in each step i⩾1 an edge e is chosen uniformly at random among the missing ones and added to the graph Gi−1. We show that the random graph process is almost surely such that starting from m⩾(16+o(1))nlogn, the largest connected component of Gm is (12−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.