Rota’s Basis Conjecture: Polymath 12, post 3

May 5, 2017

Rota’s Basis Conjecture: Polymath 12, post 3

Filed under: polymath proposals — tchow8 @ 3:48 am

We haven’t quite hit the 100-comment mark on the second Polymath 12 blog post, but this seems like a good moment to take stock. The project has lost some of its initial momentum, perhaps because other priorities have intruded into the lives of the main participants (I know that this is true of myself). However, I don’t want to turn out the lights just yet, because I don’t believe we’re actually stuck. Let me take this opportunity to describe some of the leads that I think are most promising.

Online Version of Conjecture

For general matroids, the online version of Rota’s Basis Conjecture is false, but it is still interesting to ask how many bases are achievable. One of the nicest things to come out Polymath 12, in my opinion, has been a partial answer to this question: It is somewhere between n/3 + c and n/2 + c. There is hope that this gap could be closed. If the gap can be closed then in my opinion this would be a publishable short paper. Incidentally, if a paper is published by Polymath 12, what pseudonym should be used? I know that D. H. J. Polymath was used for the first project, but maybe R. B. C. Polymath would make more sense?

Graphic Matroids

It was suggested early on that graphic matroids might be a more tractable special case. It wasn’t immediately clear to me at first why, but I understand better now. Specifically, graphic matroids with no K₄ minor are series-parallel and therefore strongly base-orderable and therefore satisfy Rota’s Basis Conjecture. Thus, in some sense, K₄ is the only obstruction to Rota’s Basis Conjecture for graphic matroids, whereas the analogous claim for matroids in general does not hold.

In one of my papers I showed, roughly speaking, that if one can prove an n × 2 version of Rota’s Basis Conjecture, then this fact can be parlayed into a proof of the full conjecture. Of course the n × 2 version is false in general, but I do believe that a thorough understanding of what can happen in just two columns will give significant insight into the full conjecture. One question I raised was whether any n × 2 arrangement of edges can yield two columns that are bases if we pull out no more than n/3 edges. This is perhaps a somewhat clumsy question, but it is trying to get at the question of whether there are any n × 2 counterexamples that are not just the disjoint union of copies of K₄ that have been expanded by “uncontracting” some edges. If we can classify all n × 2 counterexamples then I think that this would be a big step towards proving the full conjecture for graphic matroids.

This is of course not the only possible way to tackle graphic matroids. The main point is that I think there is potential for serious progress on this special case.

Computational Investigations

I mentioned an unpublished manuscript by Michael Cheung that reports that the n = 4 case of Rota’s Basis Conjecture is true for all matroids. I find this to be an impressive computation and I think it deserves independent verification.

Finding 5 × 2 counterexamples to Rota’s Basis Conjecture would also be illuminating in my opinion. Gordon Royle provided a link to a database of all nine-element matroids that should be helpful. Luke Pebody started down this road but as far as I know has not completed the computation.

Strongly Base-Orderable Matroids

In 1995, Marcel Wild proved the following result (“Lemma 6”): Let $M$ be a matroid on an $n^2$ -element set $E$ that is a disjoint union of $n$ independent sets $B_1, \ldots, B_n$ of size $n$ . Assume that there exists another matroid $M'$ on the same ground set $E$ with the following properties:

(1) $M'$ is strongly base orderable.

(2) $r(X) \ge |X|/n$ for all $X \subseteq E$ , where $r$ is the rank function of $M'$ .

(3) All circuits $C$ of $M$ satisfying $\forall j: |C\cap B_j| \le 1$ remain dependent in $M'$ .

Then there is an $n\times n$ grid whose $i$ th row comprises $B_i$ and whose columns are independent in $M$ .

Wild obtained several partial results as a corollary of Lemma 6. How much mileage can we get out of this? Can we always find a suitable $M'$ for graphic matroids?

Variants and Related Conjectures

I’m less optimistic that these will lead to progress on Rota’s Basis Conjecture itself, but maybe I’m wrong. Gil Kalai made several suggestions:

