Lemma 6 — independent bundle selection with exact marginals
OpenLinMatroidSecretary.Online.Supplement.lemma_6matroidsonline-allocationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problemxos-valuations
Let be a finite field, , , and let be a probability distribution on subspaces of . Suppose that
Let be an independent bundle in a finite labelled vector family . There exists a randomized rule that, after observing , chooses , with a nonnegative conditional distribution of total mass one for each positive-mass , such that
The probability averages over both and the conditional subset choice. Empty bundles and the endpoints are included. This is the subset-selection result needed for bundle arrivals.
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
Preamble
import Mathlib import Definitions.Def_LinMatroidSecretary_Online_Supplement_BundleLP
Formal statement
namespace LinMatroidSecretary.Online.Supplement
/-- Lemma 6, STOC 2027 #608, PDF p. 22 (printed p. 20). All clauses of the
conditional subset selection rule are asserted, with exact marginal α. -/
theorem lemma_6 {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)
(C : Finset E) (hC : LinearIndepOn F v (C : Set E)) :
∃ ρ : SelectionRule F d E, SelectionValid v ν C ρ ∧
∀ c ∈ C, selectionMarginal ν C ρ c = α := 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 6, PDF p. 22 (printed p. 20)