There has been enough interest that I think we can formally declare Rota’s Basis Conjecture to be Polymath 12. I am told that it is standard Polymath practice to start a new blog post whenever the number of comments reaches about 100, and we have reached that point, so that is one reason I am writing a second post at this time. I am also told that sometimes, separate “discussion” and “research” threads are created; I’m not seeing an immediate need for such a separation yet, and so I am not going to state a rule that comments of one type belong under the original post whereas comments of some other type belong under this new post. I will just say that if you are in doubt, I recommend posting new comments under this post rather than the old one, but if common sense clearly says that your comment belongs under the old post then you should use common sense.

The other reason to create a new post is to take stock of where we are and perhaps suggest some ways to go forward. Let me emphasize that the list below is not comprehensive, but is meant only to summarize the comments so far and to throw in a few ideas of my own. Assuming this project continues to gather steam, the plan is to populate the associated Polymath Wiki page with a more comprehensive list of references and statements of partial results. If you have an idea that does not seem to fit into any of the categories below, please consider that to be an invitation to leave a comment about your idea, not an indication that it is not of interest!

### Matroids with No Small Circuits

I want to start with an idea that I mentioned in my MathOverflow post but not in my previous Polymath Blog post. I think it is very promising, and I don’t think many people have looked at it. Geelen and Humphries proved that Rota’s Basis Conjecture is true for paving matroids. In the case of vector spaces, what this means is that they proved the conjecture in the case where every (*n* – 1)-element subset of the given set of *n*^{2} vectors is linearly independent. It is natural to ask if *n* – 1 can be reduced to *n* – 2. I have not digested the Geelen–Humphries paper so I do not know how easy or hard this might be, but it certainly could not hurt to have more people study this paper and make an attempt to extend its results. If an oracle were to tell me that Rota’s Basis Conjecture has a 10-page proof and were to ask me what I thought the method was, then at this point in time I would guess that the proof proceeds by induction on the size of the smallest circuit. Even if I am totally wrong, I think we will definitely learn something by understanding exactly why this approach cannot be extended.

### Independent Partial Transversals

Let me now review the progress on the three ideas I mentioned in my first blog post. In Idea 1, I asked if the *n*^{2} vectors could be partitioned into at most 2*n* – 2 independent partial transversals. A nice proof that the answer is yes was given by domotorp. Eli Berger then made a comment that suggested that the topological methods of Aharoni and Berger could push this bound lower, but there was either an error in his suggestion or we misunderstood it. It would be good to get this point clarified. I should also mention that Aharoni mentioned to me offline that he unfortunately could not participate actively in Polymath but that he did have an answer to my question about their topological methods, which is that the topological concepts they were using were intrinsically not strong enough to bring the bound down to *n* + 1, let alone *n*. It might nevertheless be valuable to understand exactly how far we can go by thinking about independent partial transversals. Ron Aharoni and Jonathan Farley both had interesting ideas along these lines; rather than reproduce them here, let me just say that you can find Aharoni’s comment (under the previous blog post) by searching for “Vizing” and Farley’s comment by searching for “Mirsky.”

### Local Obstructions

Idea 2 was to look for additional obstructions to natural strengthenings of Rota’s Basis Conjecture, by computationally searching for counterexamples that arise if the number of columns is smaller than the number of rows. Luke Pebody started such a search but reported a bug. I still believe that this computational search is worth doing, because I suspect that any proof that Rota’s Basis Conjecture holds for all matroids is going to have to come to grips with these counterexamples.

Note that if we are interested just in vector spaces, we could do some Gröbner basis calculations. I am not sure that this would be any less computationally intensive than exhausting over all small matroids, but it might reveal additional structure that is peculiar to the vector space case.

### Algebraic Geometry

There has been minimal progress in this (admittedly vague) direction. I will quote Ellenberg’s initial thoughts: “If you were going to degenerate, what you would need to do is say: is there any version of this question that makes sense when the basic object is, instead of a basis of an *n*-dimensional vector space *V*, a 0-dimensional subscheme of *V* of degree *n* which is not contained in any hyperplane? For instance, in 2-space you could have something which was totally supported at the point (0,1) but which was “fat” in the horizontal direction of degree 2. This is the scheme *S* such that what it means for a curve *C* to contain *S* is that *S* passes through (0,1) and has a horizontal tangent there.”

Let me also mention that Jan Draisma sent me email recently with the following remarks: “A possible idea would be to consider a counterexample as lying in some suitable equivariant Hilbert scheme in which being a counterexample is a closed condition, then degenerate to a counterexample stable under a Borel subgroup of *GL _{n}*, and come to a contradiction. ‘Equivariant’ should reflect the action of

*GL*× (

_{n}*S*⋉

_{n}*S*). However, I have not managed to make this work myself, even in low dimensions. In fact, having a good algebro-geometric argument for the

_{n}^{n}*n*= 3 case, rather than a case-by-case analysis, would already be very nice!”

### Alon–Tarsi Conjecture

Now let me move on to other ideas suggested in the comments. There were several thoughts about the Alon–Tarsi Conjecture that the Alon–Tarsi constant *L _{n}*

^{even}–

*L*

_{n}^{odd}≠ 0 when

*n*is even. Rebecca Stones gave a formula that, as Gil Kalai observed, equated the Alon–Tarsi constant with the top Fourier–Walsh coefficient for the function det

^{n}; i.e., up to sign, the Alon–Tarsi constant is

Σ_{A} (–1)^{σ(A)} det(*A*)^{n},

where the sum is over all zero-one matrices and *σ*(*A*) is the number of zero entries in *A*. This formula suggests various possibilities. For example one could try to prove that *L _{n}*

