Semi-random process without replacement

Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some pre-determined objective in an online randomized environment. We introduce and study a semi-random multigraph process, which forms a no-replacement variant of the process that was introduced in [4]. 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 aTVM8PkpEpSbvZs4dJQR8mwq0yfAgraph having the desired property. Along the way we introduce and analyze an urn model which may also have independent interest.