A Blueprint for the Formalization of Seymour's Matroid Decomposition Theorem

Read full text
Authors: Ivan Sergeev, Martin Dvorak, Cameron Rampell, Mark Sandey, Pietro Monticone
Cited by: 0

Abstract

This document is a blueprint for the formalization in Lean of the structural theory of regular matroids underlying Seymour's decomposition theorem. We present a modular account of regularity via totally unimodular representations, show that regularity is preserved under $1$-, $2$-, and $3$-sums, and establish regularity for several special classes of matroids, including graphic, cographic, and the matroid $R_{10}$. The blueprint records the logical structure of the proof, the precise dependencies between results, and their correspondence with Lean declarations. It is intended both as a guide for the ongoing formalization effort and as a human-readable reference for the organization of the proof.

Fields of Study & Subjects

Computability Logic AI Algorithms programming and type systems Complexity and Algorithms in Graphs

Publication details

Journal / source
arXiv (Cornell University)
Publication date
3 January 2026
Language
EN
Document type
Preprint