Consider d + 1 (affinely independent) subsets of size d + 1 of $\mathbb R^d$ such that the origin belongs to the interior of the convex hull of each set. Is it possible to find d + 1 sets of size d + 1 such that each set is a rainbow set and the interior of the convex hulls of all these sets have a point in common?
The wide partition conjecture or its generalization to arbitrary partitions.
If we have sets B₁, …, B_n (not necessarily bases) that cannot be arranged so that all n columns are bases, then can you always find disjoint n + 1 sets C₁, …, C_n+1 such that each set contains at most one member from each B_j and the intersection of all linear spans of the C_i is non trivial? (I confess I still don’t see why we should expect this to be true.)

Pavel Paták presented a lemma from one of his papers that might be useful. Let M be a matroid of rank r and let S be a sequence of kr elements from M, split into r subsequences, each of length at most k. Then any largest independent rainbow subsequence of S is a basis of M if and only if there does not exist an integer s < r and set of s + 1 color classes, such that the union of these color classes has rank s.

In a different direction, there are graph-theoretic conjectures such as the Brualdi–Hollingsworth conjecture: If the complete graph K_2m (for m ≥ 3) is edge-colored in such a way that every color class is a perfect matching, then there is a decomposition of the edges into m edge-disjoint rainbow spanning trees.

Remarks on Previous Blog Post

Finally, let me make a few remarks about the directions of research that were suggested in my previous Polymath 12 blog post. I was initially optimistic about matroids with no small circuits and I still think that they are worth thinking about, but I am now more pessimistic that we can get much mileage out of straightforwardly generalizing the methods of Geelen and Humphries, for reasons that can be found by reading the comments. Similarly I am more pessimistic now that the algebro-geometric approach will yield anything since being a basis is an open condition rather than a closed condition.

The other leads in that blog post have not been pursued much and I think they are still worth looking at. In particular, that old standby, the Alon–Tarsi Conjecture, may still admit more partial results. Rebecca Stones’s suggestion that maybe L_n^even – L_n^odd ≢ 0 (mod p) when p = 2n + 1 is prime still looks to me like a good idea and I don’t think many people have seriously thought about this. Also I agree with David Glynn that more people should study Carlos Gamas’s recent paper on the Alon–Tarsi Conjecture.

Comments (19)

19 Comments »

Thank you for this very nice review! D. H. J. Polymath was used also in polymath4 and polymath8. (Rather than perhaps E.F.P Polymath and B. G. P. Polymath) so perhaps we should keep it :) .

Comment by Gil Kalai — May 6, 2017 @ 5:54 pm | Reply
Is there a nice extension of Rota’s conjecture when instead of $d+1$ sets of size $d+1$ you are given $d+1$ sets of size $m$ where $m$ can be also smaller or larger than $d+1$ ?

Comment by Gil Kalai — May 7, 2017 @ 4:42 am | Reply
- I think the natural thing is to replace “basis” with “independent set.” If $m < d+1$ then this becomes something we’ve been discussing already in Polymath 12, and in particular I think that the $m = 2$ case is worth understanding thoroughly, starting with graphic matroids.
  
  If $m > d+1$ then this falls within the scope of the wide partition conjecture, so it “should” be true in my opinion. But I don’t think anyone has tried to prove it. Maybe for small $d$ or large $m$ this is not so hard to prove? To be explicit: Given $d+1$ independent sets, each of size $m > d+1$ , does there exist a $d+1 \times m$ grid whose rows are the given independent sets and whose columns are independent?
  
  Comment by tchow8 — May 8, 2017 @ 12:00 am | Reply
