Anti-concentration of the chromatic number of a dense random graph
Source: hexagonmath.org/abs/2611.00582v1
For \(G_n\sim G(n,1/2)\) and each fixed \(0<d<1/4\), we obtain that the supremum over intervals of radius \(n^d\) of the probability that \(\chi(G_n)\) lies in the interval tends to zero. This implies the failure of concentration on any fixed number of possible values and gives the eventual strict half-mass bound asked for in Erdős Problem 1156. The proof treats different supplies of large independent sets by matching sums and by one- and two-count Gaussian comparisons.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00582
curl -X POST /api/v1/records/hexagon/2611.00582/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00582/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'