Serial Exchanges in Random Bases

Abstract

It was conjectured by Kotlar and Ziv that for any two bases $B_1$ and $B_2$ in a matroid $M$ and any subset $X\subset B_1$, there is a subset $Y$ and orderings $x_1\prec x_2\prec \cdots \prec x_k$ and $y_1\prec y_2\prec \cdots \prec y_k$ of $X$ and $Y$, respectively, such that for $i=1,\dots ,k$, $B_1-\{x_1,\dots ,x_i\}+\{y_1,\dots ,y_k\}$ and $B_2-\{y_1,\dots ,y_i\}+\{x_1,\dots ,x_k\}$ are bases; that is, $X$ is serially exchangeable with $Y$. Let $M$ be a rank-$n$ matroid which is representable over ${\mathbb{F}}_q.$ We show that for $q>2,$ if bases $B_1$ and $B_2$ are chosen randomly amongst all bases of $M$, and if a subset $X$ of size $k\le \ln (n)$ is chosen randomly in $B_1$, then with probability tending to one as $n\to \infty$, there exists a subset $Y\subset B_2$ such that $X$ is serially exchangeable with $Y.$