The Density Hales-Jewett Theorem and Open-Source Mathematics

COMPUTER SCIENCE/DISCRETE MATH I
Topic:The Density Hales-Jewett Theorem and Open-Source Mathematics
Speaker:Ryan O'Donnell
Affiliation:Carnegie Mellon University
Date:Monday, May 18
Time/Room:11:15am - 12:15pm/S-101

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.