Power of k Choices in the Semi-Random Graph Process
share
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 uv 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. In this paper, we introduce a natural generalization of this game in which k random vertices u_1, …, u_k are presented to the player in each round. She needs to select one of the presented vertices and connect to any vertex she wants. We focus on the following three monotone properties: minimum degree at least ℓ, the existence of a perfect matching, and the existence of a Hamiltonian cycle.
READ FULL TEXT