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, \ldots, 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 $\ell$, the existence of a perfect matching, and the existence of a Hamiltonian cycle.
@article{10_37236_11909,
author = {Pawe{\l} Pra{\l}at and Harjas Singh},
title = {Power of \(k\) choices in the semi-random graph process},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/11909},
zbl = {1535.05196},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11909/}
}
TY - JOUR
AU - Paweł Prałat
AU - Harjas Singh
TI - Power of \(k\) choices in the semi-random graph process
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/11909/
DO - 10.37236/11909
ID - 10_37236_11909
ER -
%0 Journal Article
%A Paweł Prałat
%A Harjas Singh
%T Power of \(k\) choices in the semi-random graph process
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11909/
%R 10.37236/11909
%F 10_37236_11909
Paweł Prałat; Harjas Singh. Power of \(k\) choices in the semi-random graph process. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11909
