OctoInformBeta

OpenAI preprint, September 2026 · §7. The separate Covering and Packing conjectures

Corollary 7.1: For each conjecture a pair of matroids on a subset of EE violating it; pairs without a packing/covering partition yield counterexamples to both

Counterexamples to the separate Covering and Packing Conjectures.

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 covering of a set YY by a family (Mk)k∈K(M_k)_{k\in K} of matroids is a family (Ik)k∈K(I_k)_{k\in K} of sets with union YY and each IkI_k independent in MkM_k.✦ A set YY is covered by a family (Mk)k∈K(M_k)_{k\in K} of matroids when there is a covering of YY by (Mk)k∈K(M_k)_{k\in K}. A packing of a family (Mk)k∈K(M_k)_{k\in K} of matroids is a family (Sk)k∈K(S_k)_{k\in K} of pairwise disjoint sets with each SkS_k spanning in MkM_k.✦

The separate Covering and Packing Conjectures of Bowler and Carmesin propose, for a family of matroids on a common ground set FF, a test for each of these two properties in terms of the minors of the family on the subsets of FF.

The set DD is the countable set of pairs (m,f)(m, f) of a natural number mm and a Boolean function f:{0,1}m→{0,1}f\colon \{0,1\}^m \to \{0,1\}✦, and the double-ray ground set is E=ℤ×DE = \mathbb{Z} \times D✦. The question is whether the two tests are right for every pair of matroids on a subset of EE.

The Covering and Packing Equivalences

For a matroid MM and a set CC, the contraction M.CM.C of MM onto CC is the matroid (M*↾C)*(M^* \restriction C)^* on CC; when CC lies in the ground set of MM, it is MM with the elements outside CC contracted.✦ For a matroid MM and a set WW, the contraction M/WM/W of MM by WW is the matroid obtained from MM by contracting WW.

The Covering equivalence for a set FF and a family (Mk)k∈K(M_k)_{k\in K} of matroids is the statement F is covered by (Mk)⇔Y is covered by (Mk↾Y) for every Y⊆Fsuch that (Mk↾Y) has a packing,\begin{aligned} F \text{ is covered by } (M_k) \iff{} & Y \text{ is covered by } (M_k \restriction Y) \text{ for every } Y \subseteq F\\ & \text{such that } (M_k \restriction Y) \text{ has a packing}, \end{aligned}(1)✦ and the Packing equivalence for FF and (Mk)k∈K(M_k)_{k\in K} is the statement (Mk) has a packing⇔(Mk.Y) has a packing for every Y⊆Fthat is covered by (Mk.Y).\begin{aligned} (M_k) \text{ has a packing} \iff{} & (M_k.Y) \text{ has a packing for every } Y \subseteq F\\ & \text{that is covered by } (M_k.Y). \end{aligned}(2)✦

Waves and Packing/covering Partitions

A wave of a family (Mk)k∈K(M_k)_{k\in K} of matroids in a set FF is a pair (W,(Wk)k∈K)(W, (W_k)_{k\in K}) of a set W⊆FW \subseteq F and pairwise disjoint subsets WkW_k of WW such that W⊆cl⁡Mk(Wk)for every k∈K.W \subseteq \operatorname{cl}_{M_k}(W_k) \qquad \text{for every } k \in K.(3)✦ A wave (W,(Wk)k∈K)(W, (W_k)_{k\in K}) of (Mk)(M_k) in FF is maximal when every wave (W′,(Wk′)k∈K)(W', (W'_k)_{k\in K}) of (Mk)(M_k) in FF with W⊆W′W \subseteq W' and Wk⊆Wk′W_k \subseteq W'_k for every kk equals it.

Two matroids M0M_0 and M1M_1 admit a packing/covering partition, in the sense of the Packing/Covering Conjecture of Bowler and Carmesin, when they have a common ground set FF and FF is the union of disjoint sets PP and CC such that (M0↾P,M1↾P)(M_0 \restriction P, M_1 \restriction P) has a packing and CC is covered by (M0.C,M1.C)(M_0.C, M_1.C).✦

The Claim

Theorem 1.

  1. There are sets F,F′⊆EF, F' \subseteq E, two matroids M0M_0, M1M_1 on FF and two matroids M0′M'_0, M1′M'_1 on F′F' such that the Covering equivalence fails for F and (M0,M1),the Packing equivalence fails for F′ and (M0′,M1′).\begin{gathered} \text{the Covering equivalence fails for } F \text{ and } (M_0, M_1),\\ \text{the Packing equivalence fails for } F' \text{ and } (M'_0, M'_1). \end{gathered}(4)✦

  2. For every family (Mk)k∈K(M_k)_{k\in K} of matroids and every set FF, (Mk) has a maximal wave in F.(M_k) \text{ has a maximal wave in } F.(5)✦

  3. Let (Mk)k∈K(M_k)_{k\in K} be a family of matroids on FF and (W,(Wk)k∈K)(W, (W_k)_{k\in K}) a maximal wave of it in FF. Then for every Y⊆F\WY \subseteq F \setminus W such that ((Mk/W)↾Y)((M_k/W) \restriction Y) has a packing, Y is covered by ((Mk/W)↾Y).Y \text{ is covered by } \bigl((M_k/W) \restriction Y\bigr).(6)✦

  4. Let M0M_0, M1M_1 be two matroids on FF and (W,(W0,W1))(W, (W_0, W_1)) a wave of (M0,M1)(M_0, M_1) in FF such that F\WF \setminus W is covered by (M0/W,M1/W)(M_0/W, M_1/W). Then M0 and M1 admit a packing/covering partition.M_0 \text{ and } M_1 \text{ admit a packing/covering partition}.(7)✦

  5. For two matroids M0M_0, M1M_1 on FF, F is covered by (M0,M1)⇔(M0*,M1*) has a packing.F \text{ is covered by } (M_0, M_1) \iff (M_0^*, M_1^*) \text{ has a packing}.(8)✦

  6. Let M0M_0, M1M_1 be two matroids on FF that admit no packing/covering partition. Then there are a set CC and two matroids N0N_0, N1N_1 on CC such that C is not covered by (N0,N1),Y is covered by (N0↾Y,N1↾Y) for every Y⊆Csuch that (N0↾Y,N1↾Y) has a packing.\begin{aligned} &C \text{ is not covered by } (N_0, N_1),\\ &Y \text{ is covered by } (N_0 \restriction Y, N_1 \restriction Y) \text{ for every } Y \subseteq C\\ &\qquad \text{such that } (N_0 \restriction Y, N_1 \restriction Y) \text{ has a packing}. \end{aligned}(9)✦

  7. Let M0M_0, M1M_1 be two matroids on FF such that FF is not covered by (M0,M1)(M_0, M_1) and every Y⊆FY \subseteq F for which (M0↾Y,M1↾Y)(M_0 \restriction Y, M_1 \restriction Y) has a packing is covered by it. Then the Packing equivalence fails for F and (M0*,M1*).\text{the Packing equivalence fails for } F \text{ and } (M_0^*, M_1^*).(10)✦

In the paper, the result reads: the unrestricted separate Covering and Packing Conjectures of Bowler and Carmesin are both false in Zermelo-Fraenkel set theory with the axiom of choice (ZFC).

What Is Checked

The claim is stated over matroids given by bases with the maximality axiom, the sets DD and E=ℤ×DE = \mathbb{Z} \times D, coverings and packings of families of matroids, the contraction M.CM.C onto a set, the Covering and Packing equivalences (1) and (2), waves (3) with their maximality, and packing/covering partitions.