← All problems

Weighted proximity conjecture for group-labeled matroid bases

Let MM be a matroid on ground set EE, let GG be an abelian group, let ℓ:E→G\ell:E\to G be a labeling, let F⊆GF\subseteq G be finite, and let c:E→Rc:E\to\mathbb{R} be arbitrary costs. For a base BB write ℓ(B)=∑e∈Bℓ(e)\ell(B)=\sum_{e\in B}\ell(e). If there exists an FF-avoiding base B′B', meaning ℓ(B′)∉F\ell(B')\notin F, then for every minimum-cost base BB of MM there exists a minimum-cost FF-avoiding base B~\widetilde{B} such that ∣B∖B~∣≤∣F∣|B\setminus\widetilde{B}|\le |F|; equivalently, B~\widetilde{B} can be obtained from BB using at most ∣F∣|F| basis exchanges.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 ∣F∣\lvert F\rvert 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 ∣F∣=1\lvert F\rvert=1 (2024).
  • Unweighted form proved for ∣F∣≤2\lvert F\rvert\le 2 and ordered groups (2024).
  • Unweighted form proved for sparse paving matroids and ∣F∣≤4\lvert F\rvert\le 4 (2025).

October 23, 2026 claimed resolution

On October 23, 2026, Siyue Liu, Taihei Oki, and Chao Xu reported a theorem for arbitrary costs: an FF-avoiding minimum-cost basis is within ∣F∣\lvert F\rvert 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 ∣G∣\lvert G\rvert and ∣F∣\lvert F\rvert. 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.

Sources

Solutions 0

No solutions have been posted yet.