News

Generalizing the Multiple Exchange Property

The multiple exchange property for matroid bases states that for any bases $A$ and $B$ of a matroid and any subset $X\subseteq A\setminus B$, there exists a subset $Y\subseteq B\setminus A$ such that both $A-X+Y$ and $B+X-Y$ are bases. This classical result has not only found applications in matroid theory, but also in the analysis and design of various algorithms. In the paper Generalizing the Multiple Exchange Property for Matroid Bases, we prove a common generalization of this and other known basis exchange properties by showing that for any subsets $X \subseteq A \setminus B$ and $Y \subseteq B \setminus A$, there exist subsets $U \subseteq A \setminus B$ and $V \subseteq B \setminus A$ such that $X\subseteq U$, $Y\subseteq V$, $A-U+V$ and $B+U-V$ are bases, and $|U|=|V|$ is at most the rank of $X+Y$. As an application, we prove the robustness of the local search algorithm for finding maximum weight matroid bases. For matroids representable over a field of characteristic zero, we further generalize our exchange property to include the very recent Equitability Theorem (SODA 2026), by establishing a far-reaching generalization of the Grassmann–Plücker identity.