{"id":"palomar/PALOMAR-2026-11-12-000014","url":"https://github.com/jtraverso/asymptotic-one-factorization/tree/50bc0b383e5447dc4b70db20e3af1c6c5efc1c2f","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-12-000014-v1.json","repo":"https://github.com/jtraverso/asymptotic-one-factorization","tags":["math.CO","msc:05C15","msc:05C70"],"score":0,"title":"Asymptotic 1-factorization of dense regular graphs (Perković–Reed, via Vaughan)","trust":"high","domain":"math.CO","source":"palomar","authors":["Juan Pablo Traverso Gianini"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 / Mathlib proof of the asymptotic form of the Chetwynd–Hilton 1-factorization conjecture (Perković and Reed 1997, Häggkvist): for every ε > 0 there is N such that every d-regular simple graph on 2n vertices with n ≥ N and d ≥ (1 + ε) n is 1-factorizable, i.e. its line graph is d-colourable (one_factorization); the integer form with (q + 1) n ≤ q d for q ≥ 1 is one_factorization_of_ge. The proof follows Vaughan (arXiv:1010.5192) for multiplicity 1: a balanced bipartition A, Aᶜ with |d_A(v) − d_{Aᶜ}(v)| < s for every vertex (Lemma 13, here by a counting Chernoff bound with no…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-12","reactions":{},"formalized":true,"formalizes":[{"title":"Edge coloring regular graphs of high degree","identifier":"doi:10.1016/S0012-365X(96)00202-6","relationship":"formalizes"},{"title":"An Asymptotic Version of the Multigraph 1-Factorization Conjecture","identifier":"arXiv:1010.5192","relationship":"formalizes"}]}