Weighted exchange-distance conjecture for matroid basis pairs

At least 3 years old · documented by

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 ⁣:S→R+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 A⊆SA\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(R1∪B1)=w(R2∪B2).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.

References

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.