On the pre- and post-positional semi-random graph processes

Abstract

We study the semi-random graph process, and a variant process recently suggested by Nick Wormald. We show that these two processes are asymptotically equally fast in constructing a semi-random graph $G$ that has property $\mathcal{P}$, for the following examples of $\mathcal{P}$: - $\mathcal{P}$ is the set of graphs containing a $d$-degenerate subgraph, where $d\ge 1$ is fixed; - $\mathcal{P}$ is the set of $k$-connected graphs, where $k\ge 1$ is fixed. In particular, our result of the $k$-connectedness above settles the open case $k=2$ of the original semi-random graph process. We also prove that there exist properties $\mathcal{P}$ where the two semi-random graph processes do not construct a graph in $\mathcal{P}$ asymptotically equally fast. We further propose some conjectures on $\mathcal{P}$ for which the two processes perform differently.