On some multicolour Ramsey properties of random graphs

Abstract

The size-Ramsey number $\hat{R}(F)$ 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 two colours yields a monochromatic copy of $F$. In this paper, first we focus on the size-Ramsey number of a path $P_n$ on $n$ vertices. In particular, we show that $5n/2-15/2\le \hat{R}(P_n)\le 74n$ for $n$ sufficiently large. (The upper bound uses expansion properties of random $d$-regular graphs.) This improves the previous lower bound, $\hat{R}(P_n)\ge (1+\sqrt{2})n-O(1)$, due to Bollobás, and the upper bound, $\hat{R}(P_n)\le 91n$, due to Letzter. Next we study long monochromatic paths in edge-coloured random graph $G(n,p)$ with $pn\to \infty$. Let $\alpha >0$ be an arbitrarily small constant. Recently, Letzter showed that a.a.s.\ any $2$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(2/3-\alpha )n$, which is optimal. Extending this result, we show that a.a.s.\ any $3$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/2-\alpha )n$, which is also optimal. In general, we prove that for $r\ge 4$ a.a.s.\ any $r$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/r-\alpha )n$. We also consider a related problem and show that for any $r\ge 2$, a.a.s.\ any $r$-edge colouring of $G(n,p)$ yields a monochromatic connected subgraph on $(1/(r-1)-\alpha )n$ vertices, which is also tight.

17 pages

References in corpus (2)

• Path Ramsey number for random graphs
• Combinatorial theorems relative to a random set