Rota's basis conjecture holds for random bases of vector spaces

Abstract

In 1989, Rota conjectured that, given $n$ bases $B_1,\dots ,B_n$ of the vector space ${\mathbb{F}}^n$ over some field $\mathbb{F}$, one can always decompose the multi-set $B_1\cup \cdots \cup B_n$ into transversal bases. This conjecture remains wide open despite of a lot of attention. In this paper, we consider the setting of random bases $B_1,\dots ,B_n$. More specifically, our first result shows that Rota's basis conjecture holds with probability $1-o(1)$ as $n\to \infty$ if the bases $B_1,\dots ,B_n$ are chosen independently uniformly at random among all bases of ${\mathbb{F}}_q^n$ for some finite field ${\mathbb{F}}_q$ (the analogous result is trivially true for an infinite field $\mathbb{F}$). In other words, the conjecture is true for almost all choices of bases $B_1,\dots ,B_n\subseteq {\mathbb{F}}_q^n$. Our second, more general, result concerns random bases $B_1,\dots ,B_n\subseteq S^n$ for some given finite subset $S\subseteq \mathbb{F}$ (in other words, bases $B_1,\dots ,B_n$ where all vectors have entries in $S$). We show that when choosing bases $B_1,\dots ,B_n\subseteq S^n$ independently uniformly at random among all bases that are subsets of $S^n$, then again Rota's basis conjecture holds with probability $1-o(1)$ as $n\to \infty$.

17 pages