Power of $k$ Choices in the Semi-Random Graph Process

Paweł Prałat, Harjas Singh

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 pla…