Catalogue · Proof · Exact checks · Certificate checks · Issue #152
Status: Written proof of Theorems 1 and 2. It has been through one independent referee pass by a second model instance, which found no mathematical error; the gaps it listed are fixed in the note. The note is otherwise unrefereed. The further examples of Section 7 are computer-certified instances, not a general theorem.
Lean status: Theorems 1 and 2 are fully formalized, as are the regular C31 and C33 examples of Section 7.2. The statements use the literal finite graphs, regular degree, connectedness after every deletion of fewer than the stated number of vertices, and the infimum over actual real circular edge-colourings. The 19-module closure passed strict source compilation, an all-owned audit of 601 declarations (500 theorem declarations and 171 required endpoints), and the unchanged pinned stock-kernel replay. Only propext, Classical.choice, and Quot.sound occur. Local receipt.
The result-level badge remains partial because the nonregular positive examples, the additional structural/insertion lemmas, and the SAT exclusion claims of Section 7 are not covered by this checkpoint. The combined repository gate and hosted validation remain separate.
Primary source: J. Mazák and F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822, Section 8 (Problems 6 and 7 and the remark before them).
Result
A circular -edge-colouring of a graph is a map such that edges sharing a vertex get colours at circular distance at least modulo . The circular chromatic index is the least for which one exists. For a simple graph by Vizing's theorem, and the questions below concern the upper half of the interval . For odd and , the circulant has vertex set , with if and only if .
Theorem 1. Let and . The circulant
is a simple -regular, -connected graph with
Theorem 2. The circulant is a simple 18-regular, 18-connected graph with .
The smallest cases of Theorem 1 are with , with and with .
Mazák and Zrubák remark that for no was a single graph with maximum degree and known. Theorems 1 and 2 give such graphs, simple, regular and of connectivity , for every with and for . Their Problem 6 asks for which there is a -connected -regular graph with . Read literally, it is answered for every even by , which has . In the non-trivial reading , Theorems 1 and 2 answer it affirmatively for with and for .
The lower bounds come from (Lemma 1, proved by averaging over unit arcs), where is the matching number; the graphs have odd order and contain a matching of size , so and the bound is for . The upper bound for is an explicit -edge-colouring: two base matchings and , whose edge lengths are exactly the connection set, are translated around , and class gets colour . Every window of three consecutive colour classes is a matching that misses exactly one vertex, so the lower bound is attained; the window conditions reduce to four disjointness statements checked by hand. Connectivity follows from the theory of atoms: distinct atoms are disjoint (Watkins, Mader) and, in a Cayley graph, the atom containing is a subgroup (cf. Hamidoune); both lemmas are reproved in the note. The connection set rules out every non-trivial subgroup of . Theorem 2 is proved in the same way with a -edge-colouring built from three base matchings, which was found by computer search and whose nine window conditions are checked by hand.
Section 7 of the note records further examples. They are certified by verify_part2.py, not covered by a general proof:
- is 18-regular and 18-connected with , a denominator 5 for a simple regular graph; is 24-regular and 24-connected with .
- Non-regular graphs with for every with (Family B, built with a proved insertion lemma from base colourings found by SAT for ), and one with on 31 vertices, .
Section 7 also proves a structural lemma on perfect colourings and lists parameter sets for which exhaustive SAT searches in the cyclic ansatz found no colouring; these searches are not reproduced by the verifiers.
Not answered. Problem 7, whether every denominator occurs in , is not answered: the note has only and says nothing about . Problem 6 in the reading exactly is not answered and remains open here for every ; the values here are , and . In the non-trivial reading, Problem 6 stays open for with . No example with was found, and remain without an example.
Nothing new is claimed about atoms or connectivity. The quotations from Mazák and Zrubák were taken from the arXiv HTML through a web-fetch tool and not compared with the PDF character by character. No literature search beyond that paper and a few web searches was made; the searches found nothing more recent on this question.
Verification
Run from the repository root with Python 3.10 or later and no other dependencies:
python3 results/circular-index-upper-half-circulants/verify.py
python3 results/circular-index-upper-half-circulants/verify_part2.pyverify.py checks Theorem 1 for : the circulant is simple and -regular, the classes partition the edge set, every class is a matching, the colouring is a -colouring (checked per vertex and per window), and . Its own max-flow routine computes for over all non-adjacent pairs and for over the pairs , which suffices by vertex-transitivity. It makes the same checks for Theorem 2. verify_part2.py reads data/part2_certificates.json and, for every certificate of Section 7, rebuilds the colour sequence, checks that it is a perfect -edge-colouring of a simple graph, computes and , and computes the vertex connectivity of the regular circulants. The scripts end with ALL CHECKS PASSED and ALL PART 2 CHECKS PASSED and take a few seconds.
The scripts check finitely many cases. The Lean proof of Theorem 1 covers every g ≥ 2; it does not infer the universal result from those checks. CircularIndex.theorem_one and theorem_two combine the exact real index, degree, and connectivity assertions. graph31_complete and graph33_complete prove the corresponding three assertions for the two regular supplemental examples. The real lower bound is proved by rounding arbitrary real circular colourings and taking the resulting bounds to their limit. The atom intersection and subgroup arguments used for connectivity are proved internally.
The entry modules are CircularIndexTheorems.lean, CircularIndexFurtherConnected.lean, and CircularIndexFurther.lean. Run the registered full gate from the repository root with scripts/verify_lean.sh.
Optional checks, not run by CI:
review/contains the referee reportREVIEW.mdand the referee's scripts, written independently ofverify.py.check.pyneedsnetworkx; run it aspython3 results/circular-index-upper-half-circulants/review/check.py fam,kappaorpart2.extra.pyimportscheck.py; run it withfamBorg1.search/contains the search scripts that found the colourings, with their outputs and the work logLOG.md. Most needpython-sat;cyc2.py(the backtracking search for the cyclic ansatz) andfam3.py(a first check of the family of Theorem 1) use only the standard library. None of them is needed to check the proof.
Files
PROOF.md: context, statements, proofs, consequences for the questions of Mazák and Zrubák, verification summary, sources, and the further searches of Section 7.verify.py: standard-library check of Theorems 1 and 2.verify_part2.pyanddata/part2_certificates.json: standard-library check of the Section 7 certificates.review/: the referee report and the referee's scripts.search/: search scripts, outputs and work log.