Infinite matroid packing, covering, and intersection

Source and verification

This article explains family 185 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Independent sets beyond finite ground sets

A matroid abstracts independence, as in linearly independent vector sets or forests in a graph. Independent sets are closed under taking subsets and satisfy an exchange principle. For an infinite ground set, an additional maximal-extension requirement is indispensable: every independent set contained in $X$ must extend to a maximal independent subset of $X$.

A basis is a maximal independent set of the whole ground set. A spanning set contains a basis. The dual matroid has as bases the complements of the original bases. Self-duality on a labeled ground set means equality with this dual using the same elements, not merely an isomorphism after relabeling.

This post focuses on the combinatorial statement and the final obstruction. The set-theoretic construction of its auxiliary objects is identified as an input rather than developed as a separate logic topic.

🏷️ Packing and covering use different minors

For matroids $M_i$ on the same ground set $E$, a packing chooses pairwise disjoint spanning sets. A covering chooses independent sets whose union is $E$.

The packing/covering conjecture asks for a partition $E=P\dot{\cup }C$ such that the restrictions to $P$ admit a packing, while the contractions onto $C$ admit a covering. Restriction simply keeps elements of $P$. Contraction onto $C$ first accounts for the elements outside $C$; its independence condition is not generally the same as independence in the restriction to $C$.

Manuscript claim

There are two self-dual infinite matroids $M_0,M_1$ on one countably infinite ground set for which no two independent sets, one from each matroid, cover the ground set. The pair has no packing/covering partition and no infinite-matroid intersection witness. The construction uses ordinary set theory with Choice. (OpenAI, 2026)

Failure of an independent covering alone would not rule out a mixed partition for arbitrary matroids. The source proves the additional implication for its self-dual pair by combining restriction-spanning sets with contraction-independent sets and then taking complementary sets through duality.

🏷️ The intersection formulation

An intersection witness is a common independent set $J$ with a partition $J=J_0\dot{\cup }{J}_1$ whose closures cover $E$:

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

Here closure consists of elements already spanned by the given set. The established equivalence used in the source relates intersection for $(M,N)$ to packing/covering for $(M,N^{\ast })$. Since the constructed second matroid is self-dual on the same labels, the pair failing packing/covering is exactly the pair failing intersection.

The examples are direct sums of countably many uniform matroids. In a uniform matroid, replacing any basis element by any element outside the basis gives another basis. Such direct sums are called partitional. Countably many summands are important; a theorem for finitely many uniform summands would not cover these examples.

🏷️ A local obstruction placed along a path

The construction first produces a self-dual uniform matroid $Q$ on two labeled copies $L,R$ of a countable set $D$. An auxiliary notion of a large subset of $D$ chooses one side of every complementary pair. Large sets carry a well-ordered rank $\rho$, distinct from matroid rank, with the monotonicity rule

$$\begin{array}{c}X\subseteq Y\text{ large}\\ ⟹\rho (X)\ge \rho (Y).\end{array}$$

The crucial basis property is that if the left slice $B_L$ of a basis is large, then $D\setminus B_R$ is large and

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

Place a countable bundle of elements between each pair of consecutive vertices of a doubly infinite path. At every path vertex, put a copy of $Q$ on its two incident bundles, orienting its left coordinate toward a fixed central bundle. Copies at even vertices form $M_0$ and copies at odd vertices form $M_1$.

In a hypothetical independent covering, extend the relevant local independent sets to bases. Starting from a large side of the central bundle, the basis property and monotonicity force a strictly decreasing sequence of well-ordered ranks as one moves outward. No such infinite decreasing sequence exists. This is the final combinatorial contradiction.

🏷️ Why basis exchange is not enough

Most of the source is devoted to constructing $Q$ with all the required axioms. The ground set is partitioned into rapidly growing finite blocks. Real-valued probes of subsets and half-open interval conditions define candidate bases; balanced finite changes make the exchange calculations work.

The harder obligation is maximal extension inside every prescribed subset. A separate interpolation argument inserts bases between suitable endpoints, including cases with infinite limiting probe values. Complementary classes are assembled while preserving the rank inequalities and satisfying all these interval requirements.

Without maximal extension, one could obtain a suggestive independence system that is not an infinite matroid. The source explicitly treats that axiom rather than relying on the finite basis-exchange analogy.

🏷️ Structural limits of the counterexample

A matroid is finitary if a set is independent whenever all its finite subsets are independent. It is cofinitary if its dual is finitary. The constructed examples are neither, and have no nonempty summands of these types.

Consequently, the claim concerns unrestricted infinite matroids. It does not refute the original finitary intersection conjecture or the established countable results under finitary/cofinitary hypotheses. Countability of the ground set does not supply those structural conditions.

The source also derives failure of separate universal packing and covering assertions through equivalences. Those consequences do not identify their witnesses with this exact pair; the direct pair is the witness for the combined and intersection statements above.

