OctoInformBeta

OpenAI preprint, September 2026 · §2. The paired-ground-set reduction · §2

The paired matroid and transversals: A set AA is a common basis of matroids M1,M2M_1, M_2 on EE exactly when the transversal S(A)S(A) is a basis of M1⊕M2*M_1 \oplus M_2^*

Common bases of two matroids as transversal bases of one matroid.

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 M1M_1 and M2M_2 be matroids on the ground set [n]={0,1,…,n−1}[n] = \{0, 1, \dots, n-1\}, and let ZZ be the number of their common bases, the sets that are a basis of M1M_1 and a basis of M2M_2. Approximate counting of ZZ begins by trading the two matroids for one: a matroid KK on the paired ground set V=[n]⊔[n]V = [n] \sqcup [n], whose 2n2n elements come in nn pairs, one for each element of [n][n]. The question is how a common basis of M1M_1 and M2M_2 shows up among the bases of KK, and what rank KK has.

The Claim

Definition 1. Let M1M_1 and M2M_2 be matroids whose ground sets lie in a set EE, and write E⊔EE \sqcup E for the disjoint union of two copies of EE, in which inli\mathrm{inl}\, i and inri\mathrm{inr}\, i are the copies of i∈Ei \in E in the first and the second summand. The paired matroid KK of M1M_1 and M2M_2 is the direct sum of M1M_1, placed on the first copy of EE, and the dual M2*M_2^* of M2M_2, placed on the second: K=M1⊕M2*.K = M_1 \oplus M_2^{*}.(1)✦ The slot pair pip_i of an element ii of EE is the ordered pair of its two copies, pi=(inli,inri),p_i = (\mathrm{inl}\, i, \mathrm{inr}\, i),(2)✦ and the list of paired slots PnP_n is the list of the slot pairs of 0,1,…,n−10, 1, \dots, n-1 in [n]⊔[n][n] \sqcup [n], in this order: Pn=(p0,p1,…,pn−1).P_n = (p_0, p_1, \dots, p_{n-1}).(3)✦ The transversal S(A)S(A) of a subset AA of EE is the subset of E⊔EE \sqcup E S(A)={inli:i∈A}∪{inri:i∈E\A}.S(A) = \{\mathrm{inl}\, i : i \in A\} \cup \{\mathrm{inr}\, i : i \in E \setminus A\}.(4)✦

Theorem 1. Let M1M_1 and M2M_2 be matroids whose ground sets lie in a set EE, the ground set of M2M_2 being all of EE, let KK be their paired matroid, and write ℬ(M)\mathcal{B}(M) for the set of bases of a matroid MM. For every subset AA of EE, S(A)∈ℬ(K)⇔A∈ℬ(M1)∩ℬ(M2).S(A) \in \mathcal{B}(K) \iff A \in \mathcal{B}(M_1) \cap \mathcal{B}(M_2).(5)✦ If moreover EE is finite and M1M_1 and M2M_2 have the same rank, then the rank of KK is r(K)=|E|.r(K) = |E|.(6)✦

In the paper, the result reads: on two copies VV of [n][n], in which xix_i and yiy_i are the copies of ii (the page’s inli\mathrm{inl}\, i and inri\mathrm{inr}\, i), the matroid K=M1⊕M2*K = M_1 \oplus M_2^* has rank nn, and S(A)={xi:i∈A}∪{yi:i∉A}S(A) = \{x_i : i \in A\} \cup \{y_i : i \notin A\} is a basis of KK if and only if AA is a basis of both M1M_1 and M2M_2.

What Is Checked

The definitions are stated over the direct sum and the dual of matroids, and the theorem over the paired matroid (1) and the transversal (4) of matroids M1M_1 and M2M_2 whose ground sets lie in EE, that of M2M_2 being all of EE, with EE finite and the two ranks equal for (6).