^{even}–

*L*

_{n}^{odd}≢ 0 (mod

*p*) where

*p*= 2

*n*+ 1 is prime, because in this case, det(

*A*)

^{n}must be 0, 1, or –1. This would already be a new result for

*n*= 26, and the case

*n*= 6 is small enough to compute explicitly and look for inspiration. Luke Pebody posted the results of some computations in this case.

Another possibility, suggested by Gil Kalai, is to consider a Gaussian analogue. Instead of random zero-one matrices, consider random Gaussian matrices and try to understand the Hermite expansion of det^{n}, in particular showing that the coefficient corresponding to all ones is nonzero. This might be easier and might give some insight.

Note also that in the comments to my MathOverflow post, Abdelmalek Abdesselam proposed an analogue of the Alon–Tarsi conjecture for odd *n*. I do not think that many people have looked at this.

### Generalizations and Special Cases

Some generalizations and special cases of the conjecture were mentioned in the comments. Proving the conjecture for graphic matroids or binary matroids would be an enormous advance. There is a generalization due to Jeff Kahn, in which we have *n*^{2} bases *B _{ij}* and we have to pick

*v*∈

_{ij}*B*to form an

_{ij}*n*×

*n*grid whose rows and columns are all bases. Another generalization was prompted by a remark by David Eppstein: Suppose we are given

*n*bases

*B*

_{1}, …,

*B*of a vector space of dimension

_{n}*m*≤

*n*, and suppose we are given an

*n*×

*n*zero-one matrix with exactly

*m*1’s in every row and column. Can we replace each 1 in the matrix with a vector in such a way that the

*m*vectors in row

*i*are the elements of

*B*and such that the

_{i}*m*vectors in every column form a basis?

Juan Sebastian Lozano suggested the following reformulation: Does there exist a group *G* such that *V* is a representation of *G* and there exists *g _{i}* ∈

*G*such that

*g*

_{i}*B*=

_{i}*B*

_{i+1}, and for every vector

*b*∈

*B*

_{1},

span{*g*^{0}*b*, …, *g*^{n – 1}*b*} = *V*

where *g ^{i}* =

*g*…

_{i}*g*

_{1}and

*g*

^{0}is the identity?

### Other Ideas

Fedor Petrov mentioned a theorem by him and Roman Karasev that looks potentially relevant (or at least the method of proof might be useful). Let *p* be an odd prime, and let *V* be the **F**_{p}-vector space of dimension *k*. Denote *V*^{*} = *V* \ {0} and put *m* = |*V*^{*}|/2 = (*p ^{k}* – 1)/2. Suppose we are given

*m*linear bases of the vector space

*V*

(*v*_{11}, …, *v*_{1k}), (*v*_{21}, …, *v*_{2k}), …, (*v*_{m1}, …, *v*_{mk}).

Then there exist pairwise distinct *x*_{1}, …, *x _{m}*,

*y*

_{1}, …,

*y*∈

_{m}*V*

^{*}and a map

*g*:[

*m*] → [

*k*] such that for every

*i*∈ {1, …,

*m*} we have

*y*–

_{i}*x*=

_{i}*v*

_{ig(i)}.

Gil Kalai notes that the Alon–Tarsi conjecture is related to the coloring polynomial of a graph and asks if we can learn anything by considering more general polynomials such as

Π {(*x _{i}* –

*λ*) :

_{e}x_{j}*i*<

*j*, {

*i*,

*j*} =

*e*∈

*E*(

*G*)},

where the *λ _{e}* are weights associated to the edges

*e*.

Thank you for this wonderful summary!

Here are some very preliminary thoughts which might be of interest. I was thinking that a perhaps instructive structure might be the exterior algebra on . There are three things that are attractive about this:

1) If we consider Rota’s basis conjecture to be a statement on the existence of certain non-zero elements in the power of the graded algebra, then prima facie, it looks like the idea of a paving matroid is exactly a vector space upon which you can induct on the dimension of when proving the existence of these non-zero elements. I don’t think that this will give new information about the matroid problem — in fact it seems to me that the obstruction to doing this more generally is exactly the combinatorial/independence problem which the more general matroid approach aims to solve. However, if there is some structure specific to the vector space case, as opposed to the matroid, it seems the exterior algebra would be the natural place to capture it.

2) I do not understand fully the discussion of the Alon–Tarsi Conjecture above, but it seems that if we are talking about the signs of permutations (i.e. looking for odd v even latin squares, where the elements in our squares are basis elements), then one might be able to recover the formula given by Rebecca Stone by considering the action of on the highest exterior power in the exterior algebra. This might lend itself to some generalization (it seems to me that this is roughly the context of the mathoverflow question you link on the Alon–Tarsi Conjecture for odd , not with the exterior algebra, but with the tensor algebra, but that was just at a glance).

3) Speaking of my reformulation on the last post: one can probably make a representation theoretic reformulation on the exterior algebra (e.g. maybe using the ‘induced representation’, meaning the representation passed into the exterior algebra) in which one might get explicit conditions on the determinants of the things in the image of the homomorphism into .

Anyway, my general point is simply that the exterior algebra might be a good place to think about the intersection of some of the approaches, which might help in the solving the problem, even if I doubt it is anywhere near enough on its own.

Comment by Juan Sebastian Lozano — March 7, 2017 @ 12:24 am |

