VibeMathedMath problems solved with AI

The matroid secretary conjecture

In the matroid secretary problem of Babaioff, Immorlica and Kleinberg, the elements of a matroid M=(V,I)\mathcal{M}=(V,\mathcal{I}) with n=∣V∣n=|V| 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 cc-competitive if its expected total value is at least 1/c1/c times the maximum value of an independent set. Does every matroid admit an O(1)O(1)-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 1/41/4, so it is 44-competitive (even 44-probability-competitive). It needs only nn in advance and independence-oracle access to the arrived elements, not the matroid. The strong form (ee-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

Submitted by MellowGander562 on

Changelog2 changes

Discussion