OctoInformBeta

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

Dual rank (2.1): For a matroid MM of rank nn on EE and |S|=n|S| = n, rM*(S)=rM(E\S)r_{M^*}(S) = r_M(E \setminus S), and likewise for the rank weights qn−r(S)q^{n-r(S)}

On sets of rank size, dual rank is complement rank.

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 MM be a matroid on a ground set EE, with rank function rMr_M, and let M*M^* be its dual, the matroid on EE whose bases are the complements of the bases of MM, with rank function rM*r_{M^*}.

Fix a natural number nn. A paired ground set is a set V={x1,…,xn,y1,…,yn}V = \{x_1, \dots, x_n, y_1, \dots, y_n\} of two copies of [n]={1,…,n}[n] = \{1, \dots, n\} matched in the pairs {xi,yi}\{x_i, y_i\}, and the matroids considered on it have rank nn. For a subset SS of VV with |S|=n|S| = n the complement V\SV \setminus S also has nn elements, and the question is how the rank of SS in the dual is read off from ranks in the matroid itself.

Rank Weights

Fix a real number qq. For a matroid NN on EE, the rank weight of a set S⊆ES \subseteq E is the real number wN(S)=qmax⁡{n−rN(S),0}.w_N(S) = q^{\max\{n - r_N(S),\, 0\}}.(1)✦

The Claim

Theorem 1. Let MM be a matroid of rank nn on a ground set EE, let SS be a subset of EE with nn elements, and let qq be a real number. Then rM*(S)=rM(E\S),r_{M^*}(S) = r_M(E \setminus S),(2)✦ and the rank weights (1) built from this nn and qq satisfy wM*(S)=wM(E\S).w_{M^*}(S) = w_M(E \setminus S).(3)✦

In the paper, the result reads: rM*(A)=|A|−rM(E)+rM(E\A)r_{M^*}(A) = |A| - r_M(E) + r_M(E \setminus A) for every A⊆EA \subseteq E, and, for a matroid MM of rank nn on a ground set VV of 2n2n elements and a set SS with |S|=n|S| = n, rM*(S)=rM(V\S)r_{M^*}(S) = r_M(V \setminus S).

What Is Checked

The claim is stated over a matroid MM of rank nn on a ground set EE, its dual M*M^* and the rank functions of the two, a set SS of nn elements of EE and its complement, and the rank weight (1) for this nn and a real number qq.