Subgraph games in the semi-random graph process and its generalization to hypergraphs

Natalie Behague ; Trent Marbach ; Paweł Prałat¹ ; Andrzej Ruciński

¹Department of Mathematics Ryerson University

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

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$.

Détail

DOI : 10.37236/11859

Classification : 05C57, 05C80, 05C65, 91A43
Mots-clés : single-player game, graph processes