∑math20

Combinatorics · Result 185

Counterexamples to infinite matroid intersection and packing/covering

1 paperLean

Disproves the unrestricted infinite matroid intersection and packing/covering conjectures in ZFC, using two self-dual partitional matroids on a countably infinite ground set. The same examples answer Joó’s partitional-matroid question negatively. They are neither finitary nor cofinitary, so Nash-Williams’ original finitary conjecture remains outside the result.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of A Counterexample to the Infinite Matroid Packing/Covering Conjecture

A Counterexample to the Infinite Matroid Packing/Covering Conjecture

OpenAI · September 24, 2026

We construct in ZFC two self-dual partitional matroids on a countably infinite common ground set that admit neither a packing/covering partition nor an intersection witness. This disproves the unrestricted infinite matroid packing/covering and intersection conjectures and answers Joó's question for two partitional matroids negatively. The examples are neither finitary nor cofinitary.

Read PDF Download Source

Cite
@misc{OAI:A-Counterexample-to-the-Infinite-Matroid-Packing-Covering-Conjecture-September-24-2026,
  author = {{OpenAI}},
  title = {{A Counterexample to the Infinite Matroid Packing/Covering Conjecture}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/A-Counterexample-to-the-Infinite-Matroid-Packing-Covering-Conjecture-September-24-2026/paper.pdf}{OAI:A-Counterexample-to-the-Infinite-Matroid-Packing-Covering-Conjecture-September-24-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The infinite matroid packing/covering conjecture predicts a partition of a common ground set into parts admitting the corresponding packing and covering. The formalization constructs two self-dual partitional matroids on one countably infinite ground set that admit neither an independent covering nor a packing/covering partition. The same pair has no intersection witness, so it also refutes the unrestricted infinite matroid intersection conjecture.

Separate formalized consequences give counterexamples to the individual covering and packing conjectures. The construction is in ordinary set theory with Choice and assumes no finitary restriction on the matroids.

Comparator links

ResultComparator statement
Infinite matroid packing/covering counterexampleInfiniteMatroid.lean
Partitional intersection, covering, and packing counterexamplesInfiniteMatroidCorollaries.lean

Scope note on GitHub →