- Here’s a simple observation. If we have 2 independent sets $I_1$ and $I_2$ of size $n\ge 2$ then there is always a $2\times n$ grid whose rows are $I_1$ and $I_2$ , and whose columns are independent. To see this, label the elements in $I_1$ with the numbers 1 to $n$ and also label the elements in $I_2$ with the numbers 1 to $n$ , subject only to the constraint that if there exist $x \in I_1$ and $y\in I_2$ that are parallel, then $x$ and $y$ get the same label. This is always possible, because $I_1$ is independent and hence cannot contain two elements that are parallel to each other (and the same goes for $I_2$ ). Then the existence of the desired $2\times n$ grid follows from the fact that derangements exist.
  
  Can we prove the analogous statement for 3 independent sets of size $n \ge 3$ ? This statement includes the $n=3$ case of Rota’s Basis Conjecture as a special case, so the proof can’t be completely trivial, but perhaps it’s not too hard either.
  
  Comment by tchow8 — May 12, 2017 @ 8:30 pm | Reply
  - I just realized that this question is easy to answer. As mentioned before, we obtain a “strong” form of Rota’s Basis Conjecture by replacing “basis” by “independent set.” And as Luke Pebody explained in a comment to an earlier post, the strong form reduces to the usual form just by getting rid of all the independent sets of size more than $n$ . Then, given the strong form of the conjecture, the $n\times m$ version of the conjecture for $m \ge n$ follows easily by induction on $m$ , because constructing the first column of the desired grid is easy. So the $n \times m$ version of the conjecture for $m \ge n$ is equivalent to the original Rota Basis Conjecture.
    
    Comment by tchow8 — May 13, 2017 @ 2:41 am | Reply
In the spirit of conjectures by Ron Aharoni (and also the result reported here), I wonder if for the conclusion of Rota Basis conjectures it is enough to start with $n$ sets of $n$ vectors but instead of demanding that each set is a basis to ask that each pair of sets can be divided into two bases.

Comment by Gil Kalai — May 20, 2017 @ 5:18 pm | Reply
- I think that the usual graphic counterexample should do – let $n=3$ and the first row be 12, 12, 34, the second 13, 13, 24, and the third 14, 14, 23. A simple possible proof is that 34, 24 and 23 cannot be in one column, so one of them, say, 34 will be in a column without the other two. But then this column cannot contain 2.
  
  Comment by domotorp — May 20, 2017 @ 8:05 pm | Reply
With the $n\times 2$ version of the conjecture in mind, let us define a bi-tree to be a connected undirected graph, possibly with multiple edges, whose edge set is the disjoint union of two spanning trees. Thus if a bi-tree has $n+1$ vertices then it has $2n$ edges.

Question: In how many edges can two (distinct) $K_4$ minors of a bi-tree intersect?

A $K_4$ minor is, in particular, a set of 6 edges, so a priori the answer could be as high as 5, but it is not obvious to me how to construct an example.

Comment by tchow8 — May 29, 2017 @ 2:02 am | Reply
- I don’t really understand why it would be a restriction that the graph is a bi-tree. In particular, we a $K_4$ with a subdivided edge is a bi-tree. If we consider the two $K_4$ minors that we obtain by merging the vertex $w$ subdividing the edge $uv$ in one of the minors to one of the endpoints (to obtain $uw$ ), in the other minor to the other endpoint (to obtain $vw$ ), then these minor share 5 edges. Or did I misunderstand something?
  
  Comment by domotorp — May 29, 2017 @ 8:49 am | Reply
  - How is $K_4$ with a subdivided edge a bi-tree? It has an odd number of edges.
    
    Comment by tchow8 — May 31, 2017 @ 2:37 am | Reply
    - It is a subgraph of a bi-tree, you can extend it into a bi-tree in several ways. Adding another edge won’t decrease the number in which the $K_4$ minors intersect.
      
      Comment by domotorp — May 31, 2017 @ 4:06 am | Reply
      - I see. I was hoping that this might yield a different type of $n\times 2$ counterexample, but your construction here doesn’t seem to do that. Consider the four sets $\{13,14\}, \{12,45\}, \{35,24\}, \{25,34\}$ , where each two-digit number $ab$ represents an edge connecting vertices $a$ and $b$ in a graph with five vertices labeled 1 to 5. This is an instance of your construction, and it is “almost” an $n\times 2$ counterexample, but unfortunately there is a unique way to make both columns into bases.
        
        Comment by tchow8 — June 1, 2017 @ 3:54 am | Reply
