In recent years, combinatorial reconfiguration problems have attracted great attention due to their connection to various topics such as optimization, counting, enumeration, or sampling. One of the most intriguing open questions concerns the exchange distance of two matroid basis sequences, a problem that appears in several areas of computer science and mathematics. In 1980, White proposed a conjecture for the characterization of two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to toric ideals and Gr'obner bases. In this work, we verify White’s conjecture for basis sequences of length two in regular matroids, a problem that was formulated as a separate question by Farber, Richter, and Shank and Andres, Hochst'attler, and Merkel. Most of previous work on White’s conjecture has not considered the question from an algorithmic perspective. We study the problem from an optimization point of view: our proof implies a polynomial algorithm for determining a sequence of symmetric exchanges that transforms a basis pair into another, thus providing the first polynomial upper bound on the exchange distance of basis pairs in regular matroids. As a byproduct, we verify a conjecture of Gabow from 1976 on the serial symmetric exchange property of matroids for the regular case.

Two pairs of disjoint bases P1=(R1,B1) and P2=(R2,B2) of a matroid M are called equivalent if P1 can be transformed into P2 by a series of symmetric exchanges. In 1980, White conjectured that such a sequence always exists whenever R1∪B1=R2∪B2. A strengthening of the conjecture was proposed by Hamidoune, stating that the minimum length of an exchange is at most the rank of the matroid. We propose a weighted variant of Hamidoune’s conjecture, where the weight of an exchange depends on the weights of the exchanged elements. We prove the conjecture for several matroid classes: strongly base orderable matroids, split matroids, graphic matroids of wheels, and spikes.