2018/05/22 by Haller, Luc, Trujić, Miloš
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1805.08744
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 ≥ (\tfrac16 + o(1)) n log n, the largest connected component of Gm is (\tfrac12 - 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.