Hello everyone,
I would like to share a mathematical result on support-overlap graphs of linear kernels and request an independent review of its Lean 4 formalization.
The result concerns the homogeneous kernel K_G over GF(3) arising from the positive exact-one encoding of graph three-colouring.
For every finite nonempty simple graph G, let H_B denote the coefficient-overlap graph associated with an arbitrary basis B of K_G.
The main theorem establishes the exact identity
2\operatorname{tw}(G)+1.
]
The essential part is the universal lower bound: no change of basis can reduce the overlap treewidth below this value. An explicit canonical basis attains equality.
The Lean development includes the upper bound (wstar_le_two_tw_add_one), the lower bound (tw_le_of_coeff_tw), and the resulting equivalence (wstar_eq_iff).
The repository reports successful compilation under Lean 4.35.0 / Mathlib v4.35.0, without sorry or user-declared axioms. The reported axioms are propext, Classical.choice, and Quot.sound.
A stronger mathematical theorem extends the subgraph embedding to arbitrary fields and finite spanning families. That extension has a written proof but is not yet fully formalized in Lean.
I would particularly appreciate independent verification of:
- Reproducibility of the Lean build.
- Agreement between the formal theorem statements and the intended mathematical result.
- Completeness of the lower-bound argument, including its quantification over arbitrary bases.
- Any overlooked assumptions or opportunities to simplify the formalization.
Lean sources and proof documentation:
https://github.com/tonnestate/FruitStack-Eval/tree/c87c4263c59b879938390f535630c3517925eb87/results/PNP-001-2026-11-19/lean
Related mathematical preprint:
Positive Exact-One Satisfiability: Algebraic Structure, Universal Basis-Overlap, and Complexity Transfers | Zenodo
The result is a structural theorem about linear representations. I am not claiming that it establishes a general computational lower bound or resolves P versus NP.
Any mathematical feedback or independent verification would be greatly appreciated.
Thank you,
Bjoern Tonn