Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process. Issue 4 (27th September 2020) - Ben‐Eliezer, Omri; Gishboliner, Lior; Hefetz, Dan; Krivelevich, Michael
Abstract : 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.