Existence of the q-colorability threshold for sparse random graphs
Source: github.com/pmaronow/q-colorability-palomar/tree/f31c25fbba9…
For every integer q at least 3, the formalization proves the existence of a limiting q-colorability threshold for sparse random graphs. A single constant alpha_q in [1/2, log(q)/log(q/(q-1))] gives the transition for the uniform model with floor(c n) edges and the transition at d = 2 alpha_q for the binomial model with edge probability d/n. For every fixed eta in (0,1), there is C > 0 such that, for all sufficiently large n, the first loss of q-colorability under independent uniform additions of unordered pairs of distinct vertices lies within C n (log n)^(-3/2) steps of deterministic…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-04-000013
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-04-000013/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-04-000013/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'