Triangle Factors in the Semi-Random Graph Process
Source: arxiv.org/abs/2611.13959
The semi-random graph process is a single player game which starts with an empty graph on $n$ vertices and in each round the player is offered a random vertex and connects it to a vertex selected according to some strategy $\mathcal{S}$. The goal is, in as few rounds as possible, to arrive at a graph that satisfies some graph property $\mathcal{P}$. The main contribution of this work is to show that there is a strategy $\mathcal{S}$ which creates a $K_3$-factor in at most $2.929329 \, n$ rounds w.h.p.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.13959
curl -X POST /api/v1/records/arxiv/2611.13959/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13959/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'