Small comment on the algebraic geometry, still with very little content: Draisma’s comment is a much better way of saying what I was trying to say. Or rather, you might say: the content of my question is to ask what it would *mean* for a degenerate (e.g. Borel-fixed) object to be a “counterexample” to Rota (since it wouldn’t literally be subject to Rota’s conjecture in its original form.) I also want to endorse Draisma’s bringing up of the symmetry group GL_n × (S_n ⋉ S_n)^n, which acts on every vector space in this whole story and their symmetric powers too. What do we know about the ring of invariants?

Comment by JSE — March 7, 2017 @ 5:04 am |

I briefly discussed Draisma’s idea with Patrick Brosnan. One somewhat annoying fact is that Rota’s Basis Conjecture (or any variation or generalization that I have seen) hypothesizes that certain sets are bases, and being a basis is an

opencondition rather than aclosedcondition. I’m not sure how serious an obstacle this is?Comment by tchow8 — March 28, 2017 @ 3:00 pm |

Have people seen this paper that just came out? It should be checked.

Carlos Gamas, ON THE CONJECTURE OF ALON-TARSI, Gulf Journal of Mathematics Vol 4, Issue 4 (2016) 108-116

Abstract. The Alon-Tarsi Conjecture states that for even n, the number of even latin squares of order n differs from the number of odd latin squares. In this note we prove that this conjecture is true if and only if there exists a permutation ζ ∈ S_{n^2} and a spherical function, φ, such that φ(ζ)\ne 0.

Comment: it looks like there are a couple of misprints in this paper. Hopefully they are not serious. (Both the spherical function and the permutation are defined at the beginning of the paper. So the actual statement in the abstract could be misleading?)

Comment by David Glynn — March 7, 2017 @ 9:33 am |

It seems that the Gaussian analog is actually equivalent to the Alon-Tarsi conjecture.

It can be formulated as follows:

Let be even and let be a random matrix. Then the expectation

is non zero.

(Perhaps it is positive.)

We can take to be a random Boolean matrix with entries or a random Gaussian matrix with entries distributed .

There is maybe some hope that because we know a lot about random Gaussian matrices (and correlation inequalities for Gaussian measures) there will be some other way/formula showing that the expectation in question for the Gaussian case is positive.

Comment by Gil Kalai — March 7, 2017 @ 2:00 pm |

Sorry to be dense, but why is the Gaussian analog equivalent to the Alon-Tarsi conjecture?

Comment by tchow8 — March 10, 2017 @ 12:09 am |

Suppose the elements of X are independent, symmetric about 0 and each have non-0 finite variance. We do not assume identical distributions.

Express as a polynomial in the .

It is a homogeneous polynomial of degree in variables, in which each monomial contains each variable at least once.

The expected value of any monomial is 0 if it has a variable raised to an odd power (since each variable is symmetric around 0 and they are all independent). Any monomial that is not of such a form must include every variable at least twice. By the degree condition, it must include each variable exactly twice.

Therefore the expectation of is equal to times the product of the variances of the cells, where is independent of the distribution of the cells, and is equal to the coefficient in .

Finally: can be written as the sum of elements of the product of the signs of the sigmas times , which is equal to precisely when the sigmas form the rows of a Latin square.

Therefore Alon-Tarsi is equivalent to the expectation of being non-0.

Comment by Luke Pebody — March 28, 2017 @ 6:38 pm |

Tim asked me to write something about online versions of Rota’s Basis

conjecture. Here, the n bases arrive one at a time, and after you receive

the i-th basis, you have to decide immediately in what order to write it

as i-th row of the array you are creating. Of course, the goal is that

the columns of the eventual array are again independent. Is

there an algorithm that does this for i up to and including n? There

are at least two versions of this question:

(1) The input consists of vectors in a vector space. In this case,

for _even_ n, the online version still follows from Alon-Tarsi (in

char 0), and for _odd_ n any online algorithm can be fooled in the

last steps (if the field contains sufficiently many roots of unity);

see https://arxiv.org/pdf/1312.5953.pdf

(2) The input consists of elements in an abstract matroid. In other

words, when the new basis arrives, you get told which subsets of

the elements so far are independent, but not more. In this case, an online algorithm

can be fooled regardless for any n≥3 (even with linearly realisable matroids); see page 9 of

https://arxiv.org/pdf/1312.5953.pdf

This leads to a question that I think might prove tractable: determine

the maximal number f(n)<n (n≥3) such that there exists an online

algorithm in scenario (2) for arranging f(n) bases, but not for arranging

f(n)+1 bases. E.g., does f(n) grow as a square root of n?

Comment by Jan Draisma — March 7, 2017 @ 3:57 pm |

No, I’m pretty sure is linear, at least and at most . Indeed you can do bases in dimensions (at least for linearly realisable matroids), but you can’t do them in dimensions.

