On some multicolour Ramsey properties of random graphs

الأصل · EN

The size-Ramsey number 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ₙ on n vertices. In particular, we show that 5n/2-15/2 ≤ R(Pₙ) ≤ 74n for n sufficiently large. (The upper bound uses expansion properties of random d-regular graphs.) This improves the previous lower bound, R(Pₙ) ≥ (1+√2)n-O(1), due to Bollobás, and the upper bound, R(Pₙ) ≤ 91n, due to Letzter. Next we study long monochromatic paths in edge-coloured random graph G(n,p) with pn → ∞. Let α> 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-α)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-α)n, which is also optimal. In general, we prove that for r≥ 4 a.a.s.any r-edge colouring of G(n,p) yields a monochromatic path of length (1/r-α)n. We also consider a related problem and show that for any r ≥ 2, a.a.s.any r-edge colouring of G(n,p) yields a monochromatic connected subgraph on (1/(r-1)-α)n vertices, which is also tight.