Polymath news

If you haven’t already spotted this, you might like to know that Scott Aaronson has just posed a very interesting unsolved combinatorial problem and invited Polymath-style thoughts on it. I’ll give a quick and I hope appetite-whetting account of the problem here, but you could skip it if you want and jump straight to his posts on his blog and at Mathoverflow.

The problem is completely elementary, but it has consequences of great interest to theoretical computer scientists. As Scott says, it also seems to be at a realistic level of difficulty and highly suitable for a Polymath approach. (The first assertion is a coded way of saying that it isn’t a notorious “impossible” complexity assertion in disguise.) It asks this. Suppose you colour the points of with two colours in such a way that the origin is red and each of the coordinate axes contains at least one blue point. Do there exist constants , independent of , such that there must be a point that has at least neighbours that are coloured differently from ? At the moment, it seems that there isn’t even a proof that for sufficiently large there must be a point with 100 neighbours of the other colour. There is a non-trivial but not hard example that shows that cannot be more than . (Scott presents this in his Mathoverflow post.) A very brief remark is that if you just assume that not all points are coloured the same way, then the assertion is false: a counterexample is obtained if you colour a point red if its first coordinate is positive and blue otherwise.