Power of \(k\) choices in the semi-random graph process (Q6117415)

This paper studies a generalization of the semi-randomized graph process introduced in \textit{O. Ben-Eliezer} et al. [Random Struct. Algorithms 56, No. 3, 648--675 (2020; Zbl 1442.05203)]. In this variation, the game starts with an empty graph on \(n\) vertices, and the player is presented \(k\) random vertices \(u_1,\dots,u_k\) to choose from in each round. Once a vertex \(u\) is chosen, the player then selects a vertex \(v\) and adds \(uv\) to the graph. The objective of this game is to minimize the number of rounds it takes to force the graph to satisfy some monotone graph property with high probability. In the case of \(k=1\), we have the original game. The main results come in sections 3, 4, and 5 in which the properties of minimum degree of at least \(\ell\), the existence of a perfect matching, and the existence of a Hamiltonian cycle respectively are discussed. For sections 4 and 5, an optimal algorithm was not clear, so upper and lower bounds are presented. However, in section 3 it is shown that the optimal algorithm when the property in consideration is minimum degree of at least \(\ell\) is a greedy algorithm in which the offered vertex with the lowest degree is selected and joined to a minimum-degree vertex.