Note on the multicolour size-Ramsey number for paths (Q1671658): Difference between revisions

Summary: The size-Ramsey number \(\hat{R}(F,r)\) of a graph \(F\) is the smallest integer \(m\) such that there exists a graph \(G\) on \(m\) edges with the property that any colouring of the edges of \(G\) with \(r\) colours yields a monochromatic copy of \(F\). In this short note, we give an alternative proof of the recent result of \textit{M. Krivelevich} [``Long cycles in locally expanding graphs, with applications'', Combinatorica (to appear), \url{doi:10.1007/s00493-017-3701-1}] that \(\hat{R}(P_n,r) = O((\log r)r^2 n)\). This upper bound is nearly optimal, since it is also known that \(\hat{R}(P_n,r) = \Omega(r^2 n)\).