Weighted exchange-distance conjecture for matroid basis pairs

Let MM be a matroid over a ground set SS, let P1=(R1,B1)\mathbf{P}_1=(R_1,B_1) and P2=(R2,B2)\mathbf{P}_2=(R_2,B_2) be compatible pairs of disjoint bases, and let w ⁣:SR+w\colon S\to\mathbb{R}_+ be a weight function. The weighted exchange distance is the minimum total weight of symmetric exchanges transforming one pair into the other, or ++\infty if no such sequence exists. For a set ASA\subseteq S, write w(A)w(A) for the sum of the weights of its elements.

Weighted exchange-distance conjecture. The weighted exchange distance of P1\mathbf{P}_1 and P2\mathbf{P}_2 is at most

w(R1B1)=w(R2B2).w(R_1\cup B_1)=w(R_2\cup B_2).

The paper proposes this as a weighted extension of Hamidoune's conjecture and proves it for several classes of matroids, including strongly base orderable, split, and certain graphic matroids, while the general case remains open.

Sources & referencesView supporting material

Primary source

Kristóf Bérczi, Bence Mátravölgyi and Tamás Schwarcz, “Weighted exchange distance of basis pairs”, arXiv:2211.12750 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.