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.
Like this:
Like Loading...
Related
This entry was posted on July 13, 2010 at 5:40 pm and is filed under News, polymath. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
July 13, 2010 at 8:16 pm |
[…] Philomath Project By kristalcantwell There is a Philomath problem here. Philomath is a tribute to Polymath. The problem that is a combinatorial problem that if solved would have implications in computer science. For more on the problem see here and here. […]
July 15, 2010 at 5:51 pm |
I just added a link to Scott’s project on the polymath wiki site. I wonder if his project will need some wiki space if it really gets going?
November 20, 2011 at 10:50 am
polymathprojects.org is not a good domain name – some of us didn’t have high school education based on projects. At this time polymath.gy (Guyana) is available at 101domain.com – 48 USD/1 year.
The polymath Coven-Meyerowitz conjecture you have suggested feels like a multimath problem. Where would you consider working on it? Tim’s site is preferable – more mathematicians know him personally, so may feel more comfortable.