Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

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$.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  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

Automatic MiSe System Software Version 1.4803M   |   admin login