Circulants with circular chromatic index in the upper half

What Lean checks

Lean proves the actual 4g-regular and 4g-connected graph with real circular index 4g+2/3 for every g ≥ 2, and the complete degree/connectivity/index statements for C25, C31 and C33. The real-colouring lower bound and atom/subgroup connectivity arguments are proved internally. Strict sources, an all-owned audit of 601 declarations/500 theorem declarations and 171 required endpoints, and exact stock-kernel replay passed. Local receipt. The nonregular Section 7 examples, structural/insertion lemmas, SAT exclusions, combined repository gate, and hosted validation remain separate.

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 rr-edge-colouring of a graph GG is a map φ:E(G)→[0,r)\varphi:E(G)\to[0,r) such that edges sharing a vertex get colours at circular distance at least 11 modulo rr. The circular chromatic index χ′c(G)\chi'_c(G) is the least rr for which one exists. For a simple graph χ′c(G)≤χ′(G)≤Δ(G)+1\chi'_c(G)\le\chi'(G)\le\Delta(G)+1 by Vizing's theorem, and the questions below concern the upper half of the interval [Δ,Δ+1][\Delta,\Delta+1]. For odd nn and S⊆{1,…,(n−1)/2}S\subseteq\{1,\dots,(n-1)/2\}, the circulant Cn(S)C_n(S) has vertex set ℤn\mathbb Z_n, with x∼yx\sim y if and only if x−y∈±Sx-y\in\pm S.

Theorem 1. Let g≥2g\ge 2 and n=6g+1n=6g+1. The circulant

Gg=C6g+1(1,2,…,2g−2,2g+1,3g)G_g=C_{6g+1}(1,2,\dots,2g-2,\ 2g+1,\ 3g)

is a simple 4g4g-regular, 4g4g-connected graph with

χ′c(Gg)=12g+23=4g+23=Δ(Gg)+23.\chi'_c(G_g)=\frac{12g+2}{3}=4g+\frac23=\Delta(G_g)+\frac23 .

Theorem 2. The circulant C25(1,2,3,7,8,9,10,11,12)C_{25}(1,2,3,7,8,9,10,11,12) is a simple 18-regular, 18-connected graph with χ′c=75/4=18+3/4\chi'_c=75/4=18+3/4.

The smallest cases of Theorem 1 are G2=C13(1,2,5,6)G_2=C_{13}(1,2,5,6) with χ′c=26/3\chi'_c=26/3, G3=C19(1,2,3,4,7,9)G_3=C_{19}(1,2,3,4,7,9) with 38/338/3 and G4=C25(1,…,6,9,12)G_4=C_{25}(1,\dots,6,9,12) with 50/350/3.

Mazák and Zrubák remark that for no Δ≥8\Delta\ge 8 was a single graph with maximum degree Δ\Delta and χ′c∈(Δ+1/2,Δ+1)\chi'_c\in(\Delta+1/2,\Delta+1) known. Theorems 1 and 2 give such graphs, simple, regular and of connectivity Δ\Delta, for every Δ≡0(mod4)\Delta\equiv 0\pmod 4 with Δ≥8\Delta\ge 8 and for Δ=18\Delta=18. Their Problem 6 asks for which dd there is a dd-connected dd-regular graph with χ′c≥d+1/2\chi'_c\ge d+1/2. Read literally, it is answered for every even dd by Kd+1K_{d+1}, which has χ′c=d+1\chi'_c=d+1. In the non-trivial reading χ′c∈[d+1/2,d+1)\chi'_c\in[d+1/2,d+1), Theorems 1 and 2 answer it affirmatively for d≡0(mod4)d\equiv 0\pmod 4 with d≥8d\ge 8 and for d=18d=18.

The lower bounds come from χ′c(G)≥|E(G)|/α′(G)\chi'_c(G)\ge|E(G)|/\alpha'(G) (Lemma 1, proved by averaging over unit arcs), where α′\alpha' is the matching number; the graphs have odd order nn and contain a matching of size (n−1)/2(n-1)/2, so α′=(n−1)/2\alpha'=(n-1)/2 and the bound is 2n/32n/3 for GgG_g. The upper bound for GgG_g is an explicit (2n,3)(2n,3)-edge-colouring: two base matchings M0M_0 and M1M_1, whose edge lengths are exactly the connection set, are translated around ℤn\mathbb Z_n, and class aa gets colour 3amod2n3a\bmod 2n. 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 00 is a subgroup (cf. Hamidoune); both lemmas are reproved in the note. The connection set rules out every non-trivial subgroup of ℤn\mathbb Z_n. Theorem 2 is proved in the same way with a (75,4)(75,4)-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:

  • C31(1,2,3,7,8,9,10,11,12)C_{31}(1,2,3,7,8,9,10,11,12) is 18-regular and 18-connected with χ′c=93/5=Δ+3/5\chi'_c=93/5=\Delta+3/5, a denominator 5 for a simple regular graph; C33(1,2,3,4,5,9,10,…,15)C_{33}(1,2,3,4,5,9,10,\dots,15) is 24-regular and 24-connected with χ′c=99/4\chi'_c=99/4.
  • Non-regular graphs with χ′c=Δ+2/3\chi'_c=\Delta+2/3 for every Δ≡1,2(mod4)\Delta\equiv 1,2\pmod 4 with 25≤Δ≤5425\le\Delta\le 54 (Family B, built with a proved insertion lemma from base colourings found by SAT for 6≤g≤136\le g\le 13), and one with Δ=21\Delta=21 on 31 vertices, χ′c=65/3\chi'_c=65/3.

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 q>2q\gt 2 occurs in (Δ+1/2,Δ+1)(\Delta+1/2,\Delta+1), is not answered: the note has q=3,4,5q=3,4,5 only and says nothing about q≥6q\ge 6. Problem 6 in the reading χ′c=d+1/2\chi'_c=d+1/2 exactly is not answered and remains open here for every d≥5d\ge 5; the values here are d+2/3d+2/3, d+3/4d+3/4 and d+3/5d+3/5. In the non-trivial reading, Problem 6 stays open for d≢0(mod4)d\not\equiv 0\pmod 4 with d≠18d\ne 18. No example with Δ≡3(mod4)\Delta\equiv 3\pmod 4 was found, and Δ∈{9,10,11,13,14,15,17,19,22,23}\Delta\in\{9,10,11,13,14,15,17,19,22,23\} 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.py

verify.py checks Theorem 1 for g=2,…,30g=2,\dots,30: the circulant is simple and 4g4g-regular, the 2n2n classes partition the edge set, every class is a matching, the colouring is a (2n,3)(2n,3)-colouring (checked per vertex and per window), α′=(n−1)/2\alpha'=(n-1)/2 and |E|/α′=2n/3|E|/\alpha'=2n/3. Its own max-flow routine computes κ(Gg)=4g\kappa(G_g)=4g for g=2,3,4g=2,3,4 over all non-adjacent pairs and for g=5,…,8g=5,\dots,8 over the pairs (0,t)(0,t), 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 (p,q)(p,q)-edge-colouring of a simple graph, computes Δ\Delta and |E|/α′=p/q|E|/\alpha'=p/q, 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 report REVIEW.md and the referee's scripts, written independently of verify.py. check.py needs networkx; run it as python3 results/circular-index-upper-half-circulants/review/check.py fam, kappa or part2. extra.py imports check.py; run it with famB or g1.
  • search/ contains the search scripts that found the colourings, with their outputs and the work log LOG.md. Most need python-sat; cyc2.py (the backtracking search for the cyclic ansatz) and fam3.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.py and data/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.