Rota’s Basis Conjecture: Polymath 12?

February 23, 2017

Rota’s Basis Conjecture: Polymath 12?

Filed under: polymath proposals — tchow8 @ 11:44 pm

This post tentatively kicks off Polymath 12 on Rota’s basis conjecture.

I proposed Rota’s basis conjecture as a possible Polymath project on MathOverflow last year. If you have not read my proposal, I strongly recommend that you read it now, because in it, I sketched some reasons why I thought this would make a good Polymath project, as well as some known partial results and potential avenues for progress.

Recently, I emailed several likely participants, and a number of them responded enthusiastically, enough in my opinion to warrant an attempt to start a Polymath project. I have discussed the possibility with the polymath blog admins and since I do not have a blog of my own, they have generously agreed to host the project here on the polymath blog itself. This means that you should comment freely in the comments section below.

Rota’s basis conjecture states that if B₁, B₂, …, B_n are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (v_ij) such that

1. the n vectors in row i are the members of the ith basis B_i (in some order), and

2. in each column of the matrix, the n vectors in that column form a basis of V.

If this project gets enough momentum to be formally declared “Polymath 12” then it will be important to give a thorough summary of what is already known, and to lay out in some detail all the promising directions. However, at this early stage, I think that it is important to have some “quick wins” to get things moving, so I would like to present a couple of new ideas that I think could lead to some new partial results quickly, and also invite others to present their own ideas.

Idea 1

The first idea is to extend an old result of Aharoni and Berger that I think has not received too much attention from others. Suppose we have two matroids on the same ground set E. By definition, a common independent set is a subset of E that is independent in both matroids. We can try to partition E into a disjoint union of common independent sets, and can ask the question, what is the smallest number β of common independent sets that we need?

Here is the relation to Rota’s basis conjecture. The ground set E has n² elements, and one of the matroids is defined by the given set of n² vectors (here, if the same vector appears in more than one basis, we treat the different occurrences as being distinct). The second matroid is the so-called transversal matroid whose independent sets are precisely those subsets of E that contain at most one element from each B_i. From this point of view, Rota’s basis conjecture says that β = n, i.e., that E may be partitioned into n disjoint common independent sets (each necessarily of size n).

Aharoni and Berger have proved a general theorem about matroids that implies, in the specific case of Rota’s basis conjecture, that β ≤ 2n. They also have a very general conjecture on matroids that would imply that β ≤ n + 1 for Rota’s basis conjecture.

Let me now make the simple observation that it is easy to prove directly that β ≤ 2n – 1 for Rota’s basis conjecture. We begin with a lemma. Suppose we have a matroid and suppose that I₁, …, I_n are independent sets with |I_i| = i for all i. Call this a triangular system. Then I claim that there exists a way of choosing a v_i from each I_i in such a way that J₁ := {v_i} is independent. The proof is easy: We start with the forced choice v₁ ∈ I₁, and then note that by the independent set axiom, since |I₂| = 2, there must exist some v₂ ∈ I₂ that can be added to v₁ to produce an independent set of size 2. Similarly, once v₁ and v₂ are chosen, it follows directly from the independent set axiom that we can add some v₃ ∈ I₃, and so on. This proves the lemma. Now, once J₁ has been constructed, we can imagine removing the elements of J₁ from the original triangular system to obtain a smaller triangular system. We can then repeat the argument on this smaller system to form an independent set J₂ that contains exactly one element from each I_i for i = 2, 3, …, n. This shows that the original triangular system can be partitioned into (at most) n common independent sets (where as before, the second matroid is the natural transversal matroid).

Returning to the setup for Rota’s basis conjecture, we can write out the n² given vectors in a grid with the elements of B_i in row i (not worrying about whether the columns are bases) and draw a diagonal to split the bases into two disjoint triangular systems, one of size n and one of size n – 1. So we can partition the vectors into at most n + (n – 1) = 2n – 1 common independent sets, Q.E.D.

So the first question, which I don’t think has been looked at much and which hopefully should not be too hard, is:

Can we show that β ≤ 2n – 2?

Idea 2

In one of my papers I introduced the idea of looking for certain kinds of obstructions to an inductive proof of the conjecture. Specifically, suppose that instead of n bases, we are given n independent sets I₁, …, I_n, each of size k < n. Suppose further that these nk vectors (counted with multiplicity) can be partitioned into k bases somehow (but not necessarily bases that contain exactly one vector from each row). Then we can ask if there exists an n × k grid whose ith row comprises the elements of I_i and whose columns are all bases. In general, the answer will be no, but it is not so easy to come up with counterexamples. I came up with two counterexamples with k = 2, but I think it would be worth doing a computational search for more examples. Even k = 2 and n = 5 has not been checked, as far as I know. If there are not many counterexamples then there is some hope that we could classify them all, and I think that this would be a big step towards proving the full conjecture. Note: one family of counterexamples has been identified by Harvey, Kiraly, and Lau.

Idea 3

The last idea I want to present here is very vague. It is inspired by a paper by Ellenberg and Erman that I recently learned about. The result of the paper itself isn’t relevant, but I thought that the method might be. Roughly speaking, they reduce a certain combinatorial problem involving points and lines in a vector space to a “degenerate” case that is more tractable. Since various “degenerate” cases of Rota’s basis conjecture are known, perhaps the same idea could be applied to extend those degenerate cases to more cases.

As an example of a known degenerate case, let us first generalize Rota’s basis conjecture slightly as follows. Let us allow the vector space V to have some dimension d > n, and instead of n bases, let us take any n independent sets I₁, …, I_n, each of size n. Then we ask for the usual n × n grid except now we only require the columns to be independent and not necessarily bases. As far as I know, there is no known counterexample to this stronger conjecture. Moreover, this stronger conjecture is known to be true if we fix a single, standard basis B of V and insist that every I_i be a subset of B. Two proofs of this fact may be found in Section 2 of this paper.

Let me end this initial blog post here, with just one further comment that a couple of people that I have communicated with recently have some other concrete ideas that we can sink our teeth into immediately. I am going to invite them to explain those ideas in the comments to this blog post.

Comments (109)

109 Comments »

Congratulation, Tim, for launching polymath12. This is indeed a fascinating question. Let me refer everybody also to Tim’s answer to the polymath question where he proposed this polymath project http://mathoverflow.net/a/231153/1532 .
It contains additional useful information and, in particular, mentions the relation with Alon and Tarsi conjecture on even and odd Latin squares.

Comment by Gil Kalai — February 24, 2017 @ 5:45 am | Reply
This looks interesting! In the spirit of polymath projects where even tiny comments are allowed, and just to check my understanding, would you agree that the problem can be reformulated as : Show that for any $n\in \mathbb{N}*$ the following game has a winning strategy.

a) Pick any $n$ bases $B_1:=( b_{1,1},\cdots ,b_{1,n}),\cdots ,$ $B_n:=( b_{n,1},\cdots ,b_{n,n})$

b) Place them along the diagonal of an $n\times n$ grid : $\begin{matrix} B_1 & & & \\ & B_2 & &\\ & & \ddots & \\ & & & B_n\end{matrix}$

c) move sideways the elements of each $B_i$ to other cells so that only one element remains in each cell

d) now for each column of the grid gather all its $n$ vectors :

$\begin{matrix} b_{1,i_1} & \cdots & \cdots & b_{1,i_n}\\ b_{2,i_1} & \cdots & \cdots & b_{2,i_n}\\ \hdots & \hdots & \hdots & \hdots \\ b_{n,i_1} & \cdots & \cdots & b_{n,i_n}\\ \hline A_1:=(b_{1,i_1}, \cdots ,b_{n,i_1}) & \cdots & \cdots & A_n:= (b_{1,i_n}, \cdots ,b_{n,i_n}) \end{matrix}$

e) the game is won if all $n$ sets $A_1, \cdots , A_n$ are bases

Comment by Thomas Sauvaget — February 24, 2017 @ 8:22 am | Reply
- The indices I’ve used should be different of course, i.e. $i_1,\cdots ,i_n$ for the first row, then $j_1, \cdots ,j_n$ for the second, … So maybe it would be even cleaner to write as $A_1:=(b_{1,\sigma_1(1)}, \cdots ,b_{n,\sigma_1(n)}) , \cdots , A_n:= (b_{1,\sigma_n(1)}, \cdots ,b_{n,\sigma_n(n)})$ for some permutations $\sigma_1,\cdots , \sigma_n \in \mathfrak{S}_n$ . Sorry for these trivialities.
  
  Comment by Thomas Sauvaget — February 24, 2017 @ 10:04 am | Reply
- Yes, this is correct.
  
  Comment by tchow8 — February 24, 2017 @ 4:02 pm | Reply
