Where unrestricted infinite matroid packing and covering break down

← All digests

Family 185 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Linear independence and cycle-free edge sets share a common combinatorial structure called a matroid. For finite matroids, powerful theorems explain when independent or spanning sets can be packed, covered or chosen simultaneously in two systems.

How much survives when the ground set is infinite? An unrestricted conjecture proposed a partition into one region admitting disjoint spanning sets and another region admitting an independent covering, with contraction used on the second region.

The manuscript claims a counterexample using only two matroids on a countably infinite ground set. Both are self-dual and are direct sums of uniform matroids, yet they admit neither the proposed packing/covering partition nor an intersection witness. The examples are not finitary, so they do not refute the original finitary intersection conjecture or the established positive results for that setting.

2. Background and essential definitions

A matroid specifies which subsets of a ground set $E$ are independent. Familiar examples are linearly independent subsets of a collection of vectors, or edge sets containing no cycle in a finite graph.

Independence is hereditary: every subset of an independent set is independent. There is also an exchange principle allowing a nonmaximal independent set to be enlarged using an element from a maximal one. In the infinite theory, a further axiom requires every independent set to extend to a maximal independent set inside every prescribed containing subset of $E$. This maximal-extension requirement is essential; finite-style exchange rules alone are not enough.

A basis is a maximal independent set. A set is spanning if it contains a basis. The closure $\operatorname{cl}_M(S)$ consists of elements determined by $S$ in the matroid sense, analogous to the vectors lying in a linear span. Spanning means $\operatorname{cl}_M(S)=E$.

Restriction $M\mathbin{\upharpoonright}P$ keeps only the elements of $P$. The dual matroid $M^*$ has complements of bases as its bases. Contraction onto $C$ is defined by

$$M.C=(M^*\mathbin{\upharpoonright}C)^*.$$

It models the residual independence structure after the elements outside $C$ have been contracted. Restriction and contraction are different operations.

For two matroids, a packing is a pair of disjoint spanning sets, one for each system. A covering is a pair of independent sets whose union is the ground set. A packing/covering partition divides

$$E=P\mathbin{\dot\cup}C$$

so the restrictions to $P$ admit a packing and the contractions onto $C$ admit a covering.

A matroid is self-dual here when $M=M^*$ on the same labeled set, not merely after relabeling. It is finitary when a set is independent whenever all its finite subsets are independent. It is cofinitary when its dual is finitary.

3. Development history and previous partial results

Finite matroid intersection, packing and covering theorems are central results of combinatorial optimization. Extending them to infinity requires replacing numerical rank comparisons with structural witnesses and choosing axioms that support restriction, contraction and duality.

Bruhn, Diestel, Kriesell, Pendavingh and Wollan developed the standard infinite-matroid axioms used here. Bowler and Carmesin formulated the packing/covering conjecture and established its relationships with infinite intersection and separate packing and covering statements.

The intersection question originated in a more restricted form associated with Nash-Williams: finitary matroids. Joó proved intersection for two finitary matroids on a countable ground set. His later packing/covering theorem allows every set-indexed family on a countable ground set whose members are direct sums of finitary and cofinitary matroids.

Uniform matroids form another natural class. In the infinite setting used here, uniformity means that exchanging any basis element with any element outside that basis again produces a basis. Equivalently, every subset is independent or spanning. This should not be interpreted as a fixed finite cardinality cutoff.

Bowler and Geschke constructed countable self-dual uniform examples under additional set-theoretic assumptions, leaving their existence in ZFC open. ZFC is the usual Zermelo–Fraenkel axiom system with the axiom of choice. The new manuscript claims such a uniform matroid in ZFC as a building block.

Joó also proved intersection when one matroid is a direct sum of finitely many uniform matroids and the other is arbitrary. He asked about two partitional matroids on a countable set, where partitional means a direct sum of uniform components. The present construction uses countably infinitely many components and claims a negative answer to that question.

4. What the new manuscripts claim

The main theorem asserts that in ZFC there are two matroids $M_0,M_1$ on the same countably infinite set $E$, each self-dual, such that

$$I_0\cup I_1\ne E$$

whenever $I_0$ is independent in $M_0$ and $I_1$ is independent in $M_1$. Thus no independent covering exists.

The paper separately proves that for a self-dual pair, a mixed packing/covering partition would imply an independent covering of the whole ground set. This additional reduction is necessary: failure of a covering alone would not rule out every mixed partition for arbitrary matroids.

Each constructed matroid is partitional. The local component $Q$ is a self-dual uniform matroid on a countable set, with every basis and its complement infinite. The manuscript thereby also claims a ZFC solution to the uniform-matroid existence questions described above.

For intersection, the usual witness is a set $J$ independent in both matroids, partitioned as $J=J_0\mathbin{\dot\cup}J_1$, with

$$\operatorname{cl}_{M_0}(J_0) \cup\operatorname{cl}_{M_1}(J_1)=E.$$

The manuscript states that its pair has no such witness. This follows through Bowler and Carmesin’s established equivalence between intersection for $(M,N)$ and packing/covering for $(M,N^*)$, together with self-duality.

