Paperlane

no. 3 · Tuesday 27 October 2026

Between the Semi-Random Process and G(n,p)

Margarita Akhmejanova and Andrey Kupavskii

math.CO

Abstract

We study a random graph process that connects the Erdős–Rényi random graph with the semi-random process. In each round, a uniformly random vertex is revealed together with a uniformly random candidate set of $s$ possible partners, and Builder chooses one of them. We study how this limited adaptivity $s$ changes the hitting times of monotone graph properties and how the familiar logarithmic ``coupon–collector'' delays in random graphs are reflected in this setting.

fields
Combinatorics, Probability
pdf ↗ page arXiv:2610.33854 ↗