Weighted proximity conjecture for group-labeled matroid bases
Let be a matroid on ground set , let be an abelian group, let be a labeling, let be finite, and let be arbitrary costs. For a base write . If there exists an -avoiding base , meaning , then for every minimum-cost base of there exists a minimum-cost -avoiding base such that ; equivalently, can be obtained from using at most basis exchanges.
References
- Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases — arXiv — Siyue Liu, Taihei Oki, Chao Xu
Source: arXiv
Progress summary
An unrefereed paper claims to settle the conjecture for arbitrary costs, but the result has not been independently verified.
The conjecture asks whether, whenever a basis avoiding a finite forbidden label set exists, any basis can be changed into such a basis using at most exchanges. Its weighted version asks for the same proximity bound while minimizing arbitrary costs.
Known results
- Weighted form known for strongly base-orderable matroids and (2024).
- Unweighted form proved for and ordered groups (2024).
- Unweighted form proved for sparse paving matroids and (2025).
October 23, 2026 claimed resolution
On October 23, 2026, Siyue Liu, Taihei Oki, and Chao Xu reported a theorem for arbitrary costs: an -avoiding minimum-cost basis is within exchanges of any minimum-cost basis. The paper replaces the earlier Schrijver–Seymour assumption with the Kemperman–Scherk theorem and derives fixed-parameter algorithms in and . This remains an unverified preprint claim.
Current status (as of October 2026): the arbitrary-cost weighted conjecture is claimed solved by an unrefereed preprint, but the claim is not independently verified in the retrieved sources.
Solutions 0
No solutions have been posted yet.