Optimally building spanning graphs in semirandom graph processes

The semirandom graph process constructs a graph G in a series of rounds, starting with the empty graph on n vertices. In each round, a player is offered a vertex v chosen uniformly at random, and chooses an edge on v to add to G. The player's aim is to make G satisfy some property as quickly as possible. Our interest is in the property that G contain a given n-vertex graph H with maximum degree $Δ$. In 2021, Ben-Eliezer, Gishboliner, Hefetz and Krivelevich showed that there is a semirandom strategy that achieves this, with probability tending to 1 as n tends to infinity, in (1 + o_Δ(1)) 3 Δn/2 rounds, where o_Δ(1) is a function that tends to $0$ as $Δ$ tends to infinity. We improve this to (1 + o_Δ(1)) Δn/2, which can be seen to be asymptotically optimal in $Δ$. We show the same result for a variant of the semirandom graph process, namely the semirandom tree process introduced by Burova and Lichev, where in each round the player is offered the edge set of a uniformly chosen tree on n vertices, and chooses one edge to keep.