Subgraph Games in the Semi-Random Graph Process and Its Generalization to Hypergraphs

Abstract

The semi-random graph process is a single-player game that begins with 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.

We focus on the problem of constructing a subgraph isomorphic to an arbitrary, fixed graph $H$. In [Ben-Eliezer et al., Random Struct. Algorithms, 2020, 6(3):648– 675], it was proved that asymptotically almost surely one can construct $H$ in $t$ rounds, for any $t\gg n^{(d-1)/d}$ where $d \ge 2$ is the degeneracy of~$H$. It was also proved that this result is sharp for $H = K_{d+1}$ and conjectured that it is so for all graphs $H$. In this paper we prove this conjecture, as well as, its generalization to a semi-random $s$-uniform hypergraph process for every $s\ge2$.