Guest post by Jan Draisma, Eindhoven University of Technology.
I’d like to discuss some old and new developments on Rota’s basis conjecture.
Rota’s basis conjecture.
Let $V$ be an $n$-dimensional vector space over a field $K$, and for each $i=1,\ldots,n$ let $v_{i1},\ldots,v_{in}$ be a basis of $V$. Then there exist permutations $\pi_1,\ldots,\pi_n \in S_n$ such that for each $j\in [n]$ the transversal $v_{1,\pi_1(j)},v_{2,\pi_2(j)},\ldots,v_{n,\pi_n(j)}$ is a basis of $V$, as well.
I first learned about this conjecture in 2005 from the beautiful chapter Ten abandoned goldmines [Cra01] in a tribute to Gian-Carlo Rota. Ignorantly, I sat down on my balcony and thought, this must be easy… let’s identify $V$ with $K^n$ and introduce a variable $x_{ijk}$ for the $k$-th coordinate of $v_{ij}$. These are arranged in a cube whose horizontal slices are matrices with non-zero determinants. Let $\mathrm{hdet}$ denote the product of these horizontal determinants. For each choice $\pi (\pi_1,\ldots,\pi_n)$ let $\mathrm{vdet}_\pi$ be the product of the vertical determinants $\det(x_{i,\pi_i(j),k})_{i,k}$ for $j=1,\ldots,n$. Both $\mathrm{hdet}$ and $\mathrm{vdet}_\pi$ are degree-$n^2$ polynomials in the $x_{ijk}$, and the conjecture is equivalent (if $K$ is algebraically closed) to the statement that some power of $\mathrm{hdet}$ lies in the ideal generated by $\{\mathrm{vdet}_\pi \mid \pi \in S_n^n\}$. But they have the same degree, so perhaps $\mathrm{hdet}$ itself is already a linear combination of the $\mathrm{vdet}_\pi$? There is a natural guess for the coefficients: the polynomial \[ P=\sum_{\pi \in S_n^n} \mathrm{sign}(\pi_1) \cdots \mathrm{sign}(\pi_n) \mathrm{vdet}_\pi \] is multilinear in the $n^2$ vectors $v_{ij}$ and changes sign when you swap two vectors in the same row. There is only a one-dimensional space of such polynomials, and it is spanned by $\mathrm{hdet}$. So $P=c \cdot \mathrm{hdet}$ for some constant $c \in K$ and we’re done…oh, but wait a minute, let’s evaluate $c$. Each multilinear monomial in the $n^2$ vectors $v_{ij}$ is a product over all $(i,j)$ of a coordinate $x_{ijk}$ of $v_{ij}$ and can therefore be represented by an $n \times n$-matrix with entries $k \in [n]$. So for instance the monomial $m:=\prod_{i=1}^n (x_{i11} x_{i22} x_{i33} \cdots x_{inn})$ corresponds to the matrix with all rows equal to $1,2,\ldots,n$. The monomial $m$ appears in $\mathrm{vdet}_\pi$ if and only if, for each $j \in [n]$, the numbers $\pi_1(j),\ldots,\pi_n(j)$ are all distinct, i.e., if the array $(\pi_i(j))_{ij}$ is a Latin square (LS). The coefficient of $m$ in $P$ is then \[ \mathrm{sign}(\pi_1) \cdots \mathrm{sign} (\pi_n) \cdot \mathrm{sign}(\sigma_1) \cdots \mathrm{sign}(\sigma_n), \] where $\sigma_j:i \mapsto \pi_i(j)$ are the permutations given by the columns of the LS. Call an LS even if the coefficient above is $1$ and odd if it is $-1$. Then we have \[ c=\mathrm{ELS}(n)-\mathrm{OLS}(n) \] where $\mathrm{ELS}(n)$ is the number of even LS of order $n$ and $\mathrm{OLS}$ is the number of odd LS. Now if the characteristic of $K$ does not divide $c$, then we are done. Hmm, but why should $c$ even be non-zero?
Of course, I found out that the identity \[ P=(\mathrm{ELS}(n)-\mathrm{OLS}(n)) \mathrm{hdet} \] had been discovered long before me [Onn97]. For odd $n$ it is useless, since swapping the last two rows gives a sign-reversing involution on the set of LS, so that $c=0$. For even $n$, the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ was a already famous conjecture due to Alon and Tarsi [AT92]. So I decided to read up on the history of these and related conjectures.
What led Rota and his student Rosa Huang to the basis conjecture was their work in invariant theory [HR94], and in his talk [Rot98] Rota expressed the opinion that new insights in invariant theory would be required to settle the conjecture. Infinitely many cases of the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ were settled in [Dri97] (for primes plus one) and [Gly10] (for primes minus one). See also [Ber12] for an elementary proof of both results using Glynn’s determinantal identity. For odd dimensions, recent work by Aharoni and Kotlar [AK11] relates an odd-$n$ version of Alon and Tarsi’s conjecture to a weaker version of the basis conjecture.
Another line of research concerns the natural generalisation of the basis conjecture to arbitrary matroids. This turns out to be true for $ n=3$ [Cha95] and for n=4 [Che12] and for paving matroids [GH06]. For general matroids, the following weakening is proved in [GW07]: a $k \times n$-array of elements in a matroid whose rows are bases has $n$ disjoint independent transversals if $n > \binom{k+1}{2}$. A reduction from Rota’s conjecture to a conjecture concerning only three bases was established in [Cho10].
A third direction, which I recently explored with Eindhoven Master’s student Guus Bollen [BD13], concerns the following strengthening of the basis conjecture. Suppose that the rows of the array $(v_{ij})_{ij}$ are given to you sequentially, and that you have to fix $\pi_i$ immediately after receiving the $i$-th row, without knowledge of the remaining rows. Does such an online algorithm exist for producing $\pi_1,\ldots,\pi_n$ satisfying the requirement in the conjecture? We prove the following surprising dichotomy: for even $n$, the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ in $K$ implies the existence of such an algorithm, while for odd $n$ any online algorithm can be forced to make an error.
This leads to the following question: does the online version make sense for general matroids? Well, yes, but it is easy to come up with counterexamples of format $n \times n$ for $n \geq 3$, even among linear matroids: for the online algorithm above it is essential that the algorithm gets the vectors as input, not just their linear dependencies. But what about $k \times n$-arrays for smaller $k$? It is quite conceivable that the following problem has an easy solution.
Problem
Determine the maximal value of $k$, as a function of $n$, such that the online version of the basis conjecture has a positive answer for $k \times n$-arrays in general matroids.
To conclude, here is a rather wild speculation related to Rota’s remark that new techniques in invariant theory are needed. Among the most powerful new tools in invariant theory are invariant Hilbert schemes [Ber08,Bri13]. They might play a role as follows. Suppose that $v=(v_{ij})_{ij}$ is a counterexample to the basis conjecture. Think of the $v_{ij}$ as points in projective space $\mathbb{P}V$, and assume that no two rows represent the same set of $n$ projective points. Then the orbit of $v$ under the semi-direct product $G$ of $S_n^n$ (for permutations within rows) with $S_n$ (for permutations of the rows) is a set of $(n!)^{n+1}$ points in $(\mathbb{P}V)^{(n^2)}$. This finite $G$-stable set of points in the ambient space $(\mathbb{P}V)^{(n^2)}$ with $G$-action corresponds to a single point in a suitable $G$-invariant Hilbert scheme. Applying invertible linear transformations of $V$ yields further points in the Hilbert scheme. The power of Hilbert schemes is that they also parameterise non-reduced sets, which arise, for instance, by allowing some or all of the points in the set to collide (think of a double root of a polynomial, which encodes not just a root but also a tangency). So one would like to phrase the property of being a counterexample as a closed condition on all points of the invariant Hilbert scheme, use a one-parameter group of basis transformations to degenerate the alleged counterexample to a point in the Hilbert scheme corresponding to a non-reduced counterexample (where all $(n!)^{n+1}$ points collide but the scheme encodes an interesting higher-order tangency structure), and then use $G$-module structure of the coordinate ring of the limit to show that it is, in fact, not a counterexample… but all of this is, for the time being, just science fiction!
[AK11] Ron Aharoni and Daniel Kotlar. A weak version of rota’s basis conjecture for odd dimensions. SIAM J. Discrete Math., 2011. To appear, preprint here.
[AT92] Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125-134, 1992.
[BD13] Guus P. Bollen and Jan Draisma. An online version of Rota’s basis conjecture. 2013. Preprint, available here.
[Ber12] Jochem Berndsen. Three problems in algebraic combinatorics. Master’s thesis, Eindhoven University of Technology, 2012. Available electronically at here.
[Bri13] José Bertin. The punctual Hilbert scheme, lecture notes of the 2008 Grenoble Summer school in mathematics, available here.
[Bri13] Michel Brion. Invariant Hilbert schemes, pages 63-118. Number 24 in Advanced Lectures in Mathematics. International Press, 2013.
[Cha95] Wendy Chan. An exchange property of matroid. Discrete Math., 146:299-302, 1995.
[Che12] Michael Sze-Yu Cheung. Computational proof of Rota’s basis conjecture for matroids of rank 4. See this page, 2012.
[Cho10] Chow, Timothy Y. Reduction of Rota’s basis conjecture to a problem on three bases. SIAM J. Discrete Math 23(1): 369–371, 2009.
[Cra01] H. Crapo. Ten abandoned gold mines. In Algebraic combinatorics and computer science. A tribute to Gian-Carlo Rota, pages 3-22. Milano: Springer, 2001.
[Dri97] Arthur A. Drisko. On the number of even and odd Latin squares of order $p+1$. Adv. Math., 128(1):20-35, 1997.
[GH06] Jim Geelen and Peter J. Humphries. Rota’s basis conjecture for paving matroids. SIAM J. Discrete Math., 20(4):1042-1045, 2006.
[Gly10] David G. Glynn. The conjectures of alon-tarsi and rota in dimension prime minus one. SIAM J. Discrete Math., 24(2):394-399, 2010.
[GW07] Jim Geelen and Kerri Webb. On Rota’s basis conjecture. SIAM J. Discrete Math., 21(3):802-804, 2007.
[HR94] Rosa Huang and Gian-Carlo Rota. On the relations of various conjectures on latin squares and straightening coefficients. Discrete Math., 128:225-236, 1994.
[Onn97] Shmuel Onn. A colorful determinantal identity, a conjecture of Rota, and Latin squares. Am. Math. Mon., 104(2):156-159, 1997.
[Rot98] Gian-Carlo Rota. Ten mathematics problems I will never solve. Mitt. Dtsch. Math.-Ver., 2:45-52, 1998.
