Choongbum Lee (이중범), Ramsey numbers of cubes versus cliques

Ramsey numbers of cubes versus cliques
Choongbum Lee (이중범)
Department of Mathematics, MIT, Cambridge, MA, USA
2013/01/04 Fri 4PM-5PM
The cube graph Qn is the skeleton of the n-dimensional cube. It is an n-regular graph on 2n vertices. The Ramsey number r(Qn, Ks) is the minimum N such that every graph of order N contains the cube graph Qn or an independent set of order s. Burr and Erdős in 1983 asked whether the simple lower bound r(Qn, Ks) ≥ (s-1)(2n -1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.
Joint work w/ David Conlon, Jacob Fox, and Benny Sudakov


Comments are closed.