Between the Semi-Random Process and G(n,p)
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33854
curl -X POST /api/v1/records/arxiv/2610.33854/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33854/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'