Hamilton Cycles in the Semi-random Graph Process

Abstract The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v , and adds the edge u v to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c ∗ n rounds, where the value of c ∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c ∗ 2 . 61135 . This improves upon the previously best known upper bound of 3 n rounds. We also show that the previously best lower bound of ( ln 2 + ln ( 1 + ln 2 ) + o ( 1 ) ) n is not tight.