Hamilton cycles in the semi-random graph process. (January 2022)

• Record Type: Journal Article
• Authors: Gao, Pu; Kamiński, Bogumił; MacRury, Calum; Prałat, Paweł
• Is Part Of: European journal of combinatorics. Volume 99(2022)
• Publication Date: 2022-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103423
• Languages: English
• ISSNs: 0195-6698

Abstract

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.