← All papers
First page of Composition Direction of Seymour's Theorem for Regular Matroids -- Formally Verified

Composition Direction of Seymour's Theorem for Regular Matroids -- Formally Verified

Martin Dvorak, Tristan Figueroa-Reid, Rida Hamadani, Byung-Hak Hwang, Evgenia Karunus, Vladimir Kolmogorov, Alexander Meiburg, Alexander Nelson, Peter Nelson, Mark Sandey, Ivan Sergeev

math.CO Sep 24, 2025 · v1
Develops a Lean 4 library on totally unimodular matrices and matroids to formally prove the composition direction of Seymour's decomposition theorem.
Seymour's decomposition theorem is a hallmark result in matroid theory presenting a structural characterization of the class of regular matroids. Formalization of matroid theory faces many challenges, most importantly that only a limited number of notions and results have been implemented so far. In this work, we formalize the proof of the forward (composition) direction of Seymour's theorem for regular matroids. To this end, we develop a library in Lean 4 that implements definitions and results about totally unimodular matrices, vector matroids, their standard representations, regular matroids, and 1-, 2-, and 3-sums of matrices and binary matroids given by their standard representations. Using this framework, we formally state Seymour's decomposition theorem and implement a formally verified proof of the composition direction in the setting where the matroids have finite rank and may have infinite ground sets.

Seymour's decomposition theorem provides a structural characterization of regular matroids, but formalization of matroid theory in proof assistants has been limited, with only basic notions implemented so far.

The authors formalize the composition (forward) direction of Seymour's theorem for regular matroids in Lean 4. They develop a library implementing definitions and results about totally unimodular matrices, vector matroids, their standard representations, regular matroids, and 1-, 2-, and 3-sums of matrices and binary matroids given by their standard representations. The formalization handles matroids with finite rank and possibly infinite ground sets.

The formalization yields a formally verified proof of the composition direction of Seymour's decomposition theorem, demonstrating that graphic matroids, cographic matroids, and R10 are closed under 1-, 2-, and 3-sums and are all regular.