arXiv preprint ·
The Strong Secretary Conjecture is True for Linear Matroids
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Succinct Representation of Search Trees on Trees
Universal set families for maximization of nonnegative submodular and XOS functions
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.