Cube Ramsey numbers are polynomial

Let R ( G ) be the least integer p such that for all bicolorings of the edges of complete graph K p , at least one of the monochromatic subgraphs contains a copy of G . We show that for any positive constant c and bipartite graph G =( U ,  V ;  E ) of order n where the maximum degree of vertices in U is at most $c\,{\rm log}\,n,\,R(G) < n^{1+(c+\sqrt{c^2+4c})/2+o(1)}.$ In particular, this shows that the Ramsey number of the n ‐cube Q n satisfies $R(Q_n)<2^{(3+\sqrt{5}n/2+o(n)}$ which improves the bound 2 cn  log  n due to Graham, Rödl, and Ruciński. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 99–101, 2001