- I’d like to try to construct more $n\times 2$ counterexamples from graphs. As a start, can someone construct an $n\times 2$ graphical counterexample that (a) contains no doubled edges and (b) contains no induced subgraph isomorphic to $K_4$ ?
  
  To recap, this means constructing a bi-tree together with an arrangement of its edges into two columns such that no set of row permutations produces spanning trees in both columns.
  
  Comment by tchow8 — June 5, 2017 @ 9:28 pm | Reply
This summer, Jim Geelen and I worked on improving the lower bound on the number of transversal bases, which he and his student Kerri Webb had previously shown to be at least $\sqrt{n-1}$ . Tim had mentioned in a comment that it might be worthwhile to consider the problem via a probabilistic approach. Jim had the same intuitions, and this is exactly what we used to get the new result. I will discuss the central ideas of our proof here; the detailed writeup can be found on the ArXiv.

Theorem 1
Given $n$ disjoint bases $B_1, \dots, B_n$ in a rank- $n$ matroid, there are at least $\lfloor \frac {n}{6 \lceil \log n \rceil} \rfloor$ disjoint transversal bases.

Throughout the post, I will use the natural logarithm, and define $\alpha = 3 \lceil \log n \rceil$ .

Let $m = \lfloor \frac {n}{6 \lceil \log n \rceil}$ . For each $i \in \{1, \dots, n\}$ , let $S_{i,1}, \dots, S_{i,2m}$ be disjoint $\alpha$ -element subsets of $B_i$ chosen at random. Now for each $j \in \{1, \dots, 2m\}$ , note that the sets $S_{1,j}, \dots, S_{n,j}$ are subsets of $B_1,\ldots,B_n$ that are chosen independently and uniformly at random. If $(S_{1,j}, \dots, S_{n,j})$ contains a transversal basis with probability at least 1/2, then by the linearity of expectation, the expected number of disjoint transversal bases of $(B_1, \dots, B_n)$ will be at least $\frac{1}{2} \cdot 2m$ . It follows that there exist at least $m$ disjoint transversal bases.

Therefore, to prove Theorem 1, it suffices to prove the following:
Theorem 2
Let $B_1, \dots, B_n$ be disjoint bases for a rank- $n$ matroid. If $S_1 \subset B_1, \dots, S_n \subset B_n$ are $\alpha$ -element subsets chosen independently and uniformly at random, then the probability that $(S_1, \dots, S_n)$ contains a transversal basis is at least 1/2.

There is a very useful theorem by Rado which characterizes the existence of transversal basis.
Rado’s Theorem
Let $(S_1, \dots, S_n)$ be sets of elements in a rank- $n$ matroid. Then there is a transversal basis of $(S_1, \dots, S_n)$ if and only if $r(\cup_{i \in X} S_i) \geq |X|$ for all $X \subseteq \{1, \dots, n\}$ .

In order to prove Theorem 2, we focus on the probability of failure of each of the conditions in Rado’s Theorem. Let $B_1,\ldots, B_k$ be bases (not necessarily disjoint) of a rank- $n$ matroid. We let $Q(B_1,\ldots,B_k)$ denote the probability that, when $\alpha$ -element subsets $S_1,\ldots,S_k$ are chosen independently and uniformly at random from $B_1,\ldots,B_k$ respectively, we have $r(S_1\cup\ldots\cup S_k)< k$ .