For the lower bound, you simply use an extension of the argument from the linked paper above: There exist vectors for and such that they are in general position (i.e. any of them are linearly independent), but the vectors for are the same (non-zero) vector. (Proof: fix a prime that is greater than

, and choose the sum and the vectors with then at least one of and can be extended by some element of .

This is true for linearly realisable matroids because the space generated by the union of and is of dimension at least , so the intersection of the spaces generated by and by is of dimension at most , so is less than , so there is some element of that is not in the intersection of those spaces, so there is some element of that is either not in the space generated by or the space generated by .

So our strategy in dimension is: when the th basis arrives (for ), make it so the first sets of 4 columns each form an independent set of size , and then use Hall’s Basis Theorem to make the other columns all be independent.

It is clear by the basis exchange axiom that we can make the first sets of 4 columns each form an independent set of size (we start with an independent set of size and have independent vertices to choose from).

For the remainder, we have columns (of vectors each) of which the first pair of pairs of columns both make a matroid of dimension at least , the next pair of pairs of columns both make a matroid of dimension at least , and so on until the final pair of pairs of columns both make a matroid of dimension at least 2.

Create a bipartite graph with partition of the columns and of the vectors we need to add in from the latest basis, where an edge exists if the column and the vector make an independent set (of size ).

Each vertex in makes a matroid of dimension , so there are at least of the vertices in adjacent. In particular if is a subset of is of size at most , the total number of neighbours of is at least . If, on the other hand, is of size where , it includes both columns from one of the first pairs of columns, so it includes two pairs of columns which together make a matroid of dimension at most . So these two columns (let’s call them and ) are of size , and their union contains a set of size , so if is any set of size more than , either or is extendible by an element of . In particular, there are at most elements of which are not adjacent to either or , so there are at least neighbours of .

So the conditions of Hall’s Marriage Theorem apply, and we can add the remaining vectors of the basis to the matrix and make each column independent.

My instincts are that this proof can be improved to actually show that you can do , solving the problem completely. I did this for , but couldn’t quite do so for .

Comment by Luke Pebody — March 25, 2017 @ 5:38 pm |

If someone can edit this to make the latex things work, that would be very welcome. It seems to have caused a huge gap including the end of the proof of the upper bound and the start of the proof of the lower bound. Is there a ‘preview my post’ feature?

Comment by Luke Pebody — March 25, 2017 @ 5:43 pm |

I tried to fix your LaTeX; hopefully this is what you wanted. I’m new to WordPress myself so I am not aware of a “preview” feature; I agree that that would be nice.

Comment by tchow8 — March 26, 2017 @ 9:16 pm |

Thanks Tim, that looks a lot better.

It has occurred to me the Lemma I needed (if A, B, C and D are independent sets in a matroid with C contained in and with |C|+|D|>|A|+|B| then either A or B can be extended by some element of D) is true by the submodularity of the rank function applied to and .

The rank of the intersection of and is at least |D| clearly, and the rank of their union is at least |C|. It follows that the sum of their ranks is more than |A|+|B|, and hence either the rank of is more than |A| (and hence A is not a maximal independent set in ) or the rank of is more than |B| (and hence B is not a maximal independent set in ).

Comment by Luke Pebody — March 26, 2017 @ 9:57 pm |

Since this turned out pretty unreadable, I threw together some latex of the two proofs at https://www.overleaf.com/8773999gccdbdmfdgkm

Comment by Luke Pebody — March 26, 2017 @ 4:36 pm |

Pretty sure the same proof works to show you can do k+1 bases in 3k dimensions. What I’m using the groups of 4 for is that if you remove 0 or 1 columns, there’s still a pair remaining that works together. The same would be true with groups of 3.

Comment by Luke Pebody — March 26, 2017 @ 5:12 pm |

So I think it might be possible to extend this method to fully solve the question for online matroids.

I feel that the answer is that you can do k + 1 bases in rank 2k, but can’t necessarily do them in rank 2k-1. So far it is proved you can in rank 3k and can’t in rank 2k-1.

In order to place the (k+1)’th basis, it is sufficient to achieve that some 2 columns so far together have rank 2k, that if you cover up any column there are 2 columns remaining that together have rank at least 2k-1, that if you cover up any 2 columns there are 2 columns remaining that together have rank at least 2k-2 and so on (up to if you cover up any k-2 columns there are 2 columns remaining that together have rank at least k+2).

We stop at k-2, because it is trivial that if you cover up any k-1 columns there are 2 columns remaining that together have rank at least k+1: otherwise in the remaining k x (k+1) grid all the columns are maximal independent sets and all the rows are larger independent sets.

For k=2, you want to achieve that some 2 columns have rank 4, which is trivial to achieve in rank 4 by extending independent sets..

For k=3, you want to achieve both that some 2 columns have dimension 6 (trivial in rank 6 by extending independent sets) and also that if you cover up any column, some 2 uncovered columns have rank at least 5. Wondering if maybe someone can see how to achieve this in rank 6? (Or prove it can’t always be done)

In particular, for any k, we would be done if we could achieve that after the k’th basis, we can find k disjoint pairs of columns such that one pair combined has rank 2k, one pair has rank 2k-1, one pair has rank 2k-2, …, one pair has rank k+1. Maybe you can even arrange it so you can find k disjoint pairs of columns such that each pair combined has rank 2k?

Comment by Luke Pebody — March 28, 2017 @ 6:14 am |

I haven’t gotten around to studying your argument yet, but I just wanted to say that fully solving the question for online matroids would be an excellent partial result and I hope that others will jump in to help.

Comment by tchow8 — March 28, 2017 @ 3:08 pm |

So far I could only digest the lower bound. I think it might be useful to summarize it as follows. In an n-dimensional space, we pick a line, and n subspaces of dimension n/2 that all contain it, but are otherwise generic. For each subspace, take n/2 generating vectors. Then any n of these n x n/2 vectors are independent. So if we get them in a matrix as n/2 rows of length n, we can do nothing but randomly put them in columns. If we are unlucky, we might just group them exactly such that each column generates one of the n/2-dimensional subspaces. But then if the next row we get contains a vector from the line they have in common, we are #$&!ed.

Comment by domotorp — March 29, 2017 @ 11:25 am |

This is coming to an earlier question of Jordan-in what way could this conjecture made more general. I propose the following: Take any by array of nonzero vectors such that for any no matter how we pick vectors from distinct rows on each of the remaining rows we can find a vector not in their span. This is easily checked out by having bases on each of the rows or having the example of a vectors linearly independent on the first column and linear multiple of each of them on the rows.

One motivation for this is: we draw an -partite graph on the rows and draw an edge between the vertices in different parts if they are independent. Rota would say that each vertex is connected to at least vertices in any other part and then we want to find n disjoints paths through the parts of the graph. Jordan’s example is even more rich in edges, every vertex has degree .

The condition stated above seems very reminiscent of the marriage lemma condition.

Comment by VladM — March 7, 2017 @ 7:19 pm |

Once again, this fails on Colin McDiarmid’s example. Denote the edges of by and create duplicates of three of the edges. Then the sets , , and satisfy your condition but the conclusion of Rota’s Basis Conjecture fails.

I think it is going to be difficult to formulate a satisfactory generalization of this type without coming to grips with the “local obstructions” that I mentioned above.

Comment by tchow8 — March 7, 2017 @ 7:30 pm |

On Matroids with No Small Circuits.A paving matroid is one in which the sets of size less than the rank are

all independent. With Peter Humphries I proved that:

Theorem.Let be disjoint sets of size , and let

be rank paving matroids on

such that is a basis of for each .

Then there exist disjoint transversals of

such that is a basis of for each

.

This strengthening of Rota’s Basis Conjecture fails for matroids

in general and for for paving matroids. After an unpleasant

case analysis establishing the result for the case, the result

is proved by an easy inductive argument.

Tim is proposing extending the results in our paper, for any fixed

, to rank- matroids in which the -element sets are

all independent. It could well be true that the above theorem itself

would hold for such matroids so long as is large relative

to . To prove such a result one would likely need to do a lot

of work to establish it for some value of , but then the induction

should be easy.

I don’t see this leading to a full proof of Rota’s Basis Conjecture,

but it is a concrete approach toward interesting partial results.

On a related note, it is conjectured that the proportion of -element

matroids that are paving tends to one as goes to infinity. Given the

exciting new results of Jorn van der Pol and Rudi Pendavingh on the

structure of almost all matroids one might be able to prove that

Rota’s Basis Conjecture (for matroids) is almost always true.

Comment by Jim Geelen — March 7, 2017 @ 8:56 pm |

I have been reading the Geelen-Humphries paper and I would like to explain here the idea behind their induction step, which is the part of their argument that I think is most valuable if we are thinking of extending the results.

The starting point is the observation that in Rota’s Basis Conjecture, it is easy to arrange for the first column of the grid to be a basis. It is then natural to imagine covering up the first row and column and applying some kind of induction hypothesis to the remaining grid. However, several issues arise if we try to do this naively. First of all, the rows of the grid aren’t bases of an -dimensional vector space; they’re still sitting inside an -dimensional vector space. Secondly, and more seriously, even if we were to get the columns of the grid to all be linearly independent, there’s no guarantee that when we return to the original grid and add back the vector from the first row, the th column will still be linearly independent.

The first idea that Geelen and Humphries have to try to address these problems is

contraction. For those not familiar with matroid theory, contraction may be thought of as orthogonal projection: If is a set of nonzero vectors in a real vector space and , then thecontractionof by (written ) is obtained by orthogonally projecting all the vectors of onto the hyperplane perpendicular to , and deleting itself (which has been projected to zero, of course). This has the effect of reducing the rank by one, and also has the nice property that if we take any basis of the contraction and add back the original vector , we get a basis for the original vector space. In Rota’s Basis Conjecture, the idea is that for each column , we contract by . This (seemingly) addresses both issues in the previous paragraph.However, in the process of seemingly solving these issues, we’ve introduced new issues. The vectors in the first row are all distinct (in fact, linearly independent) so contracting by can give a totally different result from contracting by if . This is why Geelen and Humphries end up proving something about different matroid structures on the same ground set. Another issue is, if we contract by , how do we know that we’ll get a basis (for the contraction) in the th row? We somehow need to ensure that if we combine with the vectors , the result is a basis of the original space.

This latter condition is something that Geelen and Humphries state explicitly as a lemma, and prove using the assumption that we are dealing with paving matroids. Namely, they prove that if there are no linearly dependent sets of size less than (actually, as mentioned in the previous paragraph, they prove this for different paving matroid structures on the ground set, but I’ll ignore this for simplicity), then it is possible to find for all so that is a basis and also is a basis for all .

The interesting thing about this lemma is that it is a type of

basis exchangeproperty. We’re starting with bases and then we’re simultaneously swapping out elements from the first basis with one element from each of the other bases in a way that leaves everything a basis at the end. As indicated above, this particular basis exchange property does not hold in full generality, but relies on the assumption that there are no small linearly dependent sets. Geelen and Humphries prove this lemma by induction. Here I want to focus not on the induction step of this argument, but on the argument that lets them prove the base case, because it illustrates something that I think is of general interest for Rota’s Basis Conjecture.The key claim is the following: Suppose we have a matroid with no dependent sets of size less than , where . Let and be two disjoint independent sets of size , and let be any subset of of size 2 and let be any subset of of size 3. Then there exists and such that if we “swap” and , then the resulting sets and are independent.

How do we prove this claim? First we note the following: Denote the two elements of by and , and let be arbitrary; then we claim that either or is independent. For if not, they are both linearly dependent, and since there are no dependent sets of size less than , they are both

circuits(minimal dependent sets). They are distinct and both contain , so by the circuit elimination axiom of matroid theory, their union, minus , must contain a circuit. But their union minus is a subset of itself, which is independent; contradiction. So, either or is independent. Now apply this argument to each element in turn; by the pigeonhole principle, there must be some such thatbothand are independent (or else this claim holds for , but without loss of generality we may assume that it is ). Then, applying the argument at the beginning of this paragraph with in place of and in place of , we can infer that for one of or —and without loss of generality we may assume it is —we must have is independent as well.The reason I think the argument in the previous paragraph is interesting is that it can be interpreted as saying that

the absence of small circuits implies a weak form of base-orderability. Base-orderability is, I think, a crucial concept for the conjecture; it is known that strongly base-orderable matroids not only satisfy Rota’s Basis Conjecture but also have no local obstructions, so they satisfy various strengthenings of the conjecture. I may say something more about this later, but this comment is already long enough!Comment by tchow8 — March 9, 2017 @ 5:16 pm |

The argument seems correct, except that it seems that half of the time you wrote independent instead of dependent; so in the claim, we need to suppose that there is no dependent set of size less than . Also, let me remark that it might be better to suppose from the beginning that and are disjoint (otherwise the statement is not necessarily true).

Comment by domotorp — March 9, 2017 @ 9:06 pm |

I fixed the dependent/independent typos; thanks!

What’s a counterexample when and are not disjoint?

Comment by tchow8 — March 9, 2017 @ 10:54 pm |

If and .

Comment by domotorp — March 10, 2017 @ 9:11 am |

Ah, I see. Technically, and are independent in this case as well, but they now have smaller cardinality than the original independent sets, and the term “swap” is misleading, so I agree that it is better to specify that and are disjoint.

Comment by tchow8 — March 20, 2017 @ 4:59 pm |

I think that the prospects for generalizing Geelen–Humphries are good. Here are some thoughts.

Definition.Let be a non-negative integer. Say that a matroid of rank is-pavingif it has no circuits of size less than .Thus a 0-paving matroid is a uniform matroid and a 1-paving matroid is a paving matroid in the usual sense. I believe that it is straightforward to prove the following Proposition (though it would be good for someone to verify):

Proposition.For any fixed , the class of -paving matroids isminor-closed; i.e., if you delete or contract an element of a -paving matroid, the result is a -paving matroid.My first thought is that it is natural to try to generalize the Geelen–Humphries result to -paving matroids.

A second observation is that, as I alluded to an in earlier comment, a key lemma in their paper is the following:

Key Lemma.Let be disjoint sets of size , and let be rank- paving matroids on such that is a basis of for each . Then there is an ordering of the elements of as and a transversal of such that the set is a basis of , and for all , is a basis of .One thing that I realized recently is that if all the matroids are identical, with say, then the Key Lemma holds for

anymatroid , not just paving matroids. This follows from the following result, which I believe was first proved in “Comments on bases in dependence structures” by Richard Brualdi,Bull. Austral. Math. Soc.1(1969), 161–167.Strong Basis Exchange.If and are bases of a matroid, then for any there exists such that both and are bases.To prove the Key Lemma when , use Strong Basis Exchange to swap each in turn with some , as runs from 2 to .

I think that the Key Lemma is false in general if the are not all identical and are not all paving matroids (though I don’t have a counterexample offhand; maybe someone else can construct one). Certainly Brualdi’s proof breaks down. However, I suggest the following plan: Tinker with the statement of the Key Lemma, as well as the statement of the Theorem in Geelen’s comment above, to get the induction step of Geelen–Humphries to work for a more general class of matroids than paving matroids (perhaps -paving matroids, or perhaps an even more general class of matroids). This seems eminently doable to me. Of course, even if this plan succeeds, it doesn’t prove much by itself in the absence of a proof of the base case. But I think it would be an important step forwards.

Comment by tchow8 — March 20, 2017 @ 6:16 pm |

Here are some further thoughts about the “tinkering” I mentioned above.

Suppose that we modify the Theorem in Geelen’s comment by replacing “paving matroid” with “2-paving matroid.” I don’t know if this modified assertion is true, but suppose we try to prove it using similar methods. If I haven’t made a mistake, the class of 2-paving matroids is minor-closed, so the same strategy, of using contraction to reduce to a smaller instance, has a fighting chance of working. In fact, I think that if the Key Lemma holds for 2-paving matroids then the inductive step (though not necessarily the base case) of the proof of the Theorem should go through.

However, some trouble arises when we try to prove the Key Lemma by mimicking the argument of Geelen and Humphries. I think you can only conclude that if you pick any

threeelements of a basis then you can swap one of them out with an element of a disjoint basis of another 2-paving matroid (provided that the rank is at least seven), and this lets you get to be a basis as well as to be a basis for , but then you get stuck at the last step .Now maybe the Key Lemma is still true, and one just needs a different argument. On the other hand, here’s another possible diagnosis of what’s going wrong: We know that the Key Lemma is true for all matroids when all the matroid structures are equal, and what’s causing us trouble is that we’re trying to prove it for a whole

sequenceof distinct matroid structures . It seems difficult to avoid considering different matroid structures on the same ground set if we stick to the strategy of contracting a different vector for each column. Nevertheless, from the point of view of Rota’s Basis Conjecture, we don’t necessarily need to prove the Key Lemma forarbitrary. For example, the that arise in the (purported) inductive proof of Rota’s Basis Conjecture areall minors of the same initial matroid. So maybe what we need to do is to narrow our sights a little and only try to prove the Key Lemma for matroids that enjoy some degree of similarity, that is preserved when we perform certain sequences of deletions and contractions from the same starting matroid. By the same token, the Theorem itself might need to be similarly narrowed. These narrowings might make the Key Lemma (and the Theorem) easier to prove, yet still general enough to imply Rota’s Basis Conjecture.Comment by tchow8 — March 21, 2017 @ 8:44 pm |

Question.Let be a base-orderable matroid with ground set , and let . Let and be matroid structures on , each of which is obtained by a sequence of deletions and contractions of the elements of (but not necessarily the same sequence of deletions and contractions; so although and are both minors of and have the same ground set , they are not necessarily isomorphic). Suppose further that and have the same rank. Is it necessarily the case that if is a basis of and is a basis of , then there exists a bijection such that for all , is a basis of and is a basis of ?It is plausible to me that the answer is yes. For example, note that an independent set of a minor is independent in the original matroid, so both and are necessarily independent in . It seems plausible that we could extend both of them to bases in , use the base-orderability of to get a bijection, and then restrict the bijection. Or something like that.

If the answer is yes, then I think that the Geelen–Humphries induction argument goes through for base-orderable matroids. In the Theorem of Geelen’s comment above, we replace “paving matroid” by “base-orderable matroid,” and we also require that all matroid structures arise from a sequence of deletions and contractions from the same starting matroid. We modify the Key Lemma similarly. The Key Lemma then follows from a positive answer to the Question, because we can swap each in turn with some as runs from 2 to . Then we can apply the induction hypothesis to the contractions restricted to the set .

Comment by tchow8 — March 29, 2017 @ 1:23 am |

Unfortunately, the answer to the Question is no. Let be the matroid associated with the graph that is a disjoint union of two triangles and . Choose and , and let and let . Then all these matroids are base-orderable, and and are even abstractly isomorphic (but not equal), but it is easy to check that the desired bijection does not necessarily exist.

Comment by tchow8 — March 29, 2017 @ 5:51 pm |

Let me say a bit more about base-orderability. A matroid is

strongly base-orderableif, for any two bases and , there exists a bijection such that for any subset , the set is a basis. It is not hard to show that this axiom implies that is also a basis. Strong base-orderability is a very strong condition. We have the following result:Proposition.Let be a strongly base-orderable matroid of rank with elements, and suppose that there exists a partition of into disjoint bases. Given any disjoint independent sets with , there exists an grid such that the elements of appear in row and such that both columns are bases of .Sketch of proof: Let and be disjoint bases of . Denote the elements of by . Let be the the bijection guaranteed by strong base-orderability, and write for , for , etc. Construct any grid such that the elements of appear in row . Then a Hall’s marriage theorem argument along the lines of Proof 2 of Theorem 1 in this paper shows that we can permute the elements within each row so that both columns contain the numbers through

if we erase the primes. Strong base-orderability implies that the two columns must be bases.Theorem 4 of this paper then implies that the generalization of the above Proposition with replaced by any larger number is also true, and so this yields a proof of Wild’s theorem that Rota’s Basis Conjecture holds for strongly base-orderable matroids.

As already discussed in earlier comments, there are local obstructions (such as and ) that prevent the above Proposition from being true in general. The point is that these local obstructions vanish in the presence of strong base-orderability. Thus if we wish to search for local obstructions, we should look at non-base-orderable matroids. Another way to think about it is that if we want to generalize Wild’s theorem, we might want to look at weaker base-orderability hypotheses and see how far we can get with them. A very optimistic, but not inconceivable, route to proving Rota’s Basis Conjecture would be to formulate a generalization to grids that has some kind of weak base-orderability hypothesis with two properties: (1) when , blocks annoying counterexamples like and , and (2) when , is automatically satisfied by all matroids.

Administrative note: I will be unavailable to participate in Polymath for the next week or so. Obviously, this should not prevent others from continuing to work.

Comment by tchow8 — March 10, 2017 @ 12:00 am |

Here is another thought about base-orderability. A matroid is said to be

base-orderable(note that I have dropped the adverb “strongly”) if for any two bases and , there exists a bijection such that for every , the sets and are both bases. The following theorem is proved in J. de Sousa and D. J. A. Welsh, “A characterisation of binary transversal structures,”J. Math. Anal. Appl.40(1972), 55–59.Theorem.A binary matroid (i.e., a matroid representable by vectors in a vector space over the field with two elements) is base-orderable if and only if it contains no minor.As we have seen, base-orderability (or at least strong base-orderability) makes life easier for the would-be prover of Rota’s Basis Conjecture. So one could imagine a strategy for proving Rota’s Basis Conjecture for binary matroids that proceeds along the following lines: When base-orderability seems to be useful, split into two cases. In Case A, go ahead and assume base-orderability. In Case B, exploit the above theorem to conclude that there must be a minor lying around somewhere, and do something special to take care of it.

Comment by tchow8 — March 21, 2017 @ 9:01 pm |

I’m having trouble figuring out how to prove that if you delete an element from a base-orderable matroid then the resulting matroid is still base-orderable. Of course if the rank equals the rank then this is obvious, but if then the obvious line of argument is to extend the given bases and of to bases and of , then restrict the bijection to . The thing I’m worried about is that maybe and sends some element of to , in which case does not restrict to a bijection between and .

I’m confident the result is true because I see it stated everywhere. Welsh’s book even gives a proof but it’s essentially the above argument and so it looks to me as though it has a gap. Oxley’s book states it as an exercise and cites the literature, but when I looked up the papers the terminology was sufficiently different that I couldn’t figure out how to extract what I wanted. Can someone else help?

Comment by tchow8 — March 23, 2017 @ 1:58 am |

O.K., I see what I was missing now:

Fact.Let be base-orderable. Let and be bases of , and let be a bijection whose existence is guaranteed by the base-orderability axiom. Then restricted to must be the identity map.The proof is obvious as soon as you think about it: If and is

notthe identity map, then contains “two copies of ” and hence cannot be a basis.So now returning to the “obvious line of argument” in my comment above, if then that must mean that every basis of contains . In particular, and must both contain , and by the above Fact, is the identity on . So does indeed restrict to a bijection between and , and we’re done.

I am now hopeful about proving Rota’s Basis Conjecture for base-orderable matroids, which would generalize Wild’s result that the conjecture holds for

stronglybase-orderable matroids.Comment by tchow8 — March 28, 2017 @ 2:52 pm |

Some remarks on Alon-Tarsi conjecture as a correlation inequality (that Tim asked about). (I inquired a few random matrices friends and this comment reflects also a discussion with Ofer Zeitouni and remarks by Krzysztof Oleszkiewicz and Ron Peled).

Start with any symmetric (around zero) real probability distribution and consider an random matrix with entries i.i.d. from and consider the expectation

.

When you evaluate this expectation in terms of monomials in the the contribution of monomials that appears with degree one is zero. (Because is symmetric around zero). The contribution to the monomial

is precisely a signed summation of Latin squares. This comes from the product of disjoint generalized diaginals in the expansion of ,

The sign is the product of signs of all permutations representing these generalized diagonals.

This expression does not depend on the distribution, it is zero when is odd, and the common belief that for even values of there are more even than odd Latin squares gives (I think) that

is negative when and is positive if . (This should be double checked).

Three comments:

1) I am less optimistic now that this probabilistic interpretation is useful. For Gaussian matrices there are nice expressions for the joint eigenvalues distribution but it does not seem to mix well with the product of entries. Of course the key would be to give another expression for this correlation or a wider context but I dont see any.

