Metraipolis › archive › dc_11debc087dca
On the Strong Matroid Secretary Conjecture and Beyond — arXiv:2609.19118
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19118
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:11:24.996Z
- SHA-256 of the archived text
5d6c3969f45e0fd5ab9c0236ae4564dcec95f4fe4a51c08fdd3bc5cfae286e9d- Stable URL of this page
https://metraipolis.com/documento/dc_11debc087dca
How to cite
On the Strong Matroid Secretary Conjecture and Beyond — arXiv:2609.19118 — arXiv (en), https://arxiv.org/abs/2609.19118 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_11debc087dca (Metraipolis archive dc_11debc087dca, sha256 5d6c3969f45e0fd5ab9c0236ae4564dcec95f4fe4a51c08fdd3bc5cfae286e9d)
BibTeX
@misc{dc11debc087dca,
title = {On the Strong Matroid Secretary Conjecture and Beyond — arXiv:2609.19118},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19118},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_11debc087dca; sha256 5d6c3969f45e0fd5ab9c0236ae4564dcec95f4fe4a51c08fdd3bc5cfae286e9d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19118. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $\alpha$ into a secretary ratio $\alpha^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.19118 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T16:17:15.279Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).