ACO The ACO Seminar (2012-2013)

Mar 21, 3:30pm, Wean 8220
Misha Lavrov, CMU
Improved bounds on Graham's number


Graham's number is an upper bound on a geometric problem in Ramsey theory that was popularized by Martin Gardner for being extremely large; the lower bound, on the other hand, is 13.

We show that a much stronger upper bound exists by reducing the problem to a variant of the Hales-Jewett problem. We also prove a lower bound of the same type. Finally, an entirely different approach can be used to prove a very small upper bound on a simplified variant of the Graham's number problem.

Joint work with Mitchell Lee and John Mackey.

Back to the ACO home page