OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Corollary 1.2: The ray matroids M0,M1M_0, M_1 of a self-dual uniform matroid on E0E_0, both self-dual, with no packing/covering partition and no independent cover

Intersection fails for two partitional matroids on a countable set.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A pair (M,N)(M, N) of matroids on a common ground set EE satisfies intersection when there are a set JJ independent in both MM and NN and a partition of JJ into sets J0J_0 and J1J_1 with clM(J0)∪clN(J1)=E.\mathrm{cl}_M(J_0) \cup \mathrm{cl}_N(J_1) = E.(1)✦ The Matroid Intersection Conjecture asserts that every such pair satisfies intersection.

A matroid MM is uniform when every subset of its ground set is independent or spanning in MM.✦ A matroid MM on a set XX is partitional when there are uniform matroids NλN_\lambda on sets BλB_\lambda, indexed by λ\lambda in a set Λ\Lambda, and a bijection ee from the disjoint union of the BλB_\lambda onto XX with M=e(⨁λ∈ΛNλ).M = e\Bigl(\bigoplus_{\lambda \in \Lambda} N_\lambda\Bigr).(2)✦

The question here is whether intersection can fail for two partitional matroids on a countable ground set. The pair examined is made of the two ray matroids of one self-dual uniform matroid QQ: copies of QQ laid along the integers, at the even integers for one matroid and at the odd integers for the other.

Ray Matroids

The set DD is the countable set of pairs (m,f)(m, f) with mm a natural number and f:{0,1}m→{0,1}f \colon \{0,1\}^m \to \{0,1\}.✦ The set E0=D×{false,true}E_0 = D \times \{\mathrm{false}, \mathrm{true}\} is the disjoint union L⊔RL \sqcup R of two copies of DD, the left copy LL made of the pairs with second entry false and the right copy RR of those with second entry true.✦ The ground set E=ℤ×DE = \mathbb{Z} \times D is the union of the bundles en={n}×De_n = \{n\} \times D for n∈ℤn \in \mathbb{Z}.✦

Let AA be a set and QQ a matroid on A×{L,R}A \times \{L, R\}, its two halves named as in E0E_0. For a parity p∈{0,1}p \in \{0, 1\}, the vertices of parity pp are the integers vv with v≡p(mod⁡2)v \equiv p \pmod 2.✦ Each such vertex vv carries a copy of QQ, placed on the two bundles {v−1}×A\{v - 1\} \times A and {v}×A\{v\} \times A by the map βv:A×{L,R}→ℤ×A\beta_v \colon A \times \{L, R\} \to \mathbb{Z} \times A, βv(a,L)={(v−1,a),v≥0,(v,a),v<0,βv(a,R)={(v,a),v≥0,(v−1,a),v<0.\beta_v(a, L) = \begin{cases} (v - 1, a), & v \ge 0,\\ (v, a), & v < 0, \end{cases} \qquad \beta_v(a, R) = \begin{cases} (v, a), & v \ge 0,\\ (v - 1, a), & v < 0. \end{cases}(3)✦ The ray matroid Mp(Q)M_p(Q) of parity pp is the matroid on ℤ×A\mathbb{Z} \times A obtained from the direct sum of one copy of QQ for each vertex vv of parity pp by sending each element xx of the copy at vv to βv(x)\beta_v(x): Mp(Q)=β(⨁v≡p(mod2)Q),β(v,x)=βv(x).M_p(Q) = \beta\Bigl(\bigoplus_{v \equiv p \ (\mathrm{mod}\ 2)} Q\Bigr), \qquad \beta(v, x) = \beta_v(x).(4)✦ For a matroid QQ on E0E_0 we write M0=M0(Q)M_0 = M_0(Q) and M1=M1(Q)M_1 = M_1(Q), two matroids on EE.

Packing and Covering

For a matroid MM and a subset CC of its ground set, the contraction of MM onto CC is the matroid M.C=(M*↾C)*M.C = (M^* \restriction C)^* on CC.✦

A pair (M,N)(M, N) of matroids on a common ground set EE has a packing/covering partition when there are disjoint sets PP and CC with E=P∪CE = P \cup C, disjoint sets S0,S1⊆PS_0, S_1 \subseteq P and sets I0,I1⊆CI_0, I_1 \subseteq C such that S0 is spanning in M↾P,S1 is spanning in N↾P,I0 is independent in M.C,I1 is independent in N.C,I0∪I1=C.\begin{aligned} &S_0 \text{ is spanning in } M \restriction P, &\quad &S_1 \text{ is spanning in } N \restriction P,\\ &I_0 \text{ is independent in } M.C, &\quad &I_1 \text{ is independent in } N.C, \qquad I_0 \cup I_1 = C. \end{aligned}(5)✦ Two matroids MM and NN on a common ground set EE have an independent cover when EE is the union of a set independent in MM and a set independent in NN.

The Claim

Theorem 1.

  1. The set EE is countably infinite, and there is a uniform matroid QQ on E0E_0 with Q*=QQ^* = Q whose ray matroids M0M_0 and M1M_1 are partitional and satisfy M0*=M0,M1*=M1,M_0^* = M_0, \qquad M_1^* = M_1,(6)✦ and for which the pair (M0,M1)(M_0, M_1) has no independent cover, has no packing/covering partition and does not satisfy intersection.

  2. Let MM and NN be matroids with the same ground set such that (M,N)(M, N) satisfies intersection. Then (M,N*) has a packing/covering partition.(M, N^*) \text{ has a packing/covering partition.}(7)✦

  3. Let AA be a set, QQ a uniform matroid on A×{L,R}A \times \{L, R\} and p∈{0,1}p \in \{0, 1\}. Then Mp(Q) is partitional.M_p(Q) \text{ is partitional.}(8)✦

In the paper, the result reads: the pair (M0,M1)(M_0, M_1) of Theorem 1.1 consists of partitional matroids and does not satisfy intersection, in that clM0(J0)∪clM1(J1)≠E\mathrm{cl}_{M_0}(J_0) \cup \mathrm{cl}_{M_1}(J_1) \neq E for every set JJ independent in both and every partition J=J0⊔J1J = J_0 \sqcup J_1; hence the unrestricted infinite Matroid Intersection Conjecture is false in Zermelo-Fraenkel set theory with choice, and Joó’s Question 1.5 has a negative answer for two partitional matroids on a common countable ground set.

What Is Checked

The claim is stated over the sets DD, E0E_0 and EE, the ray matroids (4) with their placements (3), uniform and partitional matroids (2), the contraction onto a set, independent covers, packing/covering partitions (5) and intersection (1).

About these constructions, the library also shows that for each parity pp the map β\beta of (4) is a bijection from the pairs (v,x)(v, x), with vv a vertex of parity pp and x∈A×{L,R}x \in A \times \{L, R\}, onto ℤ×A\mathbb{Z} \times A.✦