WorksMathematics
Between the Semi-Random Process and G(n,p)
Abstract · v1
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 possible partners, and Builder chooses one of them. We study how this limited adaptivity changes the hitting times of monotone graph properties and how the familiar logarithmic ``coupon–collector'' delays in random graphs are reflected in this setting.
Review conversation
Reviews are not available for this work yet.