The smallest Ramsey numbers (Q1297442)

In classical Ramsey literature usually Ramsey numbers for complete graphs are studied, and it is asked how large they can be. Since Ramsey numbers are monotone functions in the edges of the excluded graphs, one can also investigate the other end, and ask how small a nontrivial Ramsey number of a graph on \(n\) vertices can be. This problem was first studied in [Utilitas Math. 9, 247-258 (1976; Zbl 0333.05119)] by \textit{S. A. Burr} and \textit{P. Erdős}, who determined the smallest Ramsey number of a connected graph on \(n\) vertices to be \(\left \lfloor{1\over 3}(4n -1)\right\rfloor\), and who asked for the (even smaller) minimum two-color Ramsey number of a graph of \(n\) vertices without isolated vertices. They gave a lower bound of \(n + \log n - O(\log\log n)\) and an upper bound of \(n + O(\sqrt{n})\), and conjectured that the lower bound is actually the correct one. In the current paper the authors prove an almost matching upper bound \(n + c\log n\) with \(c\approx 1.71\), using forests consisting of stars with an exponentially growing number of spikes as excluded graphs. They also sketch an application to graph discrepancy for trees.