OctoInformBeta

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

The Covering (7.1) and Packing (7.2) conjectures: Conjecturally, a family covers FF exactly when every Y⊆FY \subseteq F whose restrictions have a packing is covered by them; dually for packing, with contractions

The Covering and Packing Conjectures for a family of 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

Take a family (Mk)k∈K(M_k)_{k \in K} of matroids on a common ground set EE, indexed by an arbitrary set KK, and a set F⊆EF \subseteq E. Two questions are asked of it: whether FF is covered by independent sets of the matroids, one from each, and whether the matroids have pairwise disjoint spanning sets, one in each. The Covering Conjecture and the Packing Conjecture each tie one of these questions to a condition on the subsets YY of FF: the first through the restrictions of the matroids to YY, the second through their contractions onto YY.

Coverings, Packings and Contractions

A covering of a set FF 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, each independent in its matroid, whose union is FF: Ik is independent in Mk for every k∈K,⋃k∈KIk=F.I_k \text{ is independent in } M_k \text{ for every } k \in K, \qquad \bigcup_{k \in K} I_k = F.(1)✦ A family (Mk)k∈K(M_k)_{k \in K} of matroids covers a set FF when there is a covering of FF 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, each spanning in its matroid: Sk∩Sl=∅ for all k≠l,Sk is spanning in Mk for every k∈K.S_k \cap S_l = \emptyset \text{ for all } k \neq l, \qquad S_k \text{ is spanning in } M_k \text{ for every } k \in K.(2)✦

For a matroid MM on EE and a set C⊆EC \subseteq E, 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)^*.(3)✦

The Definition

Definition 1. Let (Mk)k∈K(M_k)_{k \in K} be a family of matroids on a set EE and let F⊆EF \subseteq E. The Covering Conjecture for (Mk)k∈K(M_k)_{k \in K} and FF is the statement (Mk)k∈K covers F⇔for every Y⊆F such that (Mk↾Y)k∈K has a packing,(Mk↾Y)k∈K covers Y.\begin{aligned} &(M_k)_{k \in K} \text{ covers } F \iff \text{for every } Y \subseteq F \text{ such that } (M_k \restriction Y)_{k \in K} \text{ has a packing},\\ &\qquad (M_k \restriction Y)_{k \in K} \text{ covers } Y. \end{aligned}(4)✦ The Packing Conjecture for (Mk)k∈K(M_k)_{k \in K} and FF is the statement (Mk)k∈K has a packing⇔for every Y⊆F such that (Mk.Y)k∈K covers Y,(Mk.Y)k∈K has a packing.\begin{aligned} &(M_k)_{k \in K} \text{ has a packing} \iff \text{for every } Y \subseteq F \text{ such that } (M_k.Y)_{k \in K} \text{ covers } Y,\\ &\qquad (M_k.Y)_{k \in K} \text{ has a packing}. \end{aligned}(5)✦

What Is Checked

Both conjectures are stated over an arbitrary family (Mk)k∈K(M_k)_{k \in K} of matroids on EE and an arbitrary set F⊆EF \subseteq E, through coverings (1), packings (2), restrictions to YY and contractions onto YY (3).