Thanks for organizing this. I’m coming at this problem from the Alon-Tarsi Conjecture. In “Formulae for the Alon-Tarsi Conjecture” (http://dx.doi.org/10.1137/110797540), I stumbled upon a slick formula:

$L^{\text{\sc even}}_n-L^{\text{\sc odd}}_n=(-1)^{n(n-1)/2} \sum_{A \in B_n} (-1)^{\sigma_0(A)} \det(A)^n,$

where $B_n$ is the set of $n \times n$ $(0,1)$ -matrices and $\sigma_0(A)$ is the number of copies of $0$ in $A$ .

I used this formula to give another proof of the Alon-Tarsi Conjecture when n=p-1 and p is an odd prime [Glynn was first], showing that $L^{\text{\sc even}}_{p-1}-L^{\text{\sc odd}}_{p-1} \not\equiv 0 \pmod p$ .

In “How not to prove the Alon-Tarsi conjecture” with Wanless 2012 (http://projecteuclid.org/euclid.nmj/1330611000), we proved that $L^{\text{\sc even}}_n-L^{\text{\sc odd}}_n \equiv 0 \pmod m$ for most small $m$ , which is an obstacle to re-using this method to prove cases of the Alon-Tarsi Conjecture.

However, it does not exclude the case: $n=26$ (the smallest $n$ for which the Alon-Tarsi Conjecture is unproved) working modulo $p=53$ . I choose $p=53$ since powers of $26$ (such as $\det(A)^n$ in the above formula) are always congruent to $-1$ , $0$ , or $1$ modulo $53$ , which I’m hoping can be used to simplify the above sum.

This is where you guys chime in… and hopefully figure out how to simplify this equation (and hopefully identify a non-zero congruence modulo 53, thereby proving the n=26 case of the Alon-Tarsi Conjecture).

Comment by rebeccastones82 — February 24, 2017 @ 12:54 pm | Reply
- It seems I need to learn how to use math markup on this site… (?)
  
  Comment by rebeccastones82 — February 24, 2017 @ 1:00 pm | Reply
  - Dear Rebecca, thanks for the comment. to make a latex formula you need to put between the two dollar signs the word latex and then the formula. For example if I put between dollar signs latex \int_0^1 \Psi(x)dx you get $\int_0^1 \Psi(x)dx$
    
    Comment by Gil Kalai — February 24, 2017 @ 1:16 pm | Reply
- Can you please explain in more detail which $(n,p)$ pairs besides (26,53) are potentially amenable to this approach?
  
  Comment by tchow8 — February 26, 2017 @ 9:54 pm | Reply
  - Suppose we want to prove the Alon-Tarsi Conjecture for some even $n$ , i.e., we want to show $L_n^{\text{\sc even}} \neq L_n^{\text{\sc odd}}$ . A natural approach is to prove $L_n^{\text{\sc even}} \not\equiv L_n^{\text{\sc odd}} \pmod m$ for some $m$ . This approach has worked twice thus far:
    
    (a) Drisko proved $L_{p+1}^{\text{\sc even}} \not\equiv L_{p+1}^{\text{\sc odd}} \pmod {p^3}$ for odd prime $p$ .
    
    (b) Glynn proved $L_{p-1}^{\text{\sc even}} \not\equiv L_{p-1}^{\text{\sc odd}} \pmod p$ for odd prime $p$ .
    
    The problem is: given $n$ , what modulus $m$ should we choose? We might as well choose the modulus $m=p^k$ as a prime power (by the Chinese Remainder Theorem).
    
    In “How not to prove the Alon-Tarsi Conjecture”, we showed that for $t \leq n$ , we can only have $L_{n+1}^{\text{\sc even}} \not\equiv L_{n+1}^{\text{\sc odd}} \pmod {t^3}$ only if $t=n$ and $n$ is an odd prime (and Drisko’s congruence is this exception).
    
    The smallest unresolved case of the Alon-Tarsi Conjecture is $n=26$ , and in this case we have $L_{26}^{\text{\sc even}} \equiv L_{26}^{\text{\sc odd}} \pmod {2^{12} 3^6 5^6 7^3 11^3 13^3 19^3 23^3}$ . So we either work modulo $p^k$ where
    
    (a) $p < 26$ , in which case we need to choose $k$ so that $p^k$ is at least 2187,
    
    (b) $p > 26$ , where the above obstacle does not enter into things, which seems easier (it might not be; it’s a guess).
    
    So, which prime $p>26$ should we choose? If we choose the prime $29$ , then $\det(A)^{26}$ can take on the values $\{0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28\}$ modulo $29$ , which makes simplifying the formula for $L^{\text{\sc even}}_n-L^{\text{\sc odd}}_n$ problematic. If we choose the prime $p=53$ , then $\det(A)^{26}$ can take on the values $\{0, 1, -1\}$ modulo $53$ . In this case, we have the property that $a^{(p-1)/2} \pmod p$ is the Legendre symbol $\left(\frac{a}{p}\right)$ (using the $\left(\frac{0}{p}\right)=0$ version), so we have
    
    ———————————————————————
    $L^{\text{\sc even}}_{(p-1)/2}-L^{\text{\sc odd}}_{(p-1)/2} \equiv -\sum_{A \in B_{(p-1)/2}} (-1)^{\sigma_0(A)} \left(\frac{\det(A)}{p}\right) \pmod p$
    ———————————————————————
    
    for any odd prime $p$ .
    
    It’s possible that this formula might be able to be simplified through elementary number theory.
    
    Comment by rebeccastones82 — February 28, 2017 @ 9:13 am | Reply
    - Thanks! Is it possible for me to edit too? This line is wrong too (I think it was a copy/paste error), so it won’t make sense:
      
      “(a) $p>26$ , where the above obstacle does not enter into things, which seems easier (it might not be; it’s a guess).”
      
      It should say:
      
      “(a) $p26$ , where the above obstacle does not enter into things, which seems easier (it might not be; it’s a guess).”
      
      Comment by rebeccastones82 — February 28, 2017 @ 11:40 am | Reply
      - Hmm.. this is not displaying correctly either. Hopefully whoever reads the above can figure out what it should say. *shrugs*
        
        Comment by rebeccastones82 — February 28, 2017 @ 11:44 am | Reply
    - Thanks for this clear explanation. If I understand correctly, this line of thinking could potentially apply to any even $n$ such that $p = 2n+1$ is prime, so in particular we could take $n = 6$ and work mod $p = 13$ , or we could take $n = 8$ and work mod $p = 17$ . In both of these cases, we have the property that $\det(A)^n$ can only take on the values $\{0, 1, -1\}$ modulo $p$ . I mention this because even though the Alon-Tarsi conjecture is known for $n = 6$ and $n = 8$ , these values of $n$ are small enough that we may be able to get some intuition for what is going on by direct computation.
      
      For example, by using the table of values in Drisko’s 1998 Electronic J. Combin. paper, I find that $L_6^{\text{\sc even}} - L_6^{\text{\sc odd}} \equiv 6 \pmod{13}$ and $L_8^{\text{\sc even}} - L_8^{\text{\sc odd}} \equiv 7 \pmod{17}$ . In particular, these values aren’t zero, so that’s encouraging! The natural game to play now would be to try to find groups of matrices that cancel each other out modulo $p$ , and figure out what’s left over.
      
      Comment by tchow8 — March 2, 2017 @ 10:45 pm | Reply
    - Here is a calculation that I think would be worth doing. Let $\mathcal M$ denote the set of all $6 \times 6$ zero-one matrices that are nonsingular over $\mathbb{F}_{13}$ and whose rows are in lexicographical order. Compute, for all $i$ and $j$ , the number $n_{ij}$ of matrices $M\in \mathcal{M}$ with $i$ zero entries and determinant $j$ (modulo 13). Since $|\mathcal{M}| \le \binom{63}{6} = 67945521$ , this is not that large a computation. If we are lucky, there will be patterns in the number $n_{ij}$ that will suggest how to proceed.
      
      Comment by tchow8 — March 3, 2017 @ 2:57 am | Reply
      - (-9, 13): 90
        (-9, 14): 93
        (-9, 15): 180
        (-9, 17): 180
        (-9, 18): 196
        (-8, 11): 32
        (-8, 12): 5
        (-8, 13): 366
        (-8, 14): 1084
        (-8, 15): 1148
        (-8, 16): 2149
        (-8, 17): 1266
        (-8, 18): 450
        (-8, 19): 450
        (-8, 20): 45
        (-7, 9): 10
        (-7, 12): 558
        (-7, 13): 285
        (-7, 14): 724
        (-7, 15): 1632
        (-7, 16): 1542
        (-7, 17): 1890
        (-7, 18): 1554
        (-7, 19): 426
        (-7, 20): 360
        (-6, 10): 184
        (-6, 11): 424
        (-6, 12): 1204
        (-6, 13): 3104
        (-6, 14): 5972
        (-6, 15): 11782
        (-6, 16): 12088
        (-6, 17): 12580
        (-6, 18): 9684
        (-6, 19): 5572
        (-6, 20): 1684
        (-6, 21): 540
        (-5, 6): 1
        (-5, 10): 153
        (-5, 11): 1200
        (-5, 12): 1326
        (-5, 13): 5414
        (-5, 14): 7726
        (-5, 15): 10128
        (-5, 16): 16816
        (-5, 17): 16640
        (-5, 18): 13625
        (-5, 19): 8658
        (-5, 20): 4674
        (-5, 21): 1815
        (-5, 22): 273
        (-4, 7): 21
        (-4, 8): 64
        (-4, 9): 188
        (-4, 10): 126
        (-4, 11): 1670
        (-4, 12): 11181
        (-4, 13): 25356
        (-4, 14): 54138
        (-4, 15): 77482
        (-4, 16): 105567
        (-4, 17): 104552
        (-4, 18): 90642
        (-4, 19): 60144
        (-4, 20): 34611
        (-4, 21): 11516
        (-4, 22): 4126
        (-4, 23): 379
        (-4, 24): 5
        (-3, 8): 182
        (-3, 9): 1036
        (-3, 10): 4182
        (-3, 11): 10572
        (-3, 12): 20638
        (-3, 13): 44928
        (-3, 14): 76863
        (-3, 15): 131788
        (-3, 16): 144094
        (-3, 17): 180728
        (-3, 18): 159764
        (-3, 19): 140514
        (-3, 20): 80270
        (-3, 21): 49299
        (-3, 22): 16194
        (-3, 23): 5656
        (-3, 24): 740
        (-3, 25): 32
        (-2, 8): 90
        (-2, 9): 1646
        (-2, 10): 10496
        (-2, 11): 37438
        (-2, 12): 102936
        (-2, 13): 209846
        (-2, 14): 374660
        (-2, 15): 544082
        (-2, 16): 747820
        (-2, 17): 816110
        (-2, 18): 839808
        (-2, 19): 678376
        (-2, 20): 510184
        (-2, 21): 287478
        (-2, 22): 143424
        (-2, 23): 50400
        (-2, 24): 14306
        (-2, 25): 2528
        (-2, 26): 244
        (-2, 27): 10
        (-1, 5): 3
        (-1, 6): 60
        (-1, 7): 600
        (-1, 8): 3540
        (-1, 9): 14370
        (-1, 10): 42577
        (-1, 11): 109472
        (-1, 12): 230064
        (-1, 13): 443818
        (-1, 14): 716938
        (-1, 15): 1089688
        (-1, 16): 1418000
        (-1, 17): 1731826
        (-1, 18): 1775873
        (-1, 19): 1720842
        (-1, 20): 1388336
        (-1, 21): 1020259
        (-1, 22): 617177
        (-1, 23): 321024
        (-1, 24): 132574
        (-1, 25): 43636
        (-1, 26): 10808
        (-1, 27): 1940
        (-1, 28): 246
        (-1, 29): 21
        (-1, 30): 1
        (1, 5): 3
        (1, 6): 60
        (1, 7): 600
        (1, 8): 3540
        (1, 9): 14370
        (1, 10): 42293
        (1, 11): 109048
        (1, 12): 229296
        (1, 13): 442982
        (1, 14): 716702
        (1, 15): 1090112
        (1, 16): 1418680
        (1, 17): 1733834
        (1, 18): 1778197
        (1, 19): 1723158
        (1, 20): 1389964
        (1, 21): 1020811
        (1, 22): 616123
        (1, 23): 318936
        (1, 24): 130406
        (1, 25): 42116
        (1, 26): 10042
        (1, 27): 1660
        (1, 28): 174
        (1, 29): 9
        (2, 8): 90
        (2, 9): 1474
        (2, 10): 10216
        (2, 11): 36782
        (2, 12): 102384
        (2, 13): 209554
        (2, 14): 374500
        (2, 15): 544558
        (2, 16): 748940
        (2, 17): 817330
        (2, 18): 841432
        (2, 19): 679544
        (2, 20): 510800
        (2, 21): 287202
        (2, 22): 142896
        (2, 23): 49920
        (2, 24): 14074
        (2, 25): 2464
        (2, 26): 236
        (2, 27): 10
        (3, 8): 118
        (3, 9): 944
        (3, 10): 3978
        (3, 11): 10428
        (3, 12): 20462
        (3, 13): 44772
        (3, 14): 76947
        (3, 15): 131828
        (3, 16): 144686
        (3, 17): 181372
        (3, 18): 160216
        (3, 19): 140886
        (3, 20): 80122
        (3, 21): 49011
        (3, 22): 15861
        (3, 23): 5504
        (3, 24): 700
        (3, 25): 28
        (4, 7): 9
        (4, 8): 56
        (4, 9): 172
        (4, 10): 126
        (4, 11): 1630
        (4, 12): 10989
        (4, 13): 25164
        (4, 14): 54042
        (4, 15): 77554
        (4, 16): 105543
        (4, 17): 104848
        (4, 18): 90738
        (4, 19): 60036
        (4, 20): 34515
        (4, 21): 11404
        (4, 22): 4094
        (4, 23): 371
        (4, 24): 5
        (5, 10): 147
        (5, 11): 1152
        (5, 12): 1314
        (5, 13): 5386
        (5, 14): 7604
        (5, 15): 10152
        (5, 16): 16976
        (5, 17): 16540
        (5, 18): 13675
        (5, 19): 8622
        (5, 20): 4626
        (5, 21): 1791
        (5, 22): 267
        (6, 10): 176
        (6, 11): 416
        (6, 12): 1196
        (6, 13): 3016
        (6, 14): 5908
        (6, 15): 11738
        (6, 16): 12032
        (6, 17): 12620
        (6, 18): 9636
        (6, 19): 5588
        (6, 20): 1676
        (6, 21): 540
        (7, 9): 10
        (7, 12): 522
        (7, 13): 285
        (7, 14): 731
        (7, 15): 1608
        (7, 16): 1518
        (7, 17): 1890
        (7, 18): 1566
        (7, 19): 414
        (7, 20): 360
        (8, 11): 28
        (8, 12): 5
        (8, 13): 354
        (8, 14): 1076
        (8, 15): 1132
        (8, 16): 2141
        (8, 17): 1254
        (8, 18): 450
        (8, 19): 450
        (8, 20): 45
        (9, 13): 90
        (9, 14): 87
        (9, 15): 180
        (9, 17): 180
        (9, 18): 194
        
        Comment by Luke Pebody — March 3, 2017 @ 6:42 am | Reply
        
        Thanks for doing this! I decided to try to reproduce your calculation and got the same numbers (at least up to the sign of the determinant, which is controlled by one’s definition of “lexicographic order”). The first thing I notice is that the counts for (a,b) and (-a,b) and (a,36-b) and (-a,36-b) all tend to be close, but usually not exactly equal, to each other. It might be good to understand why this is the case, although unfortunately it would not help much with my cancellation idea because all these terms have the same sign.
        
        Another observation is that for a fixed determinant, if we arrange the counts by the number of zeros, we do not get a unimodal sequence in general. That is not encouraging for the idea of seeking cancellation between adjacent terms of the sequence. Still, the sequence seems to be “almost” unimodal except at the edges, so maybe this idea is not out of the question.
        
        Comment by tchow8 — March 5, 2017 @ 10:26 pm | Reply
- This formula identifies the difference as the top Fourier-Walsh coefficient of the function $det (A)$ (defined on $n^2$ Boolean variables.)
  
  UPDATE: I overlooked the exponent. Corrected version: This formula identifies the difference as the top Fourier-Walsh coefficient of the function $det (A)^n$ .
  
  Comment by Gil Kalai — February 27, 2017 @ 9:06 am | Reply
- Let $R_n^{\text{\sc even}}$ denote the number of even Latin squares with the first row and column in order, and $R_n^{\text{\sc odd}}$ denote the number of odd Latin squares with the first row and column in order. The values of $s[n] := R_n^{\text{\sc even}} - R_n^{\text{\sc odd}}$ are $1, 1, 1, 4, 24, 2304, 276480, 6210846720, 31302667468800$ when $n=1,\ldots,9$ . [Stones and Wanless (2012)]
  
  I just stumbled upon the surprising property: for $n \in \{2,4,6,8\}$ , this sequence has the property that $s[n+1] = (n-1)! s[n].$ What’s up with that?! I find it hard to believe this is just a small-case numerical coincidence, since when $n=9$ we have $s[9] = 31302667468800 = 6210846720 \cdot 7! = s[8] \cdot 7!$ which are some big numbers.
  
  In Stones and Wanless (2012), we conjectured $R_n^{\text{\sc even}} \neq R_n^{\text{\sc odd}}$ for all n. If the above observation is true for all even n, then the Alon-Tarsi Conjecture also implies our conjecture. I.e., the two conjectures are equivalent.
  
  Comment by rebeccastones82 — March 11, 2017 @ 12:10 pm | Reply
  - This is fascinating! In these small terms also $s(n)$ divides $s(n+1)$ for every $n$ . But I suppose we know from Glynn’s result that 13 that divides $s(8)$ does not divide $s(12)$ .
    
    Comment by Gil Kalai — March 11, 2017 @ 5:01 pm | Reply
  - Daniel Kotlar pointed out that this observation is true for even n>=2 is Theorem 3.3 in Aharoni and Loebl, “The odd case of Rota’s bases conjecture” (2015). http://dx.doi.org/10.1016/j.aim.2015.06.015
    
    Comment by rebeccastones82 — March 12, 2017 @ 8:03 am | Reply
- I think I managed to derive two formulas (I’m not sure if they will be of use):
  
  For $n \geq 2$ , we have $L_n^{\text{\sc even}} - L_n^{\text{\sc odd}} = n! \sum_{A \in B_{n-1,n}} (-1)^{\sigma_0(A)} \prod_{j \in [n]} \det(A^{\langle j \rangle})$ where $B_{n-1,n}$ is the set of $(n-1) \times n$ $(0,1)$ -matrices, $\sigma_0(A)$ is the number of $0$ ‘s in $A$ , and $A^{\langle j \rangle}$ is the matrix formed by deleting the $j$ -th column of $A$ .
  
  For $n \geq 3$ , we have $L_n^{\text{\sc even}} - L_n^{\text{\sc odd}} = n!\ (-1)^{n(n+1)/2} \sum_{A \in B_{n-1}} (-1)^{\sigma_0(A)+1} \det(A)\ \mathrm{per}(M)$ where $B_{n-1}$ is the set of $(n-1) \times (n-1)$ $(0,1)$ -matrices, $\sigma_0(A)$ is the number of $0$ ‘s in $A$ , and $M$ is the matrix of minors satisfying $M_{i,j}=\det(A|_{i,j})$ for all $i,j \in [n-1]$ .
  
  Since the proofs are cumbersome and my WordPress LaTeX skills are not great, I wrote up what I’ve done at Overleaf: https://www.overleaf.com/8425738kswcbnfsfzqw
  
  Comment by rebeccastones82 — March 12, 2017 @ 12:16 pm | Reply
The question after Idea 1 seems to easy. Just pick two elements in distinct rows that are independent and start the two triangles with them as the respective $I_1$ ‘s. Then merge the two $J_1$ ‘s at the end. Of course one could improve on this to get better bounds on $\beta$ .

Comment by domotorp — February 24, 2017 @ 2:37 pm | Reply
- OK, this was complete nonsense, I’ve completely misunderstood something and swapped $J_1$ and $J_n$ . If any of the two people who have upvoted my comment really see some solution, please let me know…
  
  Comment by domotorp — February 24, 2017 @ 7:58 pm | Reply
  - I was one of the upvoters but I now see that I made the same mistake that you did.
    
    Comment by tchow8 — February 24, 2017 @ 8:59 pm | Reply
  - Here is an idea.
    One corollary of our topological method is the following:
    If we find k disjoint base transversals, then we can cover the rest with 2n-2k independent transversals.
    So altogether we cover everything with 2n-k independent transversals.
    I am not sure, but I think it is known that 2 disjoint base transversals can always be found.
    
    Comment by Eli Berger — February 26, 2017 @ 12:51 am | Reply
    - It was proved by Geelen and Webb that one can find \sqrt(n) base transversals.
      
      Comment by ShiraZ — February 26, 2017 @ 8:53 pm | Reply
    - Sorry, but I don’t think this is true for k=n-1. It says if you have n-1 disjoint base traversals then the remaining elements can be covered by 2 independent transversal.
      
      Counterexample: B1=B2={e1, e2, e3} and B3={e1, e1+e2, e1+e3} and the two disjoint base traversals are (e2, e3, e1+e2) and (e3, e2, e1+e3). The remaining elements are all e1 and so need 3 independent transversals to cover them.
      
      Comment by Luke Pebody — February 27, 2017 @ 9:47 pm | Reply
      - Yes, it looks like you are right. The topological method does not give what I thought it would.
        
        Comment by Eli Berger — March 8, 2017 @ 7:28 pm | Reply
- So here is a (hopefully) correct solution that shows $\beta\le 2n-2$ . We start as proposed, with two triangles. We do the procedure to get all the $J_1,\ldots,J_n$ in one of them. Denote the only element of $J_n$ by $v_0$ . I claim that given any triangle $T$ with $i$ rows, of size $1,\ldots,i$ independent sets, we can select $i$ transversal independent sets from $T$ such that $v_0$ can be added to the size $1$ independent set, IF the only element of the row of $T$ that has size $1$ forms an independent set with $v_0$ . The statement of this claim is quite long (and probably shouldn’t be squeezed into one sentence), but its proof is trivial by induction. So how can we guarantee that the second triangle satisfies the IF condition with $v_0$ ? By carefully picking when creating $J_{n-1}$ in the first triangle (and using that $I_{n-1}$ is an independent set).
  
  Comment by domotorp — February 24, 2017 @ 10:11 pm | Reply
  - Just to clarify, above size $\atex 1$ independent set means the size $\atex 1$ transversal (and in fact transversals shouldn’t be called transversals, as they doesn’t intersect all the rows, I’m not sure what word would be appropriate).
    
    Comment by domotorp — February 24, 2017 @ 10:29 pm | Reply
  - I think this works, but the trivial part didn’t seem trivial to me so I want to spell it out here. Suppose the claim is true for $i-1$ , and let $T_1, \ldots, T_i$ be the rows of $T$ . The plan is to construct the first transversal $J_1$ , delete it, and apply the induction hypothesis to the resulting smaller triangular system. For this to work, we have to make sure that the unique remaining element $v \in T_2$ forms an independent set with $v_0$ . The only way things could go wrong is if $T_2$ contains an element $u$ parallel to $v_0$ and we fail to put $u$ in $J_1$ . However, when we are constructing $J_1$ , we are free to pick any element from $T_2$ as long as it forms an independent set with the unique element $v_1 \in T_1$ . But since $\{v_0, v_1\}$ is independent by hypothesis and $v_0$ is parallel to $u$ , it follows that $\{u, v_1\}$ is independent, so we can indeed arrange for $u$ to be in $J_1$ (the other element of $T_2$ cannot also be parallel to $v_0$ since $T_2$ is independent).
    
    Comment by tchow8 — February 25, 2017 @ 2:28 am | Reply
    - Yes, this is exactly what I had in mind.
      
      Comment by domotorp — February 25, 2017 @ 6:47 am | Reply
Tim, in your proposal on mathoverflow you say: “The problem feels to me like it falls into the category of problems that have too little structure for a purely deterministic construction but too much structure for a purely random construction. A number of difficult problems of this type have fallen in recent years so the time may be ripe for another such.” I would like to know what these problems are to get a better idea of what you mean by this category of problems. Maybe this will also suggest some general directions for Rota’s basis conjecture itself.

Comment by NG — February 24, 2017 @ 3:57 pm | Reply
- There’s a nice survey by Gowers in the most recent Bull. AMS on the construction of block designs on exactly this type of issue, the problems that fall between the probabilistic method and deterministic methods. He discusses the work of Keevash, which finds a large structured sub-solution, fills in much of the rest randomly, and then uses the structure of the first part to generate enough moves to fill in the holes left by the randomness. See http://www.ams.org/journals/bull/2017-54-01/S0273-0979-2016-01553-9/
  
  Comment by David Eppstein — February 24, 2017 @ 4:50 pm | Reply
- In addition to the Gowers paper mentioned by David Eppstein, which mentions not just Keevash’s work but also the “middle layers problem” (is the graph induced by the middle two layers of an odd-dimensional Boolean algebra Hamiltonian?), I recommend reading Danny Calegari’s comment on Gil Kalai’s blog on the same topic.
  
  There are a couple of reasons why I think that Rota’s basis conjecture might fall into this “intermediate” category. First, if you start playing around a little, then you get the feeling that for any given set of bases, there is not just one solution but a vast number of solutions. For example, if all the bases are equal, then we are just looking for Latin squares, and there are lots of these. Furthermore, intuitively it seems that having all the bases equal is the “worst case” as far as the number of solutions goes, because equal bases give rise to a lot of linear dependencies. I would expect that other sets of bases admit even more solutions. Given that there are a lot of solutions, it is tempting to try a random construction. However, a naive random construction will produce undesired linear dependencies with high probability. On the other hand, if one tries an explicit deterministic construction, one quickly branches into a lot of different cases, and it seems very difficult to control all the different cases that arise. Of course, perhaps the right insight will show how to control the different cases, but so far nobody seems to have had that insight.
  
  A second reason comes from the connection with the Alon-Tarsi conjecture. If you are not familiar with this connection, then I recommend Shmuel Onn’s Monthly article for an accessible exposition. Briefly, there is a polynomial identity with the general form “sum = coefficient*product” where the hypothesis of Rota’s basis conjecture implies that the product is nonzero and the desired conclusion of the conjecture is that one of the summands is nonzero. The Alon-Tarsi conjecture is that the coefficient is nonzero, and therefore it implies Rota’s basis conjecture. They key point is that the sum is huge (it is essentially a sum over all possible grids) and so this proof is “non-constructive” in the sense that it does not yield a polynomial time algorithm for finding which summand is nonzero, which is what we need in order to construct the desired grid. To me, this is a hint that it may not suffice to think purely in terms of an explicit polytime construction of the desired grid.
  
  By the way, the aforementioned polynomial identity is related to the Nullstellensatz, though it does not seem to arise in the way that the combinatorial Nullstellensatz typically arises in “non-constructive combinatorics” (but I would love it if someone proved me wrong on this point by connecting Rota’s basis conjecture with other combinatorial Nullstellensatz problems).
  
  Comment by tchow8 — February 24, 2017 @ 6:32 pm | Reply
A result of Edmonds [Theorem 1 of “Minimum partition of a matroid into independent subsets,”
Journal of Research of the National Bureau of Standards 69B (1965), 67–72] is the following:

Theorem 1. Let $n\ge1$ . A finite matroid $E$ with rank function $\rho$ can be partitioned into $n$ pairwise disjoint independent sets if and only if, for all subsets $F$ of $E$ ,
$|F|\le n\rho(F).$

This implies (Mirsky, Transversal Theory, Corollary 3.3.4):

Theorem 2. Let $m,n\ge1$ . Let $\mathcal{B}=(B_1,\ldots,B_m)$ be a family of subsets of a finite set $E$ . For $F\subseteq E$ , let $\rho(F)$ be the size of the largest partial transversal of $\mathcal{B}$ contained in $F$ .

Then $E$ can be partitioned into $n$ pairwise disjoint partial transversals if and only if, for all subsets $F$ of $E$ ,
$|F|\le n\rho(F).$

The natural “join” of Theorems 1 and 2 to partial independent transversals is known to be false (pp. 93–94 of de Sousa, “Disjoint common transversals,” in: D. J. A. Welsh (ed.), Combinatorial Mathematics and Its Applications: Proceedings of a Conference Held at the Mathematical Institute, Oxford, from 7–10 July, 1969, Academic Press,
London and New York, 1971, pp. 87–94). But we do have the following:

Proposition 3. Let $n\ge1$ . Let $V$ be an $n$ -dimensional vector space. Let $B_1,\dots, B_n$ be bases for $V$ that are pairwise disjoint. Let $E:=\cup_{i=1}^n B_i$ .

Then for all $F\subseteq E$ ,
$|F|\le n\rho(F),$
where $\rho(F)$ is the size of the largest linearly independent partial transversal of $\mathcal{B}=(B_1,\dots,B_n)$ that is a subset of $F$ .

This is in the groundbreaking, paradigm-shifting paper by Farley,* “A Problem Attributed to Rado from Mirsky’s 1971 Monograph Transversal Theory and a Conjecture from the 1982 Proceedings of the American Mathematical Society,” Math. Pannon. 24 (2013), no. 1, 3–14.

I am not suggesting that this is a sufficient condition, but it is worth exploring how far we can push this.

*This is an attempt at humor. I am a professional humorist: do not attempt this on your own!

Comment by Jonathan Farley — February 24, 2017 @ 4:10 pm | Reply
- What do you mean by “exploring how far we can push this”? Do you have a specific conjecture in mind that might be tractable and that might bring us closer to Rota’s basis conjecture?
  
  Comment by tchow8 — February 25, 2017 @ 3:22 am | Reply
[…] This is a quick post to draw attention to the fact that a new and very interesting looking polymath project has just started, led by Timothy Chow. He is running it over at the Polymath blog. […]

Pingback by Timothy Chow starts Polymath12 | Gowers's Weblog — February 24, 2017 @ 4:40 pm | Reply
Thanks for mentioning our paper!

A quick thought: 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.) This comment is probably not helpful for people who don’t already think about schemes but I wanted to put something down as a placeholder.

Comment by JSE — February 24, 2017 @ 6:39 pm | Reply
- I don’t know if this helps, but let me offer another restatement of the “degenerate” case that I described above. Let $S_1, \ldots, S_n$ be sets of integers, where each $S_i$ consists of $n$ distinct integers (but $S_i$ and $S_j$ may have nonempty intersection). Then there exists an $n\times n$ grid whose $i$ th row comprises the elements of $S_i$ (in some order) and whose columns all consist of distinct integers. This is a theorem.
  
  In fact something stronger is true (Dinitz’s conjecture/Galvin’s theorem). Given any $n^2$ sets $S_{ij}$ , each consisting of $n$ distinct integers, there exists a way of choosing some $v_{ij}\in S_{ij}$ such that $v_{ij} \ne v_{ij'}$ (for all $i$ and $j \ne j'$ ) and $v_{ij} \ne v_{i'j}$ (for all $j$ and $i \ne i'$ ). The previous paragraph is the special case where $S_{ij} = S_{ij'}$ for all $i, j, j'$ .
  
  Comment by tchow8 — February 24, 2017 @ 6:58 pm | Reply
  - Aha, great, I was trying to figure out what the statement was that was “finite sets in both directions.” What’s funny about the question at hand is that it’s “horizontally” about S_n and finite sets, and “vertically” about GL_n and finite-dimensional vector spaces.
    
    What’s the statement that’s about vector spaces both horizontally and vertically?
    
    Comment by JSE — February 25, 2017 @ 5:31 am | Reply
    - I suppose it would say: you have a collection V_1, … V_n of n-dimensional subspaces of k^N. Then the question is whether you can write down an n x n grid whose row i is a basis for V_i, and whose columns are independent sets of vectors. Is that always possible? (In the spirit of polymath I am asking this question without thinking about it.)
      
      Comment by JSE — February 25, 2017 @ 5:33 am | Reply
      - Nice question. I think that the following argument shows that the answer is yes. The key fact is that a vector space is never the union of of two proper subspaces (where a “subspace” must contain the origin; affine subspaces don’t count). I’m not sure I can cite a reference for this folklore fact but maybe someone else can. Anyway, given this, the idea is to construct the desired grid one column at a time, filling in each column one vector at a time from (say) the top to the bottom. If you’re at location $(i,j)$ then you just have to find some vector in $V_i$ that is not in the subspace $R$ spanned by the preceding $j-1$ vectors in row $i$ and also not in the subspace $C$ spanned by the preceding $i-1$ vectors in column $j$ . But the aforementioned “key fact” implies that there is always some vector in $V_i$ that is not in $R \cup (C \cap V_i)$ .
        
        Comment by tchow8 — February 26, 2017 @ 8:43 pm | Reply
[…] 12 is hosted by Timothy Chow and you can click here to follow the progress or to […]

Pingback by Polymath 12: Rota’s Basis Conjecture | The Matroid Union — February 25, 2017 @ 3:14 pm | Reply
Dear all, when I tried to write from memory the Rota basis conjecture (in my blog for advertising polymath12) I wrote the following more general version: if you have $n^2$ bases $B_{i,j} 1 \le i \le n,1\le j \le n$ of an $n$ -dimensional vector space then you can choose $b_ {ij} \in B_{i,j}$ such that for every $k,1 \le k\le n$ , the vectors $b_{ik}:1\le i \le n$ form a basis of $V$ and also the vectors $b_{kj}:1\le j \le n$ form a basis. This conjecture can be regarded as a strengthening of the Dinits Conjecture whose solution by Galvin is described in this post. Is this more general version known to be equivalent to the one stated here or perhaps known to be false?

Comment by Gil Kalai — February 25, 2017 @ 4:21 pm | Reply
- Gil – for proper acknowledgement of authorship: I know this (really nice) version of the conjecture as “(Jeff) Kahn’s conjecture” – though a quick search on the internet didn’t yield a reference. And no, the conjectures do not seem equivalent (though probably they are, in the sense of both being true).
  
  Comment by Ron Aharoni — February 25, 2017 @ 6:18 pm | Reply
  - Dear Ron, thanks! probably I heard it from Jeff. Does the Alon-Tarsi conjecture imply this stronger version as well? Also, does the Alon-Tarsi “polynomial” criterion for choosability also implies analogous “independent sets ” coloring?
    
    Comment by Gil Kalai — February 25, 2017 @ 6:55 pm | Reply
    - I doubt that the Alon-Tarsi conjecture impiles the stronger version, but we might be able to derive an analogous result for the “Kahn conjecture” as follows. The Kahn conjecture involves $n^3$ vectors; let $v_{ijk}$ denote the $k$ th candidate vector at position $(i,j)$ . Think of each $v_{ijk}$ as a vector of indeterminates $x_{ijkl}$ . For each $(i,j)$ , we can form an $n\times n$ matrix consisting of the indeterminates $x_{ijkl}$ with the given $(i,j)$ value; let $d_{ij}$ denote the determinant of this matrix, and let $D = \prod_{ij} d_{ij}$ . Now, for any way $W$ of selecting one vector per location $(i,j)$ , we can look at any row or column and form a matrix out of the selected vectors in that row or column and consider its determinant; let $P_W$ denote the product of these $2n$ determinants. We can now seek to express $D$ explicitly as some weighted combination of all the $P_W$ . By the Nullstellensatz, if the Kahn conjecture is true, then it must be possible to express *some power* of $D$ as some *polynomial* linear combination of the $P_W$ . The nice thing about Rota’s conjecture is that we don’t have raise (the analogue of) $D$ to any power; $D$ itself suffices, and we can take a *scalar* linear combination because the degrees are the same on both sides. Things aren’t going to be as simple for the Kahn conjecture because for starters the degree of $D$ is $n^3$ while the degree of $P_W$ is $2n^2$ , but maybe something can still be done. I’m not aware of anyone who has tried this.
      
      I don’t understand your second question so I can’t comment on it.
      
      Comment by tchow8 — February 26, 2017 @ 9:09 pm | Reply
  - It is Conjecture 6 of Huang and Rota, “On the relations of various conjectures on Latin squares and straightening coefficients,” Discrete Math. 128 (1994), no. 1-3, 225–236, although for some reason Professor Rota keeps saying the field is infinite. They attribute it to Jeff Kahn in 1991.
    
    Comment by Jonathan Farley — February 26, 2017 @ 2:36 am | Reply
The “graphic matroid” version of this question would be, I think: you have a set of n-1 trees T_1, .. T_{n-1} on n vertices. Can you order the edges of each tree in such a way that, for every i, the graph formed by e_i(T_1), .. e_i(T_{n-1}) is a tree?

Is this a known question? Do we think it’s true or not? Does the Aharoni-Berger theorem say something interesting in this case?

Comment by JSE — February 25, 2017 @ 11:26 pm | Reply
- This may be completely wrong, but doesn’t this tree question follow from the main question? If we associate with each edge $xy$ the linear combination $x+y$ with coefficients in $\mathbb F_2$ , then a set of edges is linearly independent if and only if it does not contain a cycle. Since all edges have coefficients that sum to zero, they live in an $(n-1)$ -dimensional space, so trees are precisely bases in this space.
  
  Comment by gowers — February 26, 2017 @ 12:19 am | Reply
  - Yes. Matroid theorists would say, “Graphic matroids are regular, meaning that they are representable over any field.”
    
    Comment by tchow8 — February 26, 2017 @ 9:47 pm | Reply
- Of course, if what I’ve written is correct, that doesn’t necessarily mean your question is uninteresting — it could be a very good case to consider of the main question.
  
  Comment by gowers — February 26, 2017 @ 12:20 am | Reply
- A tiny extra remark is that I didn’t need the scalars to be in $\mathbb F_2$ : indeed, the standard thing to do is associate with the edge $xy$ the vector $x-y$ (which is what we did in $\mathbb F_2$ , but it works in any field). It remains the case that these vectors form a basis of the space of functions that add up to zero if and only if the graph is a tree.
  
  Comment by gowers — February 26, 2017 @ 5:46 pm | Reply
  - I was actually wondering, regarding Tim G’s “extra remark”: do we expect the Rota conjecture to be true in characteristic 2? The paper of Stones and Wanless referred to above seems to say that the Alon-Tarsi constants are always even. But of course Rota might still hold.
    
    Comment by JSE — February 26, 2017 @ 6:30 pm | Reply
- Let me refine this a little bit. Another way to go is to consider a fixed graph G whose graphic matroid has rank n. (I am not a matroidologist so forgive me if I mess up the terminology.) For instance, G could be n disjoint edges on 2n vertices, or G could be K_{n+1}, or any other connected graph on n+1 vertices.
  
  Then we can ask: given B_1, … B_n a set of maximal independent sets (i.e. spanning forests of G), can you order the elements (i.e. edges) of each B_j such that, for every i, the set e_i(B_1), .. e_i(B_n) is a spanning forest? How many such ways are there?
  
  This might be a good way to “interpolate” between easy questions and harder ones. When G is n disjoint edges, then B_1, .. B_n are all the same thing and this is just a Latin squares problem, well-understood. When G is the complete graph on n+1 vertices, it’s the question I posted above. How dense does G have to get before the problem starts getting difficult? (Or does it ever get difficult?) Of course, as Tim Gowers says, these are all special cases of the Rota conjecture, but maybe they’re interesting special cases.
  
  Comment by JSE — February 26, 2017 @ 6:48 pm | Reply
  - I guess taking G a tree on n+1 vertices is the same as n disjoint edges on 2n distinct vertices, not sure why I made the distinction.
    
    Comment by JSE — February 26, 2017 @ 9:39 pm | Reply
- I expect Rota’s basis conjecture to be true for arbitrary matroids. No counterexample is known. Rota himself was only confident of its truth for vector spaces of even dimension, essentially because of the Alon-Tarsi connection, and the work of Bollen and Draisma on the online version of the conjecture gives further indication that the odd-dimensional case is different, but at the moment I think it make sense to conjecture it for arbitrary matroids.
  
  Graphic matroids or binary matroids would be interesting special cases. They are not known to be true. As far as I know, the only two interesting classes of matroids for which the conjecture is known are strongly base-orderable matroids (due to Wild) and paving matroids (due to Geelen and Humphries). Paving matroids are matroids whose circuits all have size $n$ or $n+1$ . I think it would be very interesting to attempt to extend this result to matroids whose circuits all have size at least $n-1$ . Strong base-orderability is a rather technical condition and it is a very special class of matroids; my personal perspective is that these are matroids with “no local obstructions” and my “Idea 2” can be thought of as doing a computational search for local obstructions.
  
  Comment by tchow8 — February 26, 2017 @ 9:21 pm | Reply
  - Suppose that $M_1$ and $M_2$ are matroids that both obey the basis conjecture. Is it known that their disjoint union also obeys the basis conjecture? (It’s very easy to find a binary matrix that describes which of $M_1$ and $M_2$ to choose from so that you get the right number of elements from each matroid in each row and column. Just choose rank($M_1$) diagonals to be 0’s and the rest 1’s. The harder part is choosing which elements of each matroid to use to replace the 0’s and 1’s.) This seems vagely related to the triangular system lemma in idea 1.
    
    Comment by David Eppstein — February 27, 2017 @ 1:50 am | Reply
    - Another nice question! I don’t know the answer, but it suggests that perhaps we should consider the following strengthening of the conjecture, which I’ll phrase in terms of vector spaces in case some readers are not comfortable with matroids. Suppose we are given $n$ bases $B_1, \ldots, B_n$ of a vector space of dimension $m \le n$ , and suppose we are given an $n\times n$ 0-1 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_i$ and such that the $m$ vectors in every column is a basis? Then I think the property of satisfying this conjecture is closed under disjoint union (a Hall’s marriage theorem argument shows that any 0-1 matrix of the stated form is the sum of $m$ permutation matrices).
      
      Comment by tchow8 — February 27, 2017 @ 2:07 am | Reply
[…] Timothy Chow of MIT has proposed a new Polymath project: resolve Rota’s basis conjecture. […]

Pingback by The 12th Polymath project has started: resolve Rota’s basis conjecture | The Aperiodical — February 26, 2017 @ 11:52 am | Reply
Related to Idea 3, suppose that we are given $n$ collections of $k$ vectors, $I_1,\ldots, I_n$ , in an $n$ -dimensional space. What are necessary and sufficient conditions that allow us to pick $k$ transversal bases? I expect this to be NP-hard already for constant $k$ , but some strong enough sufficient condition would be, well, sufficient. For example, it seems to me that in Rota’s original conjecture, no matter how we pick a first transversal basis, we can always extend it into a system of $n$ transversal bases. But what is the condition that we have to maintain when we pick the second basis?

Comment by domotorp — February 26, 2017 @ 12:09 pm | Reply
- I think you mean “Idea 2” rather than “Idea 3.” It is not true that you can pick the first transversal basis however you want. This is probably a good moment to introduce one of the basic counterexamples in the subject, namely $K_4$ , the complete graph on four vertices. This graph has six edges, which I wll call 12, 13, 14, 23, 24, and 34, in honor of their endvertices. As Tim Gowers explained above, you can associate a vector to each of these edges in such a way that a subset of the vectors is linearly independent if and only if the corresponding edges do not contain a cycle. So now consider the following 3 sets of 2 edges/vectors: {12,34}, {13,24}, {23,14}. It is easy to check that there is no way to pick 2 disjoint transversal bases. So if you have a 3×3 instance of Rota’s basis conjecture and you pick your first basis in such a way as to leave a copy of $K_4$ in this way, then you’re stuck.
  
  Comment by tchow8 — February 26, 2017 @ 9:42 pm | Reply
[…] Chow launched polymath12 devoted to the Rota Basis conjecture on the polymathblog. A classic paper on the subject is the 1989 paper by Rosa Huang and Gian […]

Pingback by Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News | Combinatorics and more — February 26, 2017 @ 2:54 pm | Reply
I remember that a certain combinatorial result of the form “given several bases of $\mathbb{F}_p^n$ , we may choose an element from each basis so that…” is proved in our paper with Roman Karasev (Israel Journal of Mathematics 2012) using some sophisticated algebraic topology. This part of a paper is entirely Roman’s, and I do not know how to do the same with polynomial tools.

We may try to modify the method.

Comment by Fedor Petrov — February 26, 2017 @ 9:48 pm | Reply
- This sounds very interesting. For the benefit of others let me restate your theorem here. Let $p$ be an odd prime, and let $V$ be the $\mathbb{F}_p$ -vector space of dimension $k$ . Denote $V^* = V\backslash\{0\}$ and put $m = |V^*|/2 = (p^k-1)/2$ . Suppose we are given $m$ linear bases of the vector space $V$
  
  $(v_{11}, \ldots, v_{1k}), (v_{21}, \ldots, v_{2k}), \ldots, (v_{m1}, \ldots, v_{mk}).$
  
  Then there exist pairwise distinct $x_1, \ldots, x_m$ , $y_1, \ldots, y_m \in V^*$ and a map $g:[m] \to [k]$ such that for every $i=1,\ldots, m$ we have $y_i - x_i = v_{ig(i)}$ .
  
  It is intriguing to me that topological methods are used in the proof since topology is also used by Aharoni-Berger.
  
  Comment by tchow8 — February 27, 2017 @ 3:53 pm | Reply
In “Ten Mathematics Problems I Will Never Solve,” Professor Rota refers to proofs by Marini for n=2,3,4,6,8. Can someone please post links to these proofs?

Comment by Anonymous — February 27, 2017 @ 7:28 am | Reply
- I didn’t leave my details. (I am new to this.)
  
  Comment by Jonathan Farley — February 27, 2017 @ 7:31 am | Reply
- I am pretty sure that Marini never published anything, and also that for n=4,6,8, it was just a computational verification of what we now call the Alon-Tarsi conjecture (and so, strictly speaking, was not a proof that worked over an arbitrary field). For n=2,3 it is not hard to put together a case-by-case proof.
  
  Comment by tchow8 — February 27, 2017 @ 3:43 pm | Reply
Regarding the case k=2 and n=5 in Idea 2, I have done a computer search for matroid counterexamples and I believe every case either has one of the two following forms (subject to rearrangement of individual pairs and the ordering of the pairs):

Case 1: Two pairs are (a1, a2), (b1, b2), there is some element from the other three pairs that forms a circuit with a1 and b1, and with a2 and b2 and there is some other element from the other three pairs that forms a circuit with a1 and b2 and with a2 and b1.

Example: (e1-e2,e3-e4), (e2-e3,e1-e4), (e1-e3,??), (e2-e4,??), (??,??)

Proof that there aren’t two disjoint independent transversals: If e1-e2 is paired with e2-e3 and e3-e4 with e1-e4 then neither independent transversal can contain e1-e3. If, on the other hand, e1-e2 is paired with e1-e4 and e2-e3 with e3-e4 then neither independent transversal can contain e2-e4.

Case 2: Three pairs are (a1, a2), (b1, x2), (x1, b2) (hopefully reason for bizarre labelling will be obvious), x1 and x2 form a circuit, there is some element from the other two pairs that forms a circuit with a1 and b1, and with a2 and b2 and there is some other element from the other two pairs that forms a circuit with a1 and b2 and with a2 and b1.

Example: (e1-e2,e3-e4), (e2-e3,x), (x,e1-e4), (e1-e3,??), (e2-e4,??)

Proof that there aren’t two disjoint independent transversals: Since e4 can’t be paired with e4, e1+e3 and e2+e3 must be in different transversals, so one is paired with e1 and one is paired with e2 and the argument follows as in Case 1.

—

So basically every counterexample I have found comes down to a K4.

It would seem a bit hasty to conjecture that every counterexample for k=2 is of the form (a1, x1), (x1, x2), (x2, x3), …, (x(n-1), xn), (xn, a2), (b1, y1), (y1, y2), …, (yn, b2), with some remaining elements c1 and c2 such that circuits are formed by a1,b1,c1, by a2,b2,c1, by a1,b2,c1 and by a2,b2,c1.

You mentioned that you found 2 examples for k=2 and Harvey, Kiraly and Lau found a family of counterexamples. Do they all fit this pattern?

Comment by Luke Pebody — February 28, 2017 @ 6:20 am | Reply
- The conjecture above was indeed hasty, as it is definitely not true: (a1, e1), (a2, e2), (e1+e2, e1-e2), (b1, e3), (b2, e4), (e3+e4, e3-e4), (c1, x), (c2, y).
  
  Clearly as in the previous examples, a1 and a2 need to be in different transversals, as do b1 and b2, so the argument above shows you can’t have two disjoint independent transversals.
  
  But, we could ask the question ‘Does every counterexample for k=2 contain 6 elements that form a K4 matroid?’
  
  Comment by Luke Pebody — February 28, 2017 @ 6:27 am | Reply
- Back pedalling entirely on this for now, as a second computer search has found some cases the first computer search missed. I must have made some unnecessary assumptions the first time around.
  
  Comment by Luke Pebody — February 28, 2017 @ 8:48 am | Reply
- The k=2, n=4 example that I found is a matroid called J in Oxley’s book on Matroid Theory. In Euclidean 4-space we may for example take I1 = {(-2,3,0,1), (0,0,1,1)}, I2 = {(0,2,0,1), (1,0,3,1)}, I3 = {(1,0,0,1), (0,1,2,1)}, I4 = {(0,1,0,1), (4,0,0,1)}. Note that J is not representable over the field with two elements.
  
  The Harvey-Kiraly-Lau counterexamples for larger k are based on a class of graphs mentioned in my paper. A “wheel” is a cycle (the “rim”) together with another vertex (the “center”) that is adjacent to every vertex on the cycle; the edges coming off the center are called “spokes.” Now create multiple copies (parallel edges) of each spoke. This doesn’t immediately yield a counterexample for larger k (some additional work is needed, and I think it is best if I refer you to the Harvey-Kiraly-Lau paper at this point) but wheels with multiple spokes are the fundamental combinatorial object underlying the counterexamples.
  
  Comment by tchow8 — February 28, 2017 @ 7:25 pm | Reply
A note that for matroids, and (I think) over infinite fields, the generalization of the Basis Conjecture you mention in Item 3 is equivalent to the Basis Conjecture.

For matroids, just take your matroid and throw away all independent sets of size greater than n.

Over infinite fields (I think) no vector space of dimension >=2 is the union of finitely many strict subspaces. As such, while the dimension is greater than n, the subspaces generated by I_1, I_2, …, I_n will be strict subspaces, and so there is a vector v that is not in any of those subspaces. Then if you form a basis containing v, and then remove the v coordinate, each of the sets I_j will still be independent, and any subset of the points that is independent afterwards would have been independent before.

Comment by Luke Pebody — February 28, 2017 @ 6:47 am | Reply
The starting point of Alon-Tarsi’s theorem is the coloring polynomial of a graph $G$ with vertex set $\{1,2,\dots,n\}$ , $f_G(x_1,x_2,\dots,x_n)=\prod\{(x_i-x_j):i<j,\{i,j\}\in E(G)\}$ and connections with coloring and choosability.
Is there something similar that we can say if we consider the polynomial $f_G(x_1,x_2,\dots,x_n)=\prod\{(x_i-\lambda_e\cdot x_j):i<j,\{i,j\}=e\in E(G)\}$ .where the lambdas are weights associated to the edges. More broadly, perhaps we can replace the polynomials we use by a larger class of polynomials?

Comment by Gil Kalai — February 28, 2017 @ 10:14 am | Reply
Here is an angle from which I like to view Rota’s conjecture: the uncannily nice behavior of the intersection of two matroids.

This has at least three aspects. To discuss them I need some notation: $\beta(H)$ , where $H$ is any hypergraph, is the minimal number of edges needed to cover $V(H)$ (sometimes the notation $\rho(H)$ is used for that, but this is a bit confusing when matroids are discussed, where $\rho$ usually denotes rank).

I. covering number. There is a conjecture of Eli Berger and myself, that if $M, N$ are two matroids on the same ground set, then $\beta(M, N) \le \max(\beta(M), \beta(N)+1$ . That is, the intersection behaves almost as nicely as the worse of the two matroids. Konig’s edge coloring theorem yields the case of partition matroids, even without the $+1$ . The conjecture has been around for a while, and as yet there is no counterexample. $\beta(M, N) \le 2\max(\beta(M),\beta(N)$ follows using topological methods. The conjecture is known when $\beta(M), \beta(N) \le 2$ .

In the Rota context, this means that even if you take your bases and scramble them – so you no longer have bases, but a collection of n sets of size n, whose union is decomposable into n independent sets, you can cover their union by $n+1$ rainbow independent sets. There are examples showing that $n+1$ are indeed required in this general case.

II. Fair representation. Given a partition $(A_1, \ldots, A_m)$ of a set $V$ , a subset $S$ of $V$ represents the partition {\em $\alpha$ -fairly} if $|S \cap A_i| \ge \lfloor \alpha |A_i|\rfloor$ for all $i \le m$ , and {\em almost $\alpha$ -fairly} if $|S \cap A_i| \ge \lfloor \alpha |A_i|\rfloor -1$ for all $i \le m$ .
For every partition, a single matroid $M$ contains an independent set that represents the partition $\frac{1}{\beta(M)}$ -fairly.
A (very bold, I must admit) conjecture is that this is true (well, again almost true) for the intersection of two matroids. Namey, if $M,N$ are matroids on the same ground set, then any partition can be represented by an edge of $M \cap N$ almost $\frac{1}{\max(\beta(M),\beta(N))}$ -fairly.
This is known (even in a slightly stronger form) for partition matroids with parts of size $2$ – and even this rudimentary case is hard, the proof uses topology. It is known (with a slight weakening) for partitions into two sets.

III. Rainbow matching: another conjecture of Eli Berger and myself is that given $n$ sets of size $n+1$ each, all belonging to the intersection $M \cap N$ of two matroids $M$ and $N$ , then there exists a rainbow set belonging to $M \cap N$ (a rainbow set chooses one element from each of the sets). The special case of $M,N$ being partition matroids (and then $M \cap N$ is the matching complex of a bipartite graph) has been studied extensively, with many partial results.

Perhaps some of all this is too daring (in particular, I will not be surprised if II is given a simple counterexample – I haven’t really thought about it for too long). But the phenomenon is intriguing. In particular – is there any connection between these phenomena? Note that in all of them there is a price of $1$ for going from one matroid to the intersection of two matroids. This is reminiscent of Vizing’s theorem, and of the famous Goldberg-Seymour conjecture (and indeed, there is a common generalization of the latter and “I” above).

Comment by רון אהרוני — February 28, 2017 @ 11:59 am | Reply
- Thank you for this enlightening summary. I have a couple of questions about part I. For Rota’s basis conjecture, you say you can prove $\beta \le 2n$ by topological methods, but conjecture that $\beta \le n+1$ for very general reasons. Why do your current methods fail to do better than $\beta \le 2n$ ? Is it because the topological concepts that you are using (connectivity being the main one that I am aware of) are intrinsically too weak to yield a better bound? Or is it that you conjecture that the true values of certain topological invariants are big/small enough to imply $\beta \le n+1$ , but you are unable to prove that the topological invariants attain the conjectured values?
  
  Also, Luke Pebody seems to have given a counterexample to a claim that Eli Berger made above, inside comment #4. Can you comment on that? Does the claim need to be corrected or are we misunderstanding the claim?
  
  Comment by tchow8 — February 28, 2017 @ 9:36 pm | Reply
- Ron Aharoni (=רון אהרוני) is giving a lecture about this fascinating topic in Tel Aviv 11 hours from now http://www.math.tau.ac.il/~pelegm/fubtau2017/index.html.
  
  Comment by Gil Kalai — March 4, 2017 @ 9:09 pm | Reply
[…] Polymath 12关注的依旧是一个组合问题：Rota基猜想。和许多组合猜想一样，它的叙述非常、非常简单，只用到一点点的线性代数。通常我对组合问题的兴趣不大，不过也有例外。早在月旦 I中我们就曾提到，拟阵（matroid）这一概念虽然是组合的，却也容许一个代数几何诠释。近两年颇为热门的「组合（代数）几何」将复代数几何中的正定性定理、Lefschetz-Hodge理论等工具类比地应用于此类组合问题的研究，取得了不少成果。例如，组合几何版的强Lefschetz定理和Hodge-Riemann关系可以用来证明Rota的另一个关于拟阵的猜想： Adiprasito, Huh, Katz Hodge Theory for Combinatorial Geometries 我相信用类似的思路可以解决Rota基猜想。或者说只有这种解答才是「有趣」的。 […]

Pingback by 月旦 XII | Fight with Infinity — February 28, 2017 @ 1:32 pm | Reply
Am I understanding the problem correctly?

We are working in real numbers,
we have a cube of numbers, in depth (front to back) we have representation of a basis vector. Row (left to right) represents basis, meaning every 2D matrix obtained by slicing specific row in depth is a full rank. different basis are stacked vertically (top to bottom). The conjecture states that moving columns, going in depth direction, to left or right we can always obtain a full rank matrix when slicing the cub vertically and in depth (left-most 2D slice is a full rank matrix).

Is this is equivalent?

Comment by mkatkov — February 28, 2017 @ 10:52 pm | Reply
- Yes, that is correct. It does not have to be real numbers; the conjecture is that it is true for an arbitrary field. However, it would extremely interesting to prove the conjecture for the reals or for any particular field.
  
  Comment by tchow8 — March 1, 2017 @ 12:16 am | Reply
Just throwing out an idea: a stronger reformulation of this $n \times n$ grid might be as a set of $n$ endomorphisms $\sigma_i \in End(V)$ , such that each endomorphism is an isomorphism, and (using $\sigma^n$ to represent applying $\sigma$ n times) such that each $\mathcal{B}_v := \{\sigma^k_i (v) | 0 \leq k \geq n \}$ is a basis for every $v \in B_1$ . So, the question then becomes proving a statement of there being the desired elements in the endomorphism group. My thought is that if we can find a suitable group $G$ for which there exists a representation of $G$ by $V$ , then there might be some element of $G$ which “factor into” $n$ elements which correspond to the transformation desired. I’m not sure under what hypothesis these sorts of things happen, though…

Comment by Juan Sebastian Lozano — March 1, 2017 @ 5:35 am | Reply
- Typo: I meant $\mathcal{B}_V := \{ \sigma^k_i | 0 \leq k \leq n \}$
  
  Comment by Juan Sebastian Lozano — March 1, 2017 @ 5:41 am | Reply
- This is the wrong notion, the correct notion would be letting $\sigma^n = \sigma_n \circ \cdots \circ \sigma_1$ , and then letting $\mathcal{B}_v := \{ \sigma^k(v) | 0 \leq k \leq n \}$ .
  
  Comment by Juan Sebastian Lozano — March 1, 2017 @ 5:55 am | Reply
- Okay, here is what I think is an equivalent formulation:
  
  Prop: Rota’s conjecture is true if and only if there exists a group $G$ such that $V$ is a representation of $G$ and there exists $g_i \in G$ such that $g_i \cdot \mathcal{B}_i = \mathcal{B}_{i+1}$ , and for every vector $b \in \mathcal{B}_1,$ $ $span\{g^0 b,\dots, g^{n-1} b\} = V$ $ where $g^i = g_i \dots g_1$ and $g^0$ is the identity.
  
  Proof: ( $\Leftarrow$ ) The grid will be $b_1, \cdots, b_n \\ g_1 b_1, \cdots, g_1 b_n \\ \vdots, \ \ \ ,\vdots \\ g^{n-1} b_1, \cdots, g^{n-1} b_n$
  
  ( $\Rightarrow$ ) Let $G = GL(V)$ . Let $\rho \in S_n$ , then $a_1: b_1 \mapsto b'_{\rho(1)}$ , where $b' \in \mathcal{B}_2$ , for every $0 \leq i \leq n$ , extended linearly. Specifically, we take $b'_{\rho(1)}$ to be the member of $\mathcal{B}_2$ directly below $b_1$ in the grid we know exits according to Rota’s conjecture. Repeating this process for each pair $\mathcal{B}_i , \mathcal{B}_{i+1}$ we get a set of members of $G$ , specifically $a_1, \dots , a_{n-1}$ . Now, letting $a_0$ be the identity, we define $g_i = a_i(a_{i-1})^{-1}$ , which we see means that $g^n = a_n$ , as desired.
  
  Thanks to Ofir for helping me with formulating this idea: http://math.stackexchange.com/questions/2166516/representations-of-a-group-with-a-set-linearly-independent-factors/2166603#2166603
  
  Comment by Juan Sebastian Lozano — March 1, 2017 @ 2:45 pm | Reply
[…] a completely separate note, here is a new Polymath project that seeks to prove a problem in linear algebra. This is accessible to first-year undergraduates, […]

Pingback by Groups and Group Actions: Lecture 5 | Theorem of the week — March 1, 2017 @ 11:04 am | Reply
Regarding Stone’s formula:

$L^{\text{\sc even}}_n-L^{\text{\sc odd}}_n=(-1)^{n(n-1)/2} \sum_{A \in B_n} (-1)^{\sigma_0(A)} \det(A)^n,$ where $B_n$ is the set of $n \times n$ $(0,1)$ -matrices and $\sigma_0(A)$ is the number of copies of $0$ s in $A$ .

Is there hope to find nice closed formulas (or good asymptotics) for expressions of the form $\sum_{A \in B_n} (-1)^{\sigma_0(A)} \det(A)^k,$ where $k$ is small bounded number? especially $k=2$ and $k=1$ (maybe $k=4$ ?

Comment by Gil Kalai — March 2, 2017 @ 7:10 pm | Reply
- I think if k is less than n this sum is 0. Express det(A) in the standard way as a sum of multiples of elements of A and fully expand det(A) ^k. Each term omits some element Aij and so changing the value of that element will keep the term the same and negate the multiplier.
  
  Comment by Luke Pebody — March 2, 2017 @ 8:03 pm | Reply
  - Since, I think, for every integer p less than n there exists k less than n such that x^n-x^k is always divisible by p, it follows that the Alon-Tarsi difference is divisible by all integers less than n.
    
    Comment by Luke Pebody — March 2, 2017 @ 8:10 pm | Reply
  - I don’t understand this argument. Suppose for example that k=1. Then det(A) is a sum of n! “monomials” in the Aij, and certainly each individual monomial omits some (in fact, all but n) Aij. But what is “that element” whose value you are changing? Each monomial omits different Aij, and collectively they cover all Aij, so there is no Aij that works uniformly for all monomials. Are you trying to pick a different Aij for each monomial? But then, for each A, you’re pairing it off with n! different matrices, and it’s not obvious to me how to ensure that you’re covering all (matrix,monomial) pairs exactly once.
    
    Comment by tchow8 — March 3, 2017 @ 3:18 am | Reply
    - $\Sigma_{A\in B_n}(-1)^{\Sigma_{i,j}1-A_{i,j}}\mathrm{det}(A)^1$
      is $\Sigma_{A\in B_n}(-1)^{\Sigma_{i,j}1-A_{i,j}}\Sigma_{\sigma\in S_n}(-1)^{\mathrm{sgn}(\sigma)}\Pi_{i=1}^nA_{i,\sigma(i)}$ ,
      which is $\Sigma_{\sigma\in S_n}(-1)^{\mathrm{sgn}(\sigma)}\Sigma_{A\in B_n}(-1)^{\Sigma_{i,j}1-A_{i,j}}\Pi_{i=1}^nA_{i,\sigma(i)}$ .
      
      Now my claim is that for each individual $\sigma$ in $S_n$ , this inner sum $\Sigma_{A\in B_n}(-1)^{\Sigma_{i,j}1-A_{i,j}}\Pi_{i=1}^nA_{i,\sigma(i)}$ is zero.
      For this specific $\sigma$ , choose an $A_{i,j}$ for which $\sigma i\ne j$ . Then if you change the value of $\sigma A_{i,j}$ , you negate the value of
      $(-1)^{\Sigma_{i,j}1-A_{i,j}}$ without changing the value of $\Pi_{i=1}^nA_{i,\sigma(i)}$ .
      
      For the more general case of $k<n$ , for each monomial (seen as a function from the elements of A to the integers), you pick an unneeded element $A_{i,j}$ and pair up the matrices that differ only in that $A_{i,j}$ . For this monomial and for each such pair, the product of $(-1)^{\sigma_0(A)}$ and the monomial sum to 0. Therefore,
      for this monomial and for all matrices, the sum of the product of $(-1)^{\sigma_0(A)}$ and the monomial is 0.
      
      Thus the sum over all monomials of the sum over all matrices of this product is 0.
      
      Comment by Luke Pebody — March 3, 2017 @ 3:54 am | Reply
  - Can we say something about the quantities $S(n,r,k)=\sum\{ \det(A)^k:A \in B_n,\sigma_0(A)=r\}$ when $r$ is an integer $1 \le r \le n^2$ (and $k \le n$ )?
    In particular, when $n>1, k$ are odd is $S(n,r,k)=0$ ? And does the negation of Alon Tarski’s conjecture for some even $n$ implies that for every $r$ , and odd $k$ already $S(n,r,k)=0$ ?
    
    Comment by Gil Kalai — March 3, 2017 @ 6:49 am | Reply
    - When k is odd, S(n, r, k)=0 since swapping the first two rows negates $\mathrm{det}(A)^k.$
      
      When k is even, S(n, r, k) is the sum of non-negative stuff, so is 0 only when all 0,1 n x n matrices with r 0’s have determinant 0. Probably when r is small or large.
      
      Comment by Luke Pebody — March 3, 2017 @ 7:30 am | Reply
- Note that since $(-1)^{n(n-1)/2}\Sigma_{A\in B_n}(-1)^{\sigma_0(A)}\mathrm{det}(A)^k$ is 0 for all odd $k$ and for all $k<n$ , we can replace $\mathrm{det}(A)^k$ with any degree k+1 polynomial of $\mathrm{det}(A)$ with a non-zero $\mathrm{det}(A)$ coefficient, if it helps.
  
  Comment by Luke Pebody — March 4, 2017 @ 8:06 am | Reply
Several comments related to Rebecca Stones’ formula $L^{\text{\sc even}}_n-L^{\text{\sc odd}}_n=(-1)^{n(n-1)/2} \sum_{A \in B_n} (-1)^{\sigma_0(A)} \det(A)^n,$

The formula identifies the difference as the top Fourier-Walsh coefficient of the function $det(A)^n$ . Since $det(A)^k$ is a polynomial of degree $kn$ it indeed seems to follow that the top Fourier-Walsh coefficients is o when $k<n$ . Acrually this works also when you replace $det(A)^k$ with $per(A)^k$ . When $k=n$ you can compute the top Fourier-Walsh coefficient by adding the contributions of each monomial. Eaxh monomial for $det(A)^n$ corresponds to a generalized diagonal define by a certain permutation. The only monomials that matters are those that involve all the variables and therefore those where the $n$ permutations involved form a Latin square. (If I am not mistaken the contribution is the product of signs of the $n$ permutations and I presume (but did not check) that it will give back Rebecca's formula. (Maybe it shows that the corresponding alternating sum for $per(A)^n$ is non zero but perhaps I missed some signs.)

The second comment is that we have here a question about random Boolean matrices. We would like to understand the behavior of $S(n,r,k)=\sum\{ \det(A)^k:A \in B_n,\sigma_0(A)=r\}$ when $k$ is even and especially when $k=n$ . The obvious conjecture is that the middle term ( $r=n^2/2$ ) dominates the alternating sum. Maybe it is even true (at least for a large $n$ ) that the middle term is larger than the sum of all other terms (without the alternating sum).
It would be interesting to guess (even based on a heuristic argument) of the distribution of $det^n(A)$ behaves for matrices with $\sigma_0(A)=r$ .

The last remark is that perhaps analogs of these questions for random Gaussian matrices are easier (and perhaps even useful). E.g. if we want to understand the spherical harmonics expansion of $det(A)^n$ when $A$ is a Gaussian $n$ by n matrix.

Comment by Gil Kalai — March 4, 2017 @ 5:05 pm | Reply
- To expand on the last sentence the situation is as follows. We consider a Gaussian random $n \times n$ matrix, and the function $f=det(A)^n$ . We can describe this function via the Hermite transform.
  
  Let $h_j(x)$ be the normalized Hermite polynomial of degree $j$ . For $d=(d_1,\ldots,d_m)$ we can define a multivariate Hermite polynomial $h_d(X)=\prod_{i=1}^m h_{d_i}(x_i)$ , and the set of such polynomials is an orthonormal basis for $L_2(\mathbb R^m)$ . We can consider the expansion of $f$ in terms of Hermite polynomials $f(x) = \sum _{\beta \in \mathbb N^m}\hat f(\beta ) \prod_{i=1}^m h_{\beta_i}(x_i).$ ( $m=n^2$ .)
  
  The values $\hat f(\beta )$ are called the Hermite coefficients of $f$ . The Gaussian analog to Alon-Tarsi’s conjecture is that the Hermite coefficients that correspond to positive vectors of integers are not all zero. (Equivalently, (I think) that the coefficient corresponding to the all 1 vector is non zero.)
  
  Gaussian random matrices are usually much easier than random Bernoulli (0-1) matrices so maybe the Hermite expansion can be computed precisely. A longer shot would be to try to reduce the Bernoulli case to the Gaussian case via some sort of averaging.
  
  Comment by Gil Kalai — March 4, 2017 @ 9:02 pm | Reply
- If we are considering different ways to think about the Alon–Tarsi number, then I think that it is worth studying Theorem 1.9 of Kumar and Landsberg, which gives several reformulations, notably some in terms of an integral over the special unitary group.
  
  Comment by tchow8 — March 5, 2017 @ 10:08 pm | Reply
- Yes, indeed there is some similarity with Kumar and Landsberg’s analytical equivalent formulations of the Alon-Tarsi conjecture.
  
  Again, here is my conjecture:
  
  Let $f=det(A)^n$ , ( $n$ even) then The Hermite coefficient $\hat f(\beta )$ for $\beta={\bf 1}$ is non zero. ( $\beta={\bf 1}$ is the all one vector.)
  
  Perhaps it would be possible to move between this conjecture and Stones’s Walsh-Fourier formulation of Alon-Tarsi by replacing one by one Boolean rows with Gaussian rows. (But I am not sure at all). Usually Gaussian random matrices are easier compared to Boolean matrices, e.g. we know the joint distribution of eigenvalues (and $f$ is the $n$ th power of their product).
  
  Comment by Gil Kalai — March 6, 2017 @ 6:25 am | Reply
It’s clear we can write down nxn arrays of vectors which “fail Rota” if we drop the hypothesis that each row of the array forms a basis of V; for instance, we could take one of the vectors to be 0. On the other hand, the condition that each row forms a basis is perhaps too strong; e.g. if each row B_i consists of nonzero multiples of a single vector v_i, and the v_1, … v_n are all independent, then the columns form a basis automatically. What is the “right” linear-algebraic/combinatorial condition on the n bases?

Comment by JSE — March 5, 2017 @ 5:32 pm | Reply
- Conjecture: For ever $k$ , every $k$ -dimensional subspace contains at most $kn$ of the $n^2$ vectors. If true, this would mean that it doesn’t matter how the vectors are arranged. This condition is obviously necessary and for $n\le 2$ also sufficient.
  
  Comment by domotorp — March 5, 2017 @ 9:01 pm | Reply
  - This line of thinking is the background behind my “Idea 2.” I believe that Colin McDiarmid’s counterexample works for your conjecture too. Let’s take $K_4$ again but create two copies of the spokes, so the edges are $12,13,14,23,24,34,14',24',34'$ . Then take the rows to be $\{14,14',23\}$ , $\{24,24',13\}$ , and $\{34,34',12\}$ . This nine-element matroid is the disjoint union of three bases but you can’t get the columns to all be bases if you are limited to permuting within a row.
    
    Comment by tchow8 — March 5, 2017 @ 9:59 pm | Reply
    - Right…
      
      Comment by domotorp — March 6, 2017 @ 5:05 am | Reply
Hi all, This is my first post here on RBC and I have been looking up my old work on this which slightly extend my published paper in that SIAM Journal solving the case of n = prime – 1 for characteristics that do not divide n! or n_e-n_0 (number of (reduced) Latin squares of even or odd types respectively). Now I have seen in my notes that it actually also proves, using Cayley’s first hyperdeterminant (I call it det_0) of n^n hypercubes, another result that takes the permanents of the transversals instead of the determinants, but possibly more in a later post.
It has been mentioned that RBC for fields of characteristic two is not solved in many cases yet.

Here is some relation I have with G-C Rota. It was he (and a few others) who first introduced me to matroid theory by giving lectures on it at a conference at Villa Monastero, Lake Como, Northern Italy (early 1980’s). At the time matroid theory was very little known and practised by a few diverse and eccentric people in far out places such as Tasmania and maybe New Zealand (although started by H. Whitney and then W.T. Tutte). Actually Rota was born very close to there in NW Italy. I happen to know that his favourite wine was Asti spumante, which is a speciality of that region in Piemonte, a light and sparkly white wine. He died in 1999 at a young age, but here is a obit from an Italian source that I happen to have translated. It doesn’t mentioned the sometimes controversial books (e.g. Indiscrete Thoughts) and book reviews (in journals that he founded). But here it is:

From the Notices of the Unione Matematica Italiana
(Italian Mathematical Society)

The Death of Prof. Gian-Carlo-Rota

Gian-Carlo-Rota died at the age of 67 years in his house at
Cambridge (Massachussetts). He was the unique lecturer of the
Massachussetts Institute of Technology (MIT) who was Prof. of
Applied Mathematics and also of Philosophy.

He graduated at the University of Princeton and was awarded the
doctorate at Yale under the guidance of Jacob T. Schwartz.
From 1966 up to his death he was a consultant for the Los
Alamos Scientific Laboratory. He was given the title of
Doctor Honoris Causa by the University of Strassburg, France,
in 1984, by the University of Bologna, Italy (1996), and by
Brooklyn Polytechnical University, USA (1997). In 1982 he
was elected member of the National Academy of Sciences and from
1995 to 1997 was vice-president of the American Mathematical
Society (AMS). In 1998 he was “invited presenter” at the
American Mathematical Society Colloquium Lectures: a series of
three talks of increasing complexity presented each year by
more eminent mathematicians in the world. In 1998 he was given
the title of Wiener Professor by MIT.

His research was initially in the direction of operator theory,
differential equations and probability. In the sixties his
interests redirected towards combinatorics and in 1964 he published
“On the Foundations of Combinatorial Theory I: Theory of Moebius
Functions” for which in 1988 he received the prestigious
Steele Prize of the AMS. He was founder of three of the more
prestigious mathematical publications: Journal of Combinatorial
Theory (1966), Advances in Mathematics (1967) and Advances in
Applied Mathematics (1979) and of various series of books such
as Mathematicians of our Time (MIT Press), Contemporary Mathematicians
(Birkhauser Boston) and Encyclopedia of Mathematics (Cambridge
University Press).

Gian-Carlo-Rota is universally held to be the person behind the
transformation of discrete mathematics from a set of unrelated
technical details, each constructed in order to resolve a specific
problem, to a true and proper organic theory, that reveals deep
connections with classical sectors of mathematics and with other
fields of research to which it is traditionally related. In these
last decades, the specialization demanded by research has rendered
more and more arduous the task of whoever wants to establish
connections between various disciplines and even between diverse
sectors of the same discipline. Rota has been one of the rare
people of science who, for the vastness of interests and of his
culture, has known how to move himself with ease and with depth
of thought in fields, even those extremely distant, being able
with that to collect deep analogies between results that are
apparently different.

His premature death is an inestimable loss for comtemporary
mathematics.
D. Senato, M. Barnabei, G.C. Barozzi

Translated by David Glynn

Comment by David Glynn — March 6, 2017 @ 2:47 am | Reply
[…] er lige sat et nyt projekt i søen. Om Rotas basisformodning, som siger følgende: Hvis man har n baser B1,…,Bn for et […]

Pingback by Polymath – matematik i fællesskab online – åbent for alle. | Matematikbloggen på AAU — March 6, 2017 @ 2:50 pm | Reply
I have created a second blog post on this topic. In most cases, further comments should be posted there rather than here. https://polymathprojects.org/2017/03/06/rotas-basis-conjecture-polymath-12-2/

Comment by tchow8 — March 6, 2017 @ 11:22 pm | Reply
[…] conjecture. A similar slightly weaker form of the conclusion of Rota’s basis conjecture is conjectured by Ron Aharoni and Eli Berger in much much greater […]

Pingback by Test Your Intuition about the Alon-Tarsi Conjecture | Combinatorics and more — March 15, 2017 @ 10:29 am | Reply
Hi! are there any news or updates on this project??

Comment by Andreas — April 27, 2017 @ 1:03 pm | Reply
- Not much, but the new thread is https://polymathprojects.org/2017/03/06/rotas-basis-conjecture-polymath-12-2/.
  
  Comment by domotorp — April 27, 2017 @ 4:12 pm | Reply
[…] and even then I usually regard it as a positive contribution to the discussion. When I made this remark on poymath12, which turned out to be quite silly a few minutes later, I somehow lost my confidence […]

Pingback by Where were we? | Combinatorics and more — August 24, 2017 @ 5:49 pm | Reply
[…] 12) to solve it. (Here is my post on the project with various variants of the conjecture, the first post on the polymath blog, and the wiki). See this post for several famous conjectures by Rota, and this post about the […]

Pingback by To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically | Combinatorics and more — August 14, 2020 @ 10:09 am | Reply

RSS feed for comments on this post. TrackBack URI

	Anonymous on Rota’s Basis Conjecture:…
	Cherrypick India on Polymath projects 2021
	tanner808 on Polymath projects 2021
	Anonymous on Polymath 11 is Now Open
	Chenxiao Tian on Polymath 11 is Now Open
	ryeguy10 on Polymath 11 is Now Open
	ndnnnd on Polymath projects 2021
	Prime time on Two polymath (of a sort) propo…
	What comes after exp… on Minipolymath2 project: IMO 201…
	Will AI Replace Math… on Spontaneous Polymath 14…
	gui7575 on A new polymath proposal (relat…
	Thomas Vu on Polymath projects 2021
	Mary Megrant on Polymath projects 2021
	h0sane on A sort of Polymath on a famous…
	Thomas Vu on Polymath projects 2021

The polymath blog

February 23, 2017