The polymath blog

June 9, 2019

A sort of Polymath on a famous MathOverflow problem

Filed under: polymath proposals — Gil Kalai @ 6:09 pm


Is there any polynomials {P} of two variables with rational coefficients, such that the map P: \mathbb Q \times \mathbb Q \to \mathbb Q  is a bijection?  This is a famous 9-years old open question on MathOverflow.  Terry Tao initiated a sort of polymath attempt to solve this problem conditioned on some conjectures from arithmetic algebraic geometry.  This project is based on an plan by Tao for a solution, similar to a 2009 result by Bjorn Poonen who showed that conditioned on the Bombieri-Lang conjecture, there is a polynomial so that the map P: \mathbb Q \to \mathbb Q \times \mathbb Q  is injective. (Poonen’s result  answered a question by Harvey Friedman from the late 20th century, and is related also to a question by Don Zagier.)

February 3, 2019

Ten Years of Polymath

Filed under: discussion — Gil Kalai @ 3:14 pm
Tags: ,

Ten years ago on January 27, 2009, Polymath1 was proposed by Tim Gowers  and was launched on February 1, 2009. The first project was successful and it followed by 15 other formal polymath projects and a few other projects of similar nature.

October 19, 2018

Updates and Pictures

Filed under: discussion — Gil Kalai @ 9:10 am
Tags: , ,

Three short items:

Progress on Rota’s conjecture (polymath12) by Bucić, Kwan, Pokrovskiy, and Sudakov

First, there is a remarkable development on Rota’s basis conjecture (Polymath12) described in the paper
Halfway to Rota’s basis conjecture, 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.

Earlier the best result was giving n/\log n disjoint transversal bases.

Here is a subsequent paper about the more general Kahn’s conjecture

Polymath 16 is alive and kicking

Polymath 16 of the chromatic number of the plane is in its eleventh post. A lot of interesting developments and ideas in various directions!

The polymath picture

I took some pictures which are a little similar to our logo picture (last picture below). (more…)

April 10, 2018

Polymath proposal: finding simpler unit distance graphs of chromatic number 5

Filed under: polymath proposals — ag24ag24 @ 5:56 am

The Hadwiger-Nelson problem is that of determining the chromatic number of the plane (\mathrm{CNP}), defined as the minimum number of colours that can be assigned to the points of the plane so as to prevent any two points unit distance apart from being the same colour. It was first posed in 1950 and the bounds 4 \leq \mathrm{CNP} \leq 7 were rapidly demonstrated, but no further progress has since been made. In a recent preprint, I have now excluded the case \mathrm{CNP} = 4 by identifying a family of non-4-colourable finite “unit-distance” graphs, i.e. graphs that can be embedded in the plane with all edges being straight lines of length 1. However, the smallest such graph that I have so far discovered has 1567 [EDIT: 1581 after correction] vertices, and its lack of a 4-colouring requires checking for the nonexistence of a particular category of 4-colourings of subgraphs of it that have 388 [EDIT: 395 after correction] and 397 vertices, which obviously requires a computer search.

I’m therefore wondering whether a search for “simpler” examples might work as a Polymath project. An example might be defined as simpler if it has fewer vertices, or if it has a smaller largest subgraph whose 4-colourability must be checked directly, etc. I feel that a number of features make this nice for Polymath:

  1. being graph theory, it’s nicely accessible/seductive to non-specialists
  2. it entails a rich interaction between theory and computation
  3. simpler graphs may lead to insights into what properties such graphs will always/usually have, which might inspire strategies for seeking 6-chromatic examples, improved bounds to the analogous problem in higher dimensions, etc.

I welcome comments!

Aubrey de Grey


January 26, 2018

A new polymath proposal (related to the Riemann Hypothesis) over Tao’s blog

Filed under: polymath proposals — Gil Kalai @ 7:17 am
Tags: ,

(From a post “the music of the primes” by  Marcus du Sautoy.)


A new polymath proposal over Terry Tao’s blog who wrote: “Building on the interest expressed in the comments to this previous post, I am now formally proposing to initiate a “Polymath project” on the topic of obtaining new upper bounds on the de Bruijn-Newman constant {\Lambda}. The purpose of this post is to describe the proposal and discuss the scope and parameters of the project.”

Briefly showing that \Lambda \le 0 is the Rieman Hypothesis, and it is known that \Lambda \le 1/2.  Brad Rodgers and Terry Tao proved an old conjecture that \Lambda \ge 0. The purpose of the project is to push down this upper bound. (The RH is not considered a realistic outcome.)



Spontaneous Polymath 14 – A success!

