2013/02/15 by Gonzalo Fiz Pontiveros, Pontiveros, Gonzalo Fiz, Simon Griffiths +7
Engineering · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1302.3840
16 pages
arxiv created 2013/02/15 · openalex publication_date 2013/02/15 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Ramsey number r(K3,Qn) is the smallest integer N such that every red-blue colouring of the edges of the complete graph KN contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erdős conjectured that r(K3,Qn) = 2n+1 - 1 for every n ∈ \N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K3,Qn) ≤ 7000 ⋅ 2n. Here we show that r(K3,Qn) = (1 + o(1)) 2n+1 as n → ∞.