Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H)r(H) of a graph HH is the minimum positive integer NN such that every two-coloring of the edges of the complete graph KNKN on NN vertices contains a monochromatic copy of HH. A graph HH is dd-degenerate if every subgraph of HH has minimum degree at most dd. Burr and Erdős in 1975 conjectured that for each positive integer dd there is a constant cdcd such that r(H)≤cdnr(H)≤cdn for every dd-degenerate graph HH on nn vertices. We show that for such graphs r(H)≤2cdlognn, improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for dd fixed, almost surely the random graph G(n,d/n)G(n,d/n) has Ramsey number linear in nn. For random bipartite graphs, our proof gives nearly tight bounds.