{"id":"palomar/PALOMAR-2026-11-04-000013","url":"https://github.com/pmaronow/q-colorability-palomar/tree/f31c25fbba9ecf72305de746ec1b64c8be327f26","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-04-000013-v1.json","repo":"https://github.com/pmaronow/q-colorability-palomar","tags":["math.CO","math.PR","msc:05C80","msc:05C15","msc:60C05"],"score":0,"title":"Existence of the q-colorability threshold for sparse random graphs","trust":"high","domain":"math.CO","source":"palomar","authors":["P. M. Aronow","Patrick Lopatto"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-04","reactions":{},"formalized":true,"formalizes":[{"title":"Existence of the q-Colorability Threshold for Sparse Random Graphs","identifier":"https://github.com/pmaronow/q-colorability-palomar/blob/03a35c170b1135d8546c8d63ccadc7939389eff1/Aronow_Lopatto_colorability_threshold.pdf","relationship":"formalizes"}]}