Loading...
Please wait, while we are loading the content...
Similar Documents
Ramsey properties of randomly perturbed graphs: cliques and cycles
| Content Provider | Scilit |
|---|---|
| Author | Das, Shagnik Treglown, Andrew |
| Copyright Year | 2020 |
| 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. |
| Related Links | https://www.cambridge.org/core/services/aop-cambridge-core/content/view/C368E54DCC99B5C0651FE8403BB05FEF/S0963548320000231a.pdf/div-class-title-ramsey-properties-of-randomly-perturbed-graphs-cliques-and-cycles-div.pdf |
| Ending Page | 867 |
| Page Count | 38 |
| Starting Page | 830 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548320000231 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 6 |
| Volume Number | 29 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2020-11-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Applied Mathematics Mathematical Physics Random Graph High Probability Resulting Graph |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
