Journal of Combinatorics

Volume 14 (2023)

Number 2

Semi-random process without replacement

Pages: 167 – 196



Shoni Gilboa (Department of Mathematics and Computer Science, Open University of Israel, Raanana, Israel)

Dan Hefetz (Department of Computer Science, Ariel University, Ariel, Israel)


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.

Dan Hefetz is supported by ISF grant 822/18.

Received 26 September 2020

Published 28 December 2022