Given a matroid $M$ over a ground set $S$, the exchange axiom implies that for any pair of bases $R$ and $B$ there exists a sequence of exchanges that transforms $R$ into $B$, and the shortest length of such a sequence is $|R-B|.$ In the light of this, it is natural to ask whether analogous results hold for basis pairs instead of single bases. More precisely, let $(R,B)$ be an ordered pair of disjoint bases of $M$, and let $e\in R\setminus B$ and $f\in B\setminus R$ be such that both $R’:= R-e+f$ and $B’:= B+e-f$ are bases. In such a case, we call the exchange feasible and say that the pair $(R’,B’)$ is obtained from $(R,B)$ by a symmetric exchange. Using this terminology, we define the exchange distance (or distance for short) of two pairs of disjoint bases $\mathbf{P}_1=(R_1,B_1)$ and $\mathbf{P}_2=(R_2,B_2)$ to be the minimum number of symmetric exchanges needed to transform the former into the latter if such a sequence exists and $+\infty$ otherwise. We call two pairs of disjoint bases equivalent if their exchange distance is finite.
At this point it is not clear (I) when the distance of two pairs will be finite, and (II) if their distance is finite, whether we can give an upper bound on it. Regarding question (I), one can formulate an obvious necessary condition for the distance of $\mathbf{P}_1$ and $\mathbf{P}_2$ to be finite, namely $R_1\cup B_1=R_2\cup B_2$ should certainly hold — two pairs with this property are called compatible. In [11], White conjectured the following.
Conjecture 1. (White) Two basis pairs $\mathbf{P}_1$ and $\mathbf{P}_2$ are equivalent if and only if they are compatible.
By relying on the constructive characterization of bispanning graphs, Farber, Richter, and Shank [6] proved White’s conjecture for graphic and cographic matroids, while Farber [5] settled the statement for transversal matroids. Bonin [3] verified the conjecture for sparse paving matroids. The case of strongly base orderable matroids was solved by Lasoń and Michałek [9]. McGuinness [10] extended the graphic case to frame matroids satisfying a certain linearity condition.
Much less is known about question (II), that is, the optimization version of the problem. Gabow [7] studied sequential symmetric exchanges and posed the following problem.
Conjecture 2. (Gabow) For any two disjoint bases $R$ and $B$ of a matroid $M$, there is a sequence of $r$ symmetric exchanges that transforms the pair $\mathbf{P}_1=(R,B)$ into $\mathbf{P}_2=(B,R)$.
The rank of the matroid is a trivial lower bound on the minimum number of exchanges needed to transform a pair $(R,B)$ into $(B,R)$, and the essence of Gabow’s conjecture is that that many steps might always suffice. The relation between the conjectures of White and Gabow is immediate: the latter would imply the former for sequences of the form $(R,B)$ and $(B,R)$. Gabow’s conjecture was verified for partition matroids, matching and transversal matroids, and matroids of rank less than $4$ in [7], and an easy reasoning shows that it holds for strongly base orderable matroids as well. The graphic case was settled by Wiedemann [12], Kajitani, Ueno, and Miyano [8], and Cordovil and Moreira [4].
In general, if $M$ has rank $r$, then $r-|R_1\cap R_2|$ is an obvious lower bound on the exchange distance of $\mathbf{P}_1=(R_1,B_1)$ and $\mathbf{P}_2 = (R_2,B_2)$. However, it might happen that more symmetric exchanges are needed even if $M$ is a graphic matroid. As a common generalization of the conjectures of White and Gabow, Hamidoune [4] proposed a rather optimistic conjecture.
Conjecture 3. (Hamidoune) The exchange distance of compatible basis pairs is at most the rank of the matroid.
Bérczi and Schwarcz [2] showed that the conjecture holds for split matroids.
Let $w: S\to\mathbb{R}_+$ be a weight function on the elements of the ground set $S$. Given a pair $(R,B)$ of disjoint bases, we define the weight of a symmetric exchange $R’:= R-e+f$ and $B’:= B+e-f$ to be $w(e)+w(f)$, that is, the sum of the weights of the exchanged elements. Analogously to the unweighted setting, we define the weighted exchange distance (or weighted distance for short) of two pairs of disjoint bases $\mathbf{P}_1=(R_1,B_1)$ and $\mathbf{P}_2=(R_2,B_2)$ to be the minimum total weight of symmetric exchanges needed to transform the former into the latter if such a sequence exists and $+\infty$ otherwise. As a weighted extension of Hamidoune’s conjecture, we propose the following.
Conjecture 4. Let $\mathbf{P}_1=(R_1,B_1)$ and $\mathbf{P}_2=(R_2,B_2)$ be compatible basis pairs of a matroid $M$ over a ground set $S$, and let $w: S\to\mathbb{R}_+$ be a weight function. Then the weighted exchange distance of $\mathbf{P}_1$ and $\mathbf{P}_2$ is at most $w(R_1\cup B_1)=w(R_2\cup B_2)$.
By setting the weight function to be identically one, we get back Hamidoune’s conjecture. In [1], the conjecture was verified for strongly base orderable matroids, split matroids, graphic matroids of wheel graphs, and spikes.
References
[1] K. Bérczi, B. Mátravölgyi, T. Schwarcz. Weighted exchange distance of basis pairs. arXiv preprint arXiv:2211.12750, 2022.
[2] K. Bérczi and T. Schwarcz. Exchange distance of basis pairs in split matroids. arXiv preprint arXiv:2203.01779, 2022.
[3] J. E. Bonin. Basis-exchange properties of sparse paving matroids. Advances in Applied Mathematics, 50(1):6–15, 2013.
[4] R. Cordovil and M. L. Moreira. Bases-cobases graphs and polytopes of matroids. Combinatorica, 13(2):157–165, 1993.
[5] M. Farber. Basis pair graphs of transversal matroids are connected. Discrete Mathematics, 73(3):245–248, 1989.
[6] M. Farber, B. Richter, and H. Shank. Edge-disjoint spanning trees: A connectedness theorem. Journal of Graph Theory, 9(3):319–324, 1985.
[7] H. Gabow. Decomposing symmetric exchanges in matroid bases. Mathematical Programming, 10(1):271–276, 1976.
[8] Y. Kajitani, S. Ueno, and H. Miyano. Ordering of the elements of a matroid such that its consecutive w elements are independent. Discrete Mathematics, 72(1-3):187–194, 1988.
[9] M. Lasoń and M. Michałek. On the toric ideal of a matroid. Advances in Mathematics, 259:1–12, 2014.
[10] S. McGuinness. Frame matroids, toric ideals, and a conjecture of White. Advances in Applied Mathematics, 118:102042, 2020.
[11] N. L. White. A unique exchange property for bases. Linear Algebra and its Applications, 31:81–91, 1980.
[12] D. Wiedemann. Cyclic base orders of matroids. Manuscript, 1984.