{"id":611,"date":"2014-02-24T09:00:19","date_gmt":"2014-02-24T14:00:19","guid":{"rendered":"http:\/\/matroidunion.org\/?p=611"},"modified":"2014-02-19T16:10:33","modified_gmt":"2014-02-19T21:10:33","slug":"rotas-basis-conjecture","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=611","title":{"rendered":"Rota’s Basis Conjecture"},"content":{"rendered":"

Guest post by Jan Draisma<\/a>, Eindhoven University of Technology.<\/em><\/p>\n

I’d like to discuss some old and new developments on Rota’s basis conjecture.<\/p>\n

Rota’s basis conjecture<\/B>.
\nLet $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<\/b> $v_{1,\\pi_1(j)},v_{2,\\pi_2(j)},\\ldots,v_{n,\\pi_n(j)}$ is a basis of $V$, as well.<\/i><\/p>\n

I first learned about this conjecture in 2005 from the beautiful chapter Ten abandoned goldmines<\/EM> [Cra01<\/A>] in a tribute to Gian-Carlo Rota. Ignorantly, I sat down on my balcony and thought, this must be easy…<\/EM> 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<\/em>, 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?<\/em><\/p>\n

Of course, I found out that the identity \\[ P=(\\mathrm{ELS}(n)-\\mathrm{OLS}(n)) \\mathrm{hdet} \\] had been discovered long before me [Onn97<\/A>]. 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<\/A>]. So I decided to read up on the history of these and related conjectures.<\/p>\n

What led Rota and his student Rosa Huang to the basis conjecture was their work in invariant theory [HR94<\/A>], and in his talk [Rot98<\/A>] 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<\/A>] (for primes plus one) and [Gly10<\/A>] (for primes minus one). See also [Ber12<\/A>] for an elementary proof of both results using Glynn’s determinantal identity. For odd dimensions, recent work by Aharoni and Kotlar [AK11<\/A>] relates an odd-$n$ version of Alon and Tarsi’s conjecture to a weaker version of the basis conjecture.<\/p>\n

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<\/A>] and for n=4 [Che12<\/A>] and for paving matroids [GH06<\/A>]. For general matroids, the following weakening is proved in [GW07<\/A>]: 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>]. <\/p>\n

A third direction, which I recently explored with Eindhoven Master’s student Guus Bollen [BD13<\/A>], 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<\/EM> exist for producing $\\pi_1,\\ldots,\\pi_n$ satisfying the requirement in the conjecture? We prove the following surprising dichotomy: for even<\/EM> $n$, the non-zeroness of $\\mathrm{ELS}(n)-\\mathrm{OLS}(n)$ in $K$ implies the existence of such an algorithm, while for odd<\/EM> $n$ any online algorithm can be forced to make an error.<\/p>\n

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. <\/p>\n

Problem<\/b>
\nDetermine 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.<\/i><\/p>\n

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<\/EM> [Ber08<\/a>,Bri13<\/A>]. 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<\/EM> in the ambient space $(\\mathbb{P}V)^{(n^2)}$ with $G$-action corresponds to a single<\/EM> 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<\/EM> 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<\/EM> a counterexample… but all of this is, for the time being, just science fiction<\/EM>!<\/p>\n

[AK11]<\/A> Ron Aharoni and Daniel Kotlar. A weak version of rota’s basis conjecture for odd dimensions. SIAM J. Discrete Math.<\/EM>, 2011. To appear, preprint here<\/a>.<\/p>\n

[AT92]<\/A> Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica<\/EM>, 12(2):125-134, 1992.<\/p>\n

[BD13]<\/A> Guus P. Bollen and Jan Draisma. An online version of Rota’s basis conjecture. 2013. Preprint, available here<\/a>.<\/p>\n

[Ber12]<\/A> Jochem Berndsen. Three problems in algebraic combinatorics. Master’s thesis, Eindhoven University of Technology, 2012. Available electronically at here<\/a>.<\/p>\n

[Bri13]<\/A> José Bertin. The punctual Hilbert scheme, lecture notes of the 2008 Grenoble Summer school in mathematics, available here<\/a>.<\/p>\n

[Bri13]<\/A> Michel Brion. Invariant Hilbert schemes, pages 63-118. Number 24 in Advanced Lectures in Mathematics. International Press, 2013.<\/p>\n

[Cha95]<\/A> Wendy Chan. An exchange property of matroid. Discrete Math.<\/EM>, 146:299-302, 1995.<\/p>\n

[Che12]<\/A> Michael Sze-Yu Cheung. Computational proof of Rota’s basis conjecture for matroids of rank 4. See this page<\/a>, 2012.<\/p>\n

[Cho10]<\/a> Chow, Timothy Y. Reduction of Rota’s basis conjecture to a problem on three bases. SIAM J. Discrete Math<\/em> 23(1): 369–371, 2009.<\/p>\n

[Cra01]<\/A> H. Crapo. Ten abandoned gold mines. In Algebraic combinatorics and computer science. A tribute to Gian-Carlo Rota<\/EM>, pages 3-22. Milano: Springer, 2001.<\/p>\n

[Dri97]<\/A> Arthur A. Drisko. On the number of even and odd Latin squares of order $p+1$. Adv. Math.<\/EM>, 128(1):20-35, 1997.<\/p>\n

[GH06]<\/A> Jim Geelen and Peter J. Humphries. Rota’s basis conjecture for paving matroids. SIAM J. Discrete Math.<\/EM>, 20(4):1042-1045, 2006.<\/p>\n

[Gly10]<\/A> David G. Glynn. The conjectures of alon-tarsi and rota in dimension prime minus one. SIAM J. Discrete Math.<\/EM>, 24(2):394-399, 2010.<\/p>\n

[GW07]<\/A> Jim Geelen and Kerri Webb. On Rota’s basis conjecture. SIAM J. Discrete Math.<\/EM>, 21(3):802-804, 2007.<\/p>\n

[HR94]<\/A> Rosa Huang and Gian-Carlo Rota. On the relations of various conjectures on latin squares and straightening coefficients. Discrete Math.<\/EM>, 128:225-236, 1994.<\/p>\n

[Onn97]<\/A> Shmuel Onn. A colorful determinantal identity, a conjecture of Rota, and Latin squares. Am. Math. Mon.<\/EM>, 104(2):156-159, 1997.<\/p>\n

[Rot98]<\/A> Gian-Carlo Rota. Ten mathematics problems I will never solve. Mitt. Dtsch. Math.-Ver.<\/EM>, 2:45-52, 1998.<\/p>\n","protected":false},"excerpt":{"rendered":"

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$ … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-611","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=611"}],"version-history":[{"count":2,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/611\/revisions"}],"predecessor-version":[{"id":613,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/611\/revisions\/613"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}