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 \leq r \leq n$, in the $((q-1)n+r)$th round of the process, the decision-maker, called Builder, is offered the vertex $\pi_q (r)$, where $\pi_1, \pi_2, \dotsc$ 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 $\pi_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 an urn model which may also have independent interest.

Full Text (PDF format)

Dan Hefetz is supported by ISF grant 822/18.

Received 26 September 2020

Published 28 December 2022