2) It would be nice to examine the case for complex distributions and some familiar families of random matrices like random Hermitian matrices.

3) This observation is essentially Theorem 1.9(e) of Kumar and Landsberg’s paper CONNECTIONS BETWEEN CONJECTURES OF ALON-TARSI, HADAMARD-HOWE, AND INTEGRALS OVER THE SPECIAL UNITARY GROUP.

Comment by Gil Kalai — March 10, 2017 @ 8:07 am |

There are very relevant papers by Jeannette Janssen. One classic paper The Dinitz problem solved for rectangles contains a proof based on Alon-Tarsi theorem of a rectangle case of Dinitz conjecture. It is very interesting if the polynomial used by Janssen can beused to prove a “rectangular” (this a bit weaker) case of the Rota conjecture. (Note that a similar slightly weaker form of the conclusion of Rota conjecture is conjectured by Ron Aharoni in much greater generality.) The other paper is On even and odd Latin squares. It contains the relation between the various definitions of signs of matrices (mentioned in my previous comment). Another remark is that the conjecture that there are more even Latin squares than odd ones may well be a wishful thinking based on a few very small cases. I wonder if somebody can offer a heuristic explanation why this should be true.

Comment by Gil Kalai — March 14, 2017 @ 8:07 am |

As a starting point for a heuristic argument that there are more even Latin squares than odd ones, we might note that the number of even derangements of minus the number of odd derangements of is . Admittedly, I’m not quite sure what to do with this observation…

