On size Ramsey numbers of graphs with bounded degree (Q5928571): Difference between revisions

The paper settles an old question of \textit{J. Beck} [Algorithms Comb. 5, 34-45 (1990; Zbl 0735.05056)] on size Ramsey numbers of graphs. For graphs \(F\) and \(G\), \(F \rightarrow G\) means that every 2-coloration of the edges of \(F\) contains a monochromatic copy of \(G\). Furthermore \(\widehat r(G)\) is the smallest number for which there exists a graph \(F\), such that \(F\) has \(\widehat r(G)\) edges and \(F \rightarrow G\). The authors give a very nice construction for a graph \(G\) with largest degree 3 and still \(\widehat r(G) \geq cn(\log_2 n)^\alpha\), where \(c=\frac{1}{10}\), and \(\alpha=\frac{1}{60}\). It disproves Beck's conjecture of \(\widehat r(G_{n,r}) \leq c(r)n\), where the graph \(G_{n,r}\) has \(n\) vertices, its maximum degree is \(r\), and \(c(r)\) depends only on \(r\).