Resilience of Perfect Matchings and Hamiltonicity in Random Graph Processes

Abstract

Let $\{G_i\}$ be the random graph process: starting with an empty graph $G_0$ with $n$ vertices, in every step $i\ge 1$ the graph $G_i$ is formed by taking an edge chosen uniformly at random among the non-existing ones and adding it to the graph $G_{i-1}$. The classical `hitting-time' result of Ajtai, Komlós, and Szemerédi, and independently Bollobás, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches $2$, that is if $\delta (G_i)\ge 2$ then $G_i$ is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for $m\ge (\frac{1}{6}+o(1))n\log n$ edges, the $2$-core of the graph $G_m$ remains Hamiltonian even after an adversary removes $(\frac{1}{2}-o(1))$-fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings.

23 pages; small updates to the paper after anonymous reviewers' reports