Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process

In this paper, we study the following recently proposed semi‐random graph process: starting with an empty graph on n vertices, the process proceeds in rounds, where in each round we are given a uniformly random vertex v , and must immediately (in an online manner) add to our graph an edge incident with v . The end goal is to make the constructed graph satisfy some predetermined monotone graph property. Alon asked whether every given bounded‐degree spanning graph can be constructed with high probability in O ( n ) rounds. We answer this question positively in a strong sense, showing that any n ‐vertex graph with maximum degree Δ can be constructed with high probability in ( 3 Δ / 2 + o ( Δ ) ) n rounds. This is tight up to a multiplicative factor of 3 + o Δ ( 1 ) . We also obtain tight bounds for the number of rounds necessary to embed bounded‐degree spanning trees, and consider a nonadaptive variant of this setting.