KAIST Discrete Math Seminar

The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2ⁿ 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ⁿ -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