The matroid secretary conjecture
In the matroid secretary problem of Babaioff, Immorlica and Kleinberg, the elements of a matroid with carry nonnegative values that are revealed in uniformly random order. An online algorithm must accept or reject each element irrevocably on arrival, keeping the accepted set independent, and is -competitive if its expected total value is at least times the maximum value of an independent set. Does every matroid admit an -competitive algorithm, with a universal constant independent of the matroid?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Matroid Theory, Combinatorial Optimization
- Posed by
- Babaioff, Immorlica and Kleinberg, Matroids, secretary problems, and online mechanisms (SODA 2007); journal version with Kempe, J. ACM 2018
- Year posed
- 2007
- Years open
- 19y
- Solved
- 2026-09-13
- Model
- ChatGPT Pro (several models, including ChatGPT Astra)
- Vendor
- OpenAI
- Collaborators
- Sahil Singla
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 45 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1 (arXiv 2609.14555): there is an online algorithm for the matroid secretary problem that accepts each element of the canonical optimum with probability at least , so it is -competitive (even -probability-competitive). It needs only in advance and independence-oracle access to the arrived elements, not the matroid. The strong form (-competitive) is claimed separately by Huang (arXiv 2609.30421) and in the merged paper arXiv 2611.08869.
What the AI did
From the paper's AI Usage section (present in v1 and v2): Algorithm 2, the algorithm behind the main theorem, "was found during an extended exploration with several models available through ChatGPT Pro", and "the key algorithmic idea emerged recently in this exploration after updating the model to ChatGPT Astra." ChatGPT Astra and Claude Opus 5 were also used for help with the presentation. The author states that he checked the mathematical arguments and takes full responsibility for the content.
Verification
No independent mathematician has checked this yet. Read by this site on 15 November 2026: the paper (arXiv 2609.14555, v1 of 13 September 2026 and v2 of 29 September, single author Sahil Singla) states the conjecture in the form above and proves it in Theorem 3.1 (informal Theorem 1.1), with each element of the canonical optimum accepted with probability at least 1/4. The AI Usage section is in both versions. The proof itself was not checked here and there is no formalisation. Later work builds on it: Chan, Lin and Wang (arXiv 2609.17782) improve the constant to about 3.1462, and the merged paper arXiv 2611.08869 (Abdi, Banihashem, Hajiaghayi, Huang, Mittal, Singla) restates the 4-competitive argument; neither is an independent public check of this proof.
Sources
- PaperarXivHuang, Settling the Matroid Secretary Problem (strong form, arXiv 2609.30421)Berczi, Dughmi, Livanos, Soto, Verdugo: strong conjecture for linear matroids (arXiv 2609.20797)Chan, Lin, Wang: 3.1462-competitive (arXiv 2609.17782)Merged paper: As Easy as Rank One (arXiv 2611.08869)
- Independent workConcurrent: Abdi, Banihashem, Hajiaghayi, Mittal, 64-competitive for all matroids (arXiv 2609.19118)
- OtherRelated entry: one-sample matroid prophet inequality
Submitted by MellowGander562 on