Delphi.science

Asymptotic 1-factorization of dense regular graphs (Perković–Reed, via Vaughan)

Source: github.com/jtraverso/asymptotic-one-factorization/tree/50bc…

Juan Pablo Traverso Gianini

Palomar Registrypalomar/PALOMAR-2026-11-12-000014Nov 12, 2026math.COscore 0

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…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-12-000014
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-12-000014/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-12-000014/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'