Hamilton cycles in a semi-random graph model

Abstract

We show that with high probability we can build a Hamilton cycle after at most $1.85n$ rounds in a particular semi-random model. In this model, in one round, we are given a {uniform random} $v\in [n]$ and then we can add an {arbitrary} edge $\{v,w\}$. Our result improves on $2.016n$ in a recent paper of Gao, MacRury, and Pralat.