Computer Science/Discrete Mathematics Seminar I

On Feb. 1, in his blog, Tim Gowers proposed an open collaboration on a math problem. Specifically, he suggested working on a combinatorial proof of the Density Hales-Jewett Theorem. This theorem states that for every delta > 0, if n is sufficiently large and A is a set of at least delta 3^n strings from {1,2,3}^n, then A must contain a "combinatorial line"; i.e., three strings achievable by replacing the *'s by 1, by 2, and by 3 in a template from {1,2,3,*}^n. This theorem had been previously proven using ergodic-theory methods which gave no effective bound for n in terms of delta. A large number of people participated in the project, discussing ideas online in blogs and on wikis. On Mar. 10, Tim posted declaring the problem essentially solved; a writeup of the new combinatorial proof is underway. (As well, a separate project forked, working on constructions and bounds for small n = 3, 4, 5, 6, 7. This project also had much success.) I will explain the new proof of the Density Hales-Jewett Theorem, mention connections to computer science theory, and (time permitting) comment on what it was like to participate in the project. This is joint work of D.H.J. Polymath.