Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, November 25, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Choongbum Lee (MIT)

A lower bound on Grid Ramsey problem

The Hales-Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales-Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product $K_n \times K_n$ in $r$ colors then, for $n$ sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah's proof shows that $n = r^{\binom{r+1}{2}} + 1$ suffices, and more than twenty years ago, Graham, Rothschild and Spencer asked whether this bound can be improved to a polynomial in $r$. We provide a negative answer to their question and give a superpolynomial lower bound in $r$.

Previous talks by year:   2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996

Information for students and suggested topics for student talks