Matroid secretary problem solved for linear matroids with 1 over e guarantee
The Strong Secretary Conjecture is True for Linear Matroids
Data Structures and Algorithms
Summary
The matroid secretary problem is about choosing the best combination of items when they arrive one by one in random order, without knowing the future. This paper proves that for linear matroids—a kind of mathematical structure used to model independence—the authors can select each optimal item with at least a 1/e (around 37%) chance. This confirms a long-standing conjecture for this class of problems. Their approach works both when the matroid is fully known in advance and when it is revealed step-by-step over a finite field.
What this means in practice
- •For online algorithm developers: Design online selection algorithms with provable probability guarantees for problems modeled by linear matroids.
- •For network designers: Improve resource allocation strategies in networks that can be modeled using linear matroids to ensure reliable item selection under uncertainty.
A theory result. No direct application yet.
Authors
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo
Abstract
We prove a $1/e$ guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension. Each element of a fixed optimal basis is selected with probability at least $1/e$. $\mathbf{\text{Concurrent Discovery Disclosure:}}$ The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT. We then prepared this manuscript for public release, with the intent of uploading it on the morning of Thursday, September 17, 2026. In the early morning hours of September 17, while finalizing the submission, we discovered the manuscript https://arxiv.org/abs/2609.19118 of Abdi, Banihashem, Hajiaghayi, and Mittal, uploaded on September 16, 2026, which contains the same result via an essentially identical approach. We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era.