The chromatic number of a random graph with $o(n^{3/2})$ edges
Let $G(n,m)$ be the Erdos-Renyi random graph with $n$ vertices and $m$ edges and let $δ>0$. Alon and Krivelevich [Combinatorica 1997] proved that for any sequence $m\leq n^{3/2-δ}$ there \emph{exists} an integer sequence $q=q(n)$ such that the chromatic number of $G(n,m)$ equals either $q$ or $q+1$ with probability tending to one as $n\to\infty$. In this paper, we give an explicit formula for this sequence $q(n)$ and confirm their result under a less restrictive assumption that $m=o(n^{3/2})$. Furthermore, we show that for all but a vanishing proportion of the admissible values of $m$, the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33678
curl -X POST /api/v1/records/arxiv/2610.33678/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33678/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'