Lemma 9 — one subset rule for an entire chain
OpenLinMatroidSecretary.Online.Supplement.lemma_9matroidsonline-allocationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problemxos-valuations
Let be a finite field, , , and let be a subspace probability distribution satisfying
Let be an independent bundle of a finite labelled vector family , and put . For every finite strictly increasing chain , there exists one randomized rule, depending on the chain and the observed , selecting . Its conditional distributions are nonnegative, have mass one, and are supported on bundles with
For this same rule all the following inequalities hold simultaneously:
All expectations include both random choices. This is the chain-compatible form of bundle selection used in the feasibility argument for Lemma 7.
Differences from the source:
- encoding: an independent set of vectors in a finite-dimensional space over a finite field → a finite labelled family v : E → F^d, independent on the specified finite bundle, and a finitely supported law on subspaces; reason: independence makes the bundle labels injective on vectors; every finite-dimensional space has coordinates, and over a finite field every subspace law has finite support
- encoding: a chain L1 < ··· < Ls → a strictly increasing map L : Fin s → Submodule F (Fin d → F); reason: zero-based indexing only relabels the same finite chain; the empty chain leaves the complete selection assertion
Preamble
import Mathlib import Definitions.Def_LinMatroidSecretary_Online_Supplement_BundleLP
Formal statement
namespace LinMatroidSecretary.Online.Supplement
/-- Lemma 9, STOC 2027 #608, PDF p. 27 (printed p. 25). One rule simultaneously
satisfies the bound at every member of the chain, including the empty-chain case. -/
theorem lemma_9 {F : Type} [Field F] [Fintype F] {d : ℕ}
(α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (ν : Dist F d)
(hν : IsDistOn ν ⊤) (hDim : DimIneqAlpha ν α)
{E : Type} [Fintype E] [DecidableEq E] (v : E → Fin d → F)
(B : Finset E) (hB : LinearIndepOn F v (B : Set E))
(s : ℕ) (L : Fin s → Submodule F (Fin d → F)) (hL : StrictMono L) :
∃ ρ : SelectionRule F d E, SelectionValid v ν B ρ ∧
(∀ b ∈ B, selectionMarginal ν B ρ b = α) ∧
∀ j, selectionExpect ν B ρ (fun W T => dimInter (W ⊔ bundleSpan v T) (L j)) ≤
(1 - α) * (Module.finrank F (L j) : ℝ) + α * dimInter (bundleSpan v B) (L j) := by sorry
end LinMatroidSecretary.Online.Supplement
Source
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, Jose Soto, Victor Verdugo, The Strong Secretary Conjecture is True for Linear Matroids, STOC 2027 submission #608 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/608.pdf, Lemma 9, PDF p. 27 (printed p. 25)