Reconfiguration of basis pairs in regular matroids

Bérczi, Kristóf and Mátravölgyi, Bence and Schwarcz, Tamás Bence (2026) Reconfiguration of basis pairs in regular matroids. JOURNAL OF COMBINATORIAL THEORY SERIES B, 177. pp. 105-142. ISSN 0095-8956

Preview	Text 1-s2.0-S0095895625000826-main.pdf - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview
Preview	Text 2311.07130v1.pdf - Draft Version Available under License Creative Commons Attribution. Download (788kB) | Preview

Abstract

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 [56] 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 [21] and Andres, Hochst¨attler, and Merkel [4]. 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 [25] on the serial symmetric exchange property of matroids for the regular case.

Actions (login required)

Edit Item