Path Ramsey number for random graphs

Abstract

Answering a question raised by Dudek and Prałat, we show that if $pn\to \infty$, w.h.p.,~whenever $G=G(n,p)$ is $2$-coloured, there exists a monochromatic path of length $n(2/3+o(1))$. This result is optimal in the sense that $2/3$ cannot be replaced by a larger constant. As part of the proof we obtain the following result which may be of independent interest. We show that given a graph $G$ on $n$ vertices with at least $(1-\epsilon )\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, whenever $G$ is $2$-edge-coloured, there is a monochromatic path of length at least $(2/3-100\sqrt{\epsilon })n$. This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever $K_n$ is $2$-coloured there is a monochromatic path of length at least $2n/3$.

References in corpus (2)

• An alternative proof of the linearity of the size-Ramsey number of paths
• Combinatorial theorems relative to a random set

Cited by in corpus (12)

• The size-Ramsey number of powers of bounded degree trees
• Colour-biased Hamilton cycles in random graphs
• On some multicolour Ramsey properties of random graphs
• On the size-Ramsey number of grid graphs
• Size-Ramsey numbers of powers of hypergraph trees and long subdivisions
• The multicolour size-Ramsey number of powers of paths
• A note on the size Ramsey number of powers of paths
• On the size-Ramsey number of tight paths
• Large monochromatic components in expansive hypergraphs
• Cycle Ramsey numbers for random graphs
• On-line size Ramsey number for monotone k-uniform ordered paths with uniform looseness
• Multicolor Size-Ramsey Number of Cycles