Filed under: polymath proposals — Gil Kalai @ 6:27 am
Tags: ,

This post is to report an unplanned polymath project, now called polymath 14 that took place over Terry Tao’s blog. A problem was posed by Apoorva Khare was presented and discussed and openly and collectively solved. (And the paper arxived.)

August 22, 2017

Polymath 13 – a success!

Filed under: polymath proposals — Gil Kalai @ 2:09 pm

This post is to note that the polymath13 project has successfully settled one of the major objective. Reports on it can be found on Gower’s blog especially in this post Intransitive dice IV: first problem more or less solved? and this post Intransitive dice VI: sketch proof of the main conjecture for the balanced-sequences model.


May 15, 2017

Non-transitive Dice over Gowers’s Blog

Filed under: polymath proposals — Gil Kalai @ 7:36 am

A polymath-style project on non transitive dice (Wikipedea) is now running over Gowers blog. (Here is the link to the first post.)



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 K4 minor are series-parallel and therefore strongly base-orderable and therefore satisfy Rota’s Basis Conjecture.  Thus, in some sense, K4 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 K4 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 ith 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:

  1. 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?
  2. The wide partition conjecture or its generalization to arbitrary partitions.
  3. If we have sets B1, …, Bn (not necessarily bases) that cannot be arranged so that all n columns are bases, then can you always find disjoint n + 1 sets C1, …, Cn+1 such that each set contains at most one member from each Bj and the intersection of all linear spans of the Ci 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 K2m (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 LnevenLnodd ≢ 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.

March 6, 2017

Rota’s Basis Conjecture: Polymath 12

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

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

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

Matroids with No Small Circuits

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

Independent Partial Transversals

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

Local Obstructions

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

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

Algebraic Geometry

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

Let me also mention that Jan Draisma sent me email recently with the following remarks: “A possible idea would be to consider a counterexample as lying in some suitable equivariant Hilbert scheme in which being a counterexample is a closed condition, then degenerate to a counterexample stable under a Borel subgroup of GLn, and come to a contradiction. ‘Equivariant’ should reflect the action of GLn × (SnSnn). However, I have not managed to make this work myself, even in low dimensions. In fact, having a good algebro-geometric argument for the n = 3 case, rather than a case-by-case analysis, would already be very nice!”

Alon–Tarsi Conjecture

Now let me move on to other ideas suggested in the comments. There were several thoughts about the Alon–Tarsi Conjecture that the Alon–Tarsi constant LnevenLnodd ≠ 0 when n is even. Rebecca Stones gave a formula that, as Gil Kalai observed, equated the Alon–Tarsi constant with the top Fourier–Walsh coefficient for the function detn; i.e., up to sign, the Alon–Tarsi constant is

ΣA (–1)σ(A) det(A)n,

where the sum is over all zero-one matrices and σ(A) is the number of zero entries in A. This formula suggests various possibilities. For example one could try to prove that LnevenLnodd ≢ 0 (mod p) where p = 2n + 1 is prime, because in this case, det(A)n must be 0, 1, or –1. This would already be a new result for n = 26, and the case n = 6 is small enough to compute explicitly and look for inspiration. Luke Pebody posted the results of some computations in this case.

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

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

Generalizations and Special Cases

Some generalizations and special cases of the conjecture were mentioned in the comments. Proving the conjecture for graphic matroids or binary matroids would be an enormous advance. There is a generalization due to Jeff Kahn, in which we have n2 bases Bij and we have to pick vijBij to form an n × n grid whose rows and columns are all bases. Another generalization was prompted by a remark by David Eppstein: Suppose we are given n bases B1, …, Bn of a vector space of dimension mn, and suppose we are given an n × n zero-one matrix with exactly m 1’s in every row and column. Can we replace each 1 in the matrix with a vector in such a way that the m vectors in row i are the elements of Bi and such that the m vectors in every column form a basis?

Juan Sebastian Lozano suggested the following reformulation: Does there exist a group G such that V is a representation of G and there exists giG such that gi Bi = Bi+1, and for every vector bB1,

span{g0b, …, gn – 1b} = V

where gi = gig1 and g0 is the identity?

Other Ideas

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

(v11, …, v1k), (v21, …, v2k), …, (vm1, …, vmk).

Then there exist pairwise distinct x1, …, xm, y1, …, ymV* and a map g:[m] → [k] such that for every i ∈ {1, …, m} we have yixi = vig(i).

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

Π {(xiλexj) : i < j, {i,j} = eE(G)},

where the λe are weights associated to the edges e.

Next Page »

Blog at