PreprintarXiv licencearXiv
Between the Semi-Random Process and G(n,p)
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.
Related
- Accelerated Degradation Process Analysis Based on the Generalized Wiener Process with Mixed Random Effects
- Hitting time for loose Hamilton cycles in the random hypergraph process
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- A Branching Process with Geometric Emigration and the "Have Your Cookie and Eat It" Random Walk
- A covariance density for a point process and a random field
BibTeX
@misc{akhmejanova2026between,
title = {{Between the Semi-Random Process and G(n,p)}},
author = {Margarita Akhmejanova and Andrey Kupavskii},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33854},
eprint = {2610.33854},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33854},
}
RIS
TY - UNPB
TI - Between the Semi-Random Process and G(n,p)
AU - Margarita Akhmejanova
AU - Andrey Kupavskii
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33854
UR - https://arxiv.org/abs/2610.33854
AB - 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.
ER -