Google Summer of Code 2014

Google’s Summer of Code is an annual event in which Google will pay a bunch of students to spend the summer writing code for open-source projects.

As last year, Sage┬áis one of the mentoring organizations, and as last year, we are hoping to have one of about 4 students work on Sage’s matroid capabilities. We are looking for an undergraduate or graduate student who

  • Knows a bit of matroid theory (some possible topics require more knowledge than others)
  • Has some programming experience, preferably in Python
  • Wants to work on building exciting mathematics software for 3 months during the summer
  • Would like the word “Google” on his or her CV
  • Is interested in earning 5500 US dollars and a t-shirt

On the ideas page, a list of possible features to work on can be found. Students must produce a detailed proposal including a timeline with milestones. Early interaction with the mentors is important: we want to know you’re serious about this, and able to deliver. The place for this is the sage-gsoc Google group.

If you know an interested student, send her or him to this post. If you are an interested student, study the links above to figure out the requirements, timeline, etc. One important date: applications must be in on

MARCH 21

and we’d like to start working on the proposal with you well before then.

Rota’s Basis Conjecture

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.

The Geometric Erdös-Stone Theorem

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