OctoInformBeta

OpenAI preprint, September 2026 · §2. Matroids and the self-dual reduction

Lemma 2.2: If self-dual matroids N0N_0 and N1N_1 on FF have a packing/covering partition, then FF is the union of an independent set of each

For self-dual matroids, packing/covering partitions give covers by independent sets.

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

Let N0N_0 and N1N_1 be matroids on a set FF. A matroid NN on FF is self-dual when N*=NN^* = N on the same labelled set FF. The packing/covering conjecture for a pair of self-dual matroids asks: when N0N_0 and N1N_1 have a packing/covering partition of FF, is FF the union of an independent set of N0N_0 and an independent set of N1N_1?

Contraction and Packing/covering Partitions

For a matroid MM on FF and a set C⊆FC \subseteq F, the contraction of MM onto CC is the matroid M.CM.C on CC obtained from MM by contracting every element outside CC: M.C=(M*↾C)*.M.C = (M^* \restriction C)^*.(1)✦

A packing/covering partition for two matroids N0N_0 and N1N_1 on FF is a partition F=P⊔CF = P \sqcup C into a packing side PP and a covering side CC, together with disjoint sets S0,S1⊆PS_0, S_1 \subseteq P and sets I0,I1⊆CI_0, I_1 \subseteq C, such that for i=0,1i = 0, 1 Si spans Ni↾P,Ii is independent in Ni.C,I0∪I1=C.S_i \text{ spans } N_i \restriction P, \qquad I_i \text{ is independent in } N_i.C, \qquad I_0 \cup I_1 = C.(2)✦

The Claim

Theorem 1. Let FF be a set.

(a) If N0N_0 and N1N_1 are self-dual matroids on FF that have a packing/covering partition, then there are a set J0J_0 independent in N0N_0 and a set J1J_1 independent in N1N_1 with J0∪J1=F.J_0 \cup J_1 = F.(3)✦

(b) If MM is a self-dual matroid on FF, C⊆FC \subseteq F and II is independent in M.CM.C, then C\I spans M↾C.C \setminus I \text{ spans } M \restriction C.(4)✦

(c) If MM is a matroid on FF, P∪C=FP \cup C = F, S⊆PS \subseteq P spans M↾PM \restriction P and T⊆CT \subseteq C spans M↾CM \restriction C, then S∪T spans M.S \cup T \text{ spans } M.(5)✦

(d) If MM is a self-dual matroid on FF and AA spans MM, then F\A is independent in M.F \setminus A \text{ is independent in } M.(6)✦

In the paper, the result reads: if N0N_0 and N1N_1 are matroids on FF with Ni=Ni*N_i = N_i^*, if F=P⊔CF = P \sqcup C, if disjoint sets S0,S1⊆PS_0, S_1 \subseteq P span N0↾PN_0 \restriction P and N1↾PN_1 \restriction P, and if sets IiI_i independent in Ni.CN_i.C satisfy I0∪I1=CI_0 \cup I_1 = C, then FF is covered by one independent set of each of N0N_0 and N1N_1.

What Is Checked

The theorem is stated over matroids on FF with their duals, restrictions, independent sets and spanning sets, over the contraction M.CM.C of (1), and over the packing/covering partition of (2).