The paper also deduces that the unrestricted separate universal Packing and Covering conjectures are false. Those deductions use equivalences between universal statements. It does not identify the same pair as the direct witnessing family for every separate formulation.

5. Why the advance matters

Importance: 4/5. The claim sets a sharp boundary on how far finite matroid principles can be generalized without structural assumptions. Countability of the ground set and decomposition into uniform components do not by themselves suffice.

The result also illustrates a characteristic infinite phenomenon. Every finite subset of the constructed ground set is independent, yet the entire set is dependent. Finite tests therefore cannot detect the obstruction. The counterexample exploits precisely the behavior excluded by finitary hypotheses.

The local self-dual uniform construction has independent significance because it is claimed within ordinary ZFC, without the continuum hypothesis or the extra assumptions used in earlier constructions. The rating reflects both the failure of broad conjectures and this new building block, while keeping the established finitary theory clearly outside the negative conclusion.

6. The main idea

Force a quantity to decrease forever

The final obstruction uses ordinals, which generalize nonnegative integers as well-ordered positions. Like nonnegative integers, ordinals cannot form an infinite strictly decreasing sequence: any nonempty collection of them has a least element.

The manuscript equips certain large subsets of a countable set $D$ with an ordinal-valued quantity $\rho$. This is an auxiliary rank, not matroid rank. Largeness is defined by an ultrafilter: a coherent collection closed under supersets and finite intersections that chooses exactly one side of every complementary pair of subsets.

On two labeled copies $L,R$ of $D$, the local matroid $Q$ is constructed so that a basis with a large left slice forces a large complement of its right slice and a strict decrease:

$$\rho(B_L)>\rho(D\setminus B_R).$$

The auxiliary rank also behaves monotonically in the direction needed to pass from independent sets to containing bases.

Arrange the components along a two-sided path

Take vertices indexed by all integers and place a copy of $D$ in each bundle between consecutive vertices. At every vertex, place one copy of $Q$ on its two incident bundles. Its left coordinate points toward a central bundle, and its right coordinate points outward.

The components at even-indexed vertices form $M_0$; those at odd-indexed vertices form $M_1$. Within either parity, the component supports partition the common ground set, so these are direct sums of uniform matroids.

Suppose independent sets from the two matroids covered everything. They can be made into a partition by removing overlap. Assign each bundle element to the endpoint whose matroid receives it.

The ultrafilter selects one large side of the central bundle. Follow the path outward from that side. At every vertex, extend the received independent set to a basis of its local component. The defining inequality then forces the ordinal rank to decrease strictly at the next bundle. Continuing outward would produce an impossible infinite descending sequence.

Build the local matroid without losing maximal extension

Most of the paper constructs $Q$. It partitions $D$ into rapidly growing finite blocks and compares subsets modulo sets whose block densities tend to zero. Within each resulting class, real-valued probes select bases using interval conditions.

Finite exchanges shift these probes by controlled integer amounts, supporting the uniform basis-exchange property. A separate interpolation argument ensures that bases can be found between suitable subset endpoints.

The construction processes all required intervals through a transfinite recursion, choosing complementary classes together to preserve self-duality. Additional reservations keep the ordinal inequalities compatible with earlier choices. The maximal-extension axiom is then established for every prescribed subset, completing the infinite-matroid structure needed for the final path argument.

7. Scope, limitations, and open questions

The counterexample is unrestricted and nonfinitary. It does not refute Nash-Williams’ original finitary intersection conjecture. It also lies outside Joó’s positive countable packing/covering theorem for direct sums of finitary and cofinitary matroids.

Indeed, the manuscript states that its examples have no nonempty finitary or cofinitary direct summand. Their failure is not caused by adding a small pathological component to an otherwise covered class.

The ground set is countable, but its family of subsets is uncountable. The construction uses choice, ultrafilters and transfinite recursion over subset requirements. It is an existence construction in ZFC, not an efficiently encoded finite counterexample or an algorithm for a finite optimization problem.

Self-duality means equality on the same labels and is used in the reduction from a mixed partition to a full covering. Merely knowing that a matroid is isomorphic to its dual would require additional care.

The broader lesson for further questions is structural: which infinite matroid classes still admit intersection or packing/covering witnesses? The theorem excludes the unrestricted formulation while leaving stronger hypotheses meaningful and, in several countable cases, already supported by positive results.

8. Sources and further reading

The manuscript states its packing/covering and intersection conventions explicitly, constructs the local uniform component, and finishes with the ordinal descent on a two-sided path.

Primary context comes from Bowler–Carmesin’s equivalence framework, Joó’s partitional intersection theorem and question, and Joó’s positive countable packing/covering theorem. The source bibliography identifies the standard infinite-matroid axioms and Bowler–Geschke’s earlier self-dual uniform constructions under additional set-theoretic assumptions.

Source manuscripts

• M1. OpenAI, A Counterexample to the Infinite Matroid Packing/Covering Conjecture (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.