OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Packing/covering partitions and contraction onto a set: The set DD of Boolean functions, E0=D×{L,R}E_0 = D \times \{L, R\}, E=ℤ×DE = \mathbb{Z} \times D, and the contraction M.C=(M*↾C)*M.C = (M^* \restriction C)^* the covering part uses

The ground sets and the packing/covering partition of two matroids.

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 M0M_0 and M1M_1 be two matroids on one ground set. Two matroids M0M_0 and M1M_1 on a common ground set pack when they have disjoint spanning sets, and cover when the ground set is the union of an independent set of M0M_0 and an independent set of M1M_1. The packing/covering conjecture asks whether the ground set always splits into a part on which the restrictions of M0M_0 and M1M_1 pack and a part on which their contractions onto it cover.

Alongside the partition, the item fixes the ground sets built from Boolean functions of every arity: a countable set DD, two copies of DD side by side, and one copy of DD at each integer.

The Definition

Definition 1. The set DD consists of the pairs (m,f)(m, f) of a natural number mm and a Boolean function ff on {0,1}m\{0,1\}^m: D={(m,f):m∈ℕ,f:{0,1}m→{0,1}}.D = \{(m, f) : m \in \mathbb{N},\ f \colon \{0,1\}^m \to \{0,1\}\}.(1)✦ The small ground set E0E_0 is the disjoint union of a left copy LL and a right copy RR of DD: E0=D×{false,true}=L⊔R,L=D×{false},R=D×{true}.E_0 = D \times \{\mathrm{false}, \mathrm{true}\} = L \sqcup R, \qquad L = D \times \{\mathrm{false}\}, \quad R = D \times \{\mathrm{true}\}.(2)✦ The ground set EE holds a copy en={n}×De_n = \{n\} \times D of DD for each integer nn: E=ℤ×D.E = \mathbb{Z} \times D.(3)✦ For a matroid MM and a set CC, the contraction of MM onto CC is the matroid M.CM.C on CC given by M.C=(M*↾C)*.M.C = (M^* \restriction C)^*.(4)✦ Let M0M_0 and M1M_1 be matroids with the same ground set. A packing/covering partition of (M0,M1)(M_0, M_1) consists of disjoint sets PP and CC whose union is that ground set, disjoint sets S0,S1⊆PS_0, S_1 \subseteq P, and sets I0,I1⊆CI_0, I_1 \subseteq C such that Si spans Mi↾P and Ii is independent in Mi.C(i=0,1),I0∪I1=C.S_i \text{ spans } M_i \restriction P \text{ and } I_i \text{ is independent in } M_i.C \quad (i = 0, 1), \qquad I_0 \cup I_1 = C.(5)✦ The pair (M0,M1)(M_0, M_1) has a packing/covering partition when such sets exist.

In the paper, the result reads: M.X=(M*↾X)*M.X = (M^* \restriction X)^*, and a packing/covering partition of (M0,M1)(M_0, M_1) on their common ground set is a split of it as P⊔CP \sqcup C with disjoint S0,S1⊆PS_0, S_1 \subseteq P spanning Mi↾PM_i \restriction P and Ii⊆CI_i \subseteq C independent in Mi.CM_i.C with I0∪I1=CI_0 \cup I_1 = C.

What Is Checked

The ground sets (1), (2) and (3) are built from the integers and Boolean functions, and the contraction (4) and the partition (5) are stated over arbitrary matroids given by bases with the maximality axiom, through their duals, restrictions, spanning sets and independent sets.