Details

Autor(en) / Beteiligte

• Das, Shagnik
• Treglown, Andrew

Titel

Ramsey properties of randomly perturbed graphs: cliques and cycles

Ist Teil von

• Combinatorics, probability & computing, 2020-11, Vol.29 (6), p.830-867

Ort / Verlag

Cambridge: Cambridge University Press

Erscheinungsjahr

2020

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Abstract Given graphs H 1 , H 2 , a graph G is ( H 1 , H 2 ) -Ramsey if, for every colouring of the edges of G with red and blue, there is a red copy of H 1 or a blue copy of H 2 . In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs . This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability ( K 3 , K t ) -Ramsey (for t ≽ 3). They also raised the question of generalizing this result to pairs of graphs other than ( K 3 , K t ). We make significant progress on this question, giving a precise solution in the case when H 1 = K s and H 2 = K t where s , t ≽ 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the ( K 3 , K t ) -Ramsey question. Moreover, we give bounds for the corresponding ( K 4 , K t ) -Ramsey question; together with a construction of Powierski [37] this resolves the ( K 4 , K 4 ) -Ramsey problem. We also give a precise solution to the analogous question in the case when both H 1 = C s and H 2 = C t are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalization of the Krivelevich, Sudakov and Tetali [30] result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability ( C s , K t ) -Ramsey (for odd s ≽ 5 and t ≽ 4). To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.