Ramsey numbers of cubes versus cliques

الأصل · EN

The cube graph Qₙ is the skeleton of the n-dimensional cube. It is an n-regular graph on 2ⁿ vertices. The Ramsey number r(Qₙ, Kₛ) is the minimum N such that every graph of order N contains the cube graph Qₙ or an independent set of order s. Burr and Erdos in 1983 asked whether the simple lower bound r(Qₙ, Kₛ) >= (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.