On bipartite graphs with linear Ramsey numbers (Q5955195)

The upper bound \(8(8\Delta)^{\Delta}n\) is proved for the Ramsey number of \(n\)-vertex bipartite graphs with largest degree \(\Delta\). This gives a \(2^{cn\log n}\) bound for the \(n\)-cube. In the other direction, probabilistic methods give the existence of a constant \(c>1\) such that for \(\Delta\geq 1\), \(n\geq \Delta+1\), unless \(\Delta=1\) and \(n=2,3,5\), there exists a bipartite \(n\)-vertex graph with maximum degree \(\Delta\) and Ramsey number at least \(c^{\Delta}n\).