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.

Guest post by Jim Geelen.
$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\bF}{\mathbb{F}}$ $\newcommand{\cL}{\mathcal{L}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\DeclareMathOperator{\ex}{ex}$ $\DeclareMathOperator{\rank}{rank}$ $\DeclareMathOperator{\PG}{PG}$ $\DeclareMathOperator{\AG}{AG}$ $\DeclareMathOperator{\BB}{BB}$

In my last two posts I discussed the Turán problems for the binary projective geometry and for the binary affine geometry. This time I will consider the Turán problem for an arbitrary binary geometry. An extraordinary connection between Turán densities and critical exponents emerges.

Graphs

Recall that a graph is called $H$-free if it has no subgraph isomorphic to $H$. The Turán problem for a given graph $H$ is to determine, for each integer $n$, the maximum number, $\ex(H,n)$, of edges among all $n$-vertex $H$-free graphs.

The following result, due to Erdös and Stone [ES46], is among my favourite theorems in extremal graph theory. It reveals an unexpected connection between the chromatic number of a graph and the asymptotic behaviour of its Turán numbers.

Erdös-Stone Theorem: Let $H$ be a graph with chromatic number $\chi\ge 2$. Then $$ \lim_{n\rightarrow\infty} \frac{\ex(H,n)}{|E(K_n)|} = \frac{\chi-2}{\chi-1}.$$

Note that the Turán graphs $T(n,\chi)$ are $H$-free and have densities approaching $\frac{\chi-2}{\chi-1}.$

The Erdös-Stone Theorem shows that $\ex(H,n) = \frac{\chi-2}{\chi-1}{n\choose 2} + o(n^2)$, which gives the asymptotic behaviour of $\ex(H,n)$ except when $\chi=2$. Determining the asymptotic behaviour of the Turán numbers of bipartite graphs is a difficult open problem, which I discussed last time.

Binary Geometries

Recall that a binary geometry is called $N$-free if it has no restriction isomorphic to $N$. The Turán problem for a given binary geometry $N$ is to determine, for each integer $r$, the maximum number, $\ex(N,r)$, of points among all rank-$r$ $N$-free binary geometries. The Bose-Burton geometry $\BB(r,c)$ is the binary geometry obtained from $\PG(r-1,2)$ by deleting all of the points in a flat of rank $r-c$.

The following result relates the critical exponent of a binary geometry and the asymptotic behaviour of its Turán numbers; see [GN].

Geometric Erdös-Stone Theorem: Let $N$ be a binary geometry with critical exponent $c\ge 1$. Then $$ \lim_{r\rightarrow\infty} \frac{\ex(N,r)}{|\PG(r-1,2)|} = 1-2^{-(c-1)}.$$

Note that the Bose-Burton geometries $\BB(r,c-1)$ are $N$-free and have densities approaching $1-2^{-(c-1)}.$

The Geometric Erdös-Stone Theorem shows that $\ex(N,r) = 2^r – 2^{r-c+1} + o(2^r)$, which gives the asymptotic behaviour of $\ex(N,r)$ except when $c=1$. When $c=1$, the result is implied by the Binary Density Hales-Jewett Theorem which we proved last time.

We reformulate the Geometric Erdös-Stone Theorem below to facilitate its proof. The proof is a bit on the heavy side for a blog post, but it is surprizingly short considering the result, and it is easier than the proof of the Erdös-Stone Theorem.

Theorem: Let $c\ge 1$ be an integer. Then, for each integer $m\gt c$ and real number $\epsilon>0$, $$\ex( \BB(m,c); r) \lt (1- 2^{-(c-1)}+\epsilon) |\PG(r-1,2)|,$$ for all sufficiently large $r$.

Proof Sketch. The proof is by induction on $c$; the case that $c=1$ follows directly from the Binary Density Hales-Jewett Theorem. So we may assume that $c\gt 1$ and that the result holds for $c-1$.

Let $m\gt c$ be an integer, let $\epsilon\gt 0$ be a real number, and let $r\gg n$ be large integers. Now let $M$ be a rank-$r$ binary geometry with $|M| \ge (1-2^{-(c-1)}+\epsilon) |\PG(r-1,2)|$. By the inductive assumption, $M$ has a $\BB(n,c-1)$-restriction. Consider $M$ as a restriction of $\PG(r-1,2)$. Thus there are flats $F_0\subseteq F_1$ of $\PG(r-1,2)$ such that $\rank(F_1)=n$, $\rank(F_0)=n-c+1$, and $F_1-F_0\subseteq M$.

So by an easy averaging argument, there exists a rank-$(n+1)$ flat $F_2$ containing $F_1$ such that $$|M\cap(F_2-F_1)| \ge \left(1-2^{1-c} +\frac{\epsilon}{2}\right)|F_2-F_1| = (1-2^{1-c})2^{n} +\frac{\epsilon}{2} 2^n .$$

For a flat $F$ of $\PG(r-1,2)$ and point $e\not\in F$, we let $F+e$ denote the flat spanned by $F\cup\{e\}$. Let $e\in F_2-F_1$ and let $Q_0 = (F_0+e)-F_0$. Now let $F_0^c\subseteq F_1$ be a rank-$(c-1)$ flat that is disjoint from $F_0$. Now let $S= (F_2-F_1)\cap E(M)$ and, for each $f\in Q_0$, let $S_f = (F_0^c + f)\cap S$. Note that $(S_f\, : \, f\in Q_0)$ partitions $S$ and $|S_f|\le 2^{c-1}$. By another easy averaging argument, there is a $\frac{\epsilon}{2} 2^n$-element subset $Q_1$ of $Q_0$ such that $|S_f|= 2^{c-1}$ for each $f\in Q_1$. By the Binary Density Hales-Jewett Theorem, there is a subset $Q_2$ of $Q_1$ such that $M|Q_2 \cong \AG(m-c, 2)$. Let $F$ be the flat of $\PG(n-1,2)$ spanned by $F_0^c$ and $Q_2$. Thus $F$ has rank $m$, $F_0^c\subseteq F$, and, since $Q_2\subseteq Q_1$, $F-F_1\subseteq M$. So the restriction of $M$ to $F-F_0$ gives $\BB(m,c)$, as required. $\Box$

Open problem

Bonin and Qin [BQ00] determine exact values for the Turán numbers for several classes of geometries. There are many other natural classes that are yet to be considered; this might be an interesting avenue for further research. I will conclude with one problem in that direction. We call a binary geometry $c$-critical if it has critical exponent $c$ and each of its proper restrictions has critical exponent $\lt c$.

Conjecture: For any $c$-critical binary geometry $N$, $\ex(N,r) = 2^r – 2^{r-c+1},$ for all sufficiently large $r$.

References

[BQ00] J.E. Bonin, H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Math. 224 (2000).

[ES46] P. Erdös, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946).

[GN] J. Geelen, P. Nelson, An analogue of the Erdös-Stone Theorem for finite geometries, arXiv:1203.1911