Cube Ramsey numbers are polynomial (Q2748419)

Let \(G,H\) be two graphs. The Ramsey number \(R(G,H)\) is the minimum number \(p\) such that for any bicolouring of the edges of the complete graph \(K_p\), either the first monochromatic subgraph contains a copy of \(G\) or the second monochromatic subgraph contains a copy of \(H\). The symbol \(R(G)\) is used for the Ramsey number \(R(G,G)\). The paper provides a contribution to a problem formulated by \textit{S. A. Burr} and \textit{P. Erdős} [Colloq. Math. Soc. János Bolyai 10, 215-240 (1975; Zbl 0316.05110)]. They asked whether the Ramsey number of the \(n\)-dimensional cube \(Q_n\) is linear with the respect to the order of \(Q_n\). It is shown that for any positive constant \(c\) and bipartite graph \(G(U,V,E)\) of order \(n\) with the maximum degree of vertices in \(U\) at most \(c\log n\), \(R(G)< n^{1+\frac{c+\sqrt{c^2+4c}}{2}+o(1)}\). This implies that \(R(Q_n)<2^{\frac{3+\sqrt{5}}{2}n+o(n)}\). The proof is short, elegant and very well readable.