On the Ramsey number of the triangle and the cube

Abstract

The Ramsey number r(K 3,Q n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erdős conjectured that r(K 3,Q n )=2 n+1−1 for every n∈ℕ, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K 3,Q n )⩽7000·2 n . Here we show that r(K 3,Q n )=(1+o(1))2 n+1 as n→∞.

Locations

• arXiv (Cornell University) - View - PDF
• London School of Economics and Political Science Research Online (London School of Economics and Political Science) - View - PDF
• COMBINATORICA - View