Note that we do not require the sets $B_1,\ldots,B_k$ to be disjoint. In fact, the case that $B_1=\cdots=B_k$ is interesting and plays an important role in the proof. In this case we have $r(S_1\cup\ldots\cup S_k) = |S_1\cup\ldots\cup S_k|$ , and hence the failure probability $Q(B_1,\ldots,B_k)$ depends only on $k$ and $n$ ; we denote it by $Q_{k,n}$ . It turns out this is an upper bound on all the other failure probabilities. We prove this by naively constructing an independent set within the randomly chosen $S_1, \ldots, S_k$ , and showing that it has rank less than $k$ with probability equal to $Q_{k,n}$ .

We then compute $Q_{k,n}$ , which is closely related to the Coupon Collector’s Problem, as well as a bipartite matching problem considered by Erdős and Renyi. We get
${Q_{k,n}} \leq \binom{n}{k-1} \left( \frac{\binom{k-1}{\alpha}}{\binom{n}{\alpha}} \right)^k.$

Finally, by the union bound, the probability that $(S_1, \dots, S_n)$ does not contain a transversal basis is at most the sum of the failure probabilities of each of the conditions in Rado’s Theorem; hence, it is at most $\sum_{k=1}^{n} \binom{n}{k} Q_{k,n}.$ With some algebraic manipulation, we can show that this is bounded by 1/2, as required by our theorem.

Comment by Sally Dong — September 5, 2017 @ 7:28 pm | Reply
- This is a marvelous result and a huge improvement over the previous bound! It is very tempting now to speculate that a combination of explicit construction and random construction (a la Keevash as it were) could be the path to the full conjecture.
  
  Comment by tchow8 — September 6, 2017 @ 2:03 am | Reply
For what it’s worth, in connection with Rota’s basis conjecture for graphic matroids, the following is very easy to show:
Proposition: Let $G$ be a simple graph edge-coloured in such a way that the edges in each colour class $c$ form a spanning tree $t_c$ . Then there is a partition of $G$ into edge-disjoint rainbow trees.
Proof: Choose an arbitrary vertex $v$ of $G$ and consider the orientation of each $t_c$ corresponding to rooting $t_c$ at $v$ (i. e. every edge points away from $v$ .) Assign to each edge the vertex it points to. For each vertex $w \neq v$ , consider the subgraph consisting of the edges to which $w$ is assigned. Since each vertex $\neq v$ is assigned to precisely one edge from each colour class, these graphs form a collection of edge-disjoint rainbow trees.

Comment by dsp — September 16, 2017 @ 4:32 pm | Reply
Although Polymath 12 seems to have gone dormant, I decided to finish writing the Polymath Wiki page. It is intended to be more of a capsule summary than a complete survey, but I have tried to make the list of references as complete as possible.

Comment by tchow8 — October 23, 2017 @ 12:21 am | Reply
Very nice progress in the paper
Halfway to Rota’s basis conjecture authored
by
Matija Bucić, Matthew Kwan, Alexey Pokrovskiy, and Benny Sudakov

Abstract: In 1989, Rota made the following conjecture. Given $n$ bases $B_{1},\dots,B_{n}$ in an $n$-dimensional vector space $V$, one can always find $n$ disjoint bases of $V$, each containing exactly one element from each $B_{i}$ (we call such bases transversal bases). Rota’s basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (for example, the conjecture was recently the subject of the collaborative “Polymath” project). In this paper we prove that one can always find $\left(1/2-o\left(1\right)\right)n$ disjoint transversal bases, improving on the previous best bound of $\Omega\left(n/\log n\right)$. Our results also apply to the more general setting of matroids.

http://front.math.ucdavis.edu/1810.07462

Comment by Gil Kalai — October 19, 2018 @ 8:49 am | Reply
[…] there is a nice development on Rota’s basis conjecture (Polymath12) described in the paper Halfway to Rota’s basis conjecture, by Matija Bucić, Matthew Kwan, […]

Pingback by Updates and Pictures | The polymath blog — October 19, 2018 @ 9:10 am | Reply

RSS feed for comments on this post. TrackBack URI

	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
	Hyun seok on A sort of Polymath on a famous…
	Polymath16, seventee… on Polymath proposal: finding sim…

The polymath blog

May 5, 2017