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 that has property , for the following examples of : (1) is the set of graphs containing a fixed ‐degenerate subgraph, where is fixed and (2) is the set of ‐connected graphs, where is fixed. In particular, our result of the ‐connectedness above settles the open case of the original semi‐random graph process. We also prove that there exist properties where the two semi‐random graph processes do not construct a graph in asymptotically equally fast. We further propose some conjectures on for which the two processes perform differently.