Semi-random Process Without Replacement

We introduce and study a semi-random multigraph process, which forms a no-replacement variant of the process that was introduced in [3]. The process starts with an empty graph on the vertex set [n]. For every positive integers q and 1 ≤ r≤ n, in the ((q- 1 ) n+ r) th round of the process, the decision-maker, called Builder, is offered the vertex π_q(r), where π₁, π₂, … is a sequence of permutations in S_n, chosen independently and uniformly at random. Builder then chooses an additional vertex (according to a strategy of his choice) and connects it by an edge to π_q(r). For several natural graph properties, such as k-connectivity, minimum degree at least k, and building a given spanning graph (labeled or unlabeled), we determine the typical number of rounds Builder needs in order to construct a graph having the desired property. Along the way we introduce and analyze two urn models which may also have independent interest.