Comment by tchow8 — March 28, 2017 @ 3:11 am |

This means that the number of row-even partial Latin squares minus the number of row-odd partial Latin squares is

.

Clearly for this difference will be 0, so maybe we should instead consider partial matrices where the first row is .

Then for the difference is 1, for , it is ,

and for , it is 0, 0, 2, 0, 72, -320, 3600, -32256, …, which is at http://oeis.org/A098276. For , the sequence starts 0,0,0,24,-576,12960.

Comment by Luke Pebody — March 28, 2017 @ 4:59 am |

It may be worth mentioning that Levent Alpoge has used the Kumar–Landsberg result to estimate the size of the Alon–Tarsi constant. Unfortunately, from the point of view of Rota’s Basis Conjecture, he provides only an upper bound rather than a lower bound, but I think it is still an interesting result.

Comment by tchow8 — March 20, 2017 @ 6:29 pm |

[…] the occasion of Polymath 12 devoted to the Rota basis conjecture let me remind you about the Alon-Tarsi conjecture and test […]

Pingback by Test Your Intuition about the Alon-Tarsi Conjecture | Combinatorics and more — March 15, 2017 @ 10:29 am |

Let me provide another possible inductive approach:

Let be a sequence split into some subsequences (called color classes).

We say that another subsequence is rainbow, if it contains at most one element from each .

