Ramsey numbers of cubes versus cliques

Choongbum Lee (이중범)

Department of Mathematics, MIT, Cambridge, MA, USA

Department of Mathematics, MIT, Cambridge, MA, USA

2013/01/04 Fri 4PM-5PM

The cube graph Q

Joint work w/ David Conlon, Jacob Fox, and Benny Sudakov

_{n}is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^{n}vertices. The Ramsey number r(Q_{n}, K_{s}) is the minimum N such that every graph of order N contains the cube graph Q_{n}or an independent set of order s. Burr and Erdős in 1983 asked whether the simple lower bound r(Q_{n}, K_{s}) ≥ (s-1)(2^{n}-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

Tags: 이중범