🏷️ Key steps and proof outlines

The local interface: independence forces a strict rank drop

The construction uses a self-dual matroid $Q$ on two labeled copies $L\bigsqcup R$ of a set $D$. Its technical construction supplies a notion of “large” subset of $D$ and an ordinal-valued rank $\rho$ on large subsets. Exactly one of a set and its complement is large, and every superset of a large set is large. Rank is antitone under inclusion: if large sets satisfy $X\subseteq Y$, then $\rho (X)\ge \rho (Y)$.

The decisive basis property is this: whenever a basis $B$ has a large left trace $B_L$, its omitted right trace $D\setminus B_R$ is large and

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

The source also arranges that every finite set is independent although the whole ground set is dependent. These are precise inputs from the local construction; the following argument explains how they produce the packing-covering obstruction. It does not replace the local construction by an unproved claim that every self-dual matroid has such a rank. (OpenAI, 2026)

Put local copies on a doubly infinite chain

Let $E=\mathbb{Z}\times D$, and call $e_n=\{n\}\times D$ the bundle between vertices $v_n$ and $v_{n+1}$. Place a copy $Q_n$ of $Q$ on the two incident bundles at $v_n$. Orient its left side toward the central bundle $e_{-1}$: for $n\le -1$ take $L=e_n,R=e_{n-1}$, and for $n\ge 0$ take $L=e_{n-1},R=e_n$.

Let $M_0$ be the direct sum over even vertices and $M_1$ the direct sum over odd vertices. Within either parity, the component ground sets are disjoint and cover $E$. This makes the direct sum a legitimate infinite matroid: to extend an independent set maximally inside a prescribed set, extend it in each component and take the union. Componentwise complements of bases also show that both sums are self-dual.

Suppose independent sets $J_0$ of $M_0$ and $J_1$ of $M_1$ cover $E$. Replace $J_1$ by $E\setminus J_0$, a subset of the old $J_1$, so the cover becomes a partition. Exactly one of the two assigned traces on the central bundle is large. Follow the chain outward on that side.

The contradiction is a descending ordinal sequence

Let $x_k$ be the large inward trace assigned to the current matroid, and $z_k$ its outward trace. The next matroid receives $x_{k+1}=D\setminus z_k$. Extend the current local independent set to a basis $B_k$. Its left trace $u_k$ contains $x_k$, while its omitted right trace $y_k$ is contained in $x_{k+1}$. Therefore

$$\rho (x_k)\ge \rho (u_k)>\rho (y_k)\ge \rho (x_{k+1}).$$

The local basis property makes $y_k$, and hence $x_{k+1}$, large. Thus the argument iterates forever, producing an impossible infinite strictly decreasing sequence of ordinals.

The extension-to-a-basis step is essential: the rank-drop interface is stated for bases, whereas the supposed cover initially supplies only independent sets. Antitonicity transports the basis inequality back to those independent traces.

Why ruling out a cover also rules out a mixed decomposition

A packing-covering decomposition would split $E=P\bigsqcup C$. On $P$, it supplies disjoint spanning sets $S_0,S_1$ in the restrictions $M_i|P$. On $C$, it supplies independent sets $I_0,I_1$ in the contractions $M_i.C$ that cover $C$.

Self-duality gives

$$M_i.C=(M_i|C{)}^{\ast }.$$

Consequently $T_i=C\setminus I_i$ spans $M_i|C$, and $T_0,T_1$ are disjoint. The union $A_i=S_i\cup T_i$ spans $M_i$: each part spans its own restriction, so their closures together contain $P\cup C$. The sets $A_0,A_1$ remain disjoint. By self-duality, their complements are independent in $M_0,M_1$, respectively, and those complements cover $E$. This is exactly the independent cover already ruled out by ordinal descent.

Locate the boundary of the counterexample

The result depends on genuinely infinite dependence. Because every finite subset is independent but the entire ground set is not, these matroids are not finitary. Nor can a nonempty finitary direct summand be hidden inside: all its finite subsets would be independent, hence all its subsets would be independent. Its ground set would then belong to every global basis. Self-duality would make complements of global bases into bases as well, a contradiction. The corresponding cofinitary conclusion follows by duality.

These checks explain which hypotheses prevent the example from contradicting positive results for more restricted classes. The global construction and its reductions occur in “The counterexample,” with the direct-sum and duality conventions established in the preliminary matroid section.

See Also

• Thin spanning trees uses finite graphic-matroid packing, where finite rank and partition criteria have a different scope.
• Hypergraph covering counterexamples treats another packing/covering comparison with its own distinct independence notion.

🏷️ Manuscripts and verification scope

• A Counterexample to the Infinite Matroid Packing/Covering Conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the self-dual partitional pair on a countable ground set and its intersection obstruction, plus separate universal packing and covering counterexamples. No finitary hypothesis is imposed. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A Counterexample to the Infinite Matroid Packing/Covering Conjecture.