Now the lemma: (from https://arxiv.org/abs/1702.08170)

Let be a matroid of rank and be a sequence of elements from ,

split into subsequences, each of length at most .

Then any largest independent rainbow subsequence of is a basis of

if and only if (*) there does not exist an integer and set of color classes, such that the union of these color classes has rank .

The idea would be to remove the largest independent rainbow set, leaving elements and use recursion. This of course does not always work, in many cases the remaining elements will not satisfy (*),

but it seems to me that in this case one can try to use some backtracking (going several steps back if necessary) and exchange axiom to force (*).

Comment by Pavel Paták — March 23, 2017 @ 9:13 am |

This is an interesting idea. My guess is that a more promising approach than backtracking is to try to modify/generalize the lemma to make the induction/recursion go through

withoutbacktracking. Once you start backtracking, it becomes difficult to keep track of all the different cases that could arise.More specifically, can you give examples of how (*) can fail after a basis is removed? Then we could think about what conditions are needed to ensure that this scenario can’t happen. That will require modifying the induction hypothesis and maybe force more conditions, but hopefully the modification process will eventually converge.

Comment by tchow8 — March 28, 2017 @ 1:27 am |

Is Rota’s basis conjecture]implied by the same statement restricted to vector spaces over a fixed field (say , or even )?

Comment by dominiczypen — March 28, 2017 @ 6:17 am |

This is not known.

Comment by tchow8 — March 28, 2017 @ 2:41 pm |