Name
Abstract | ||
|---|---|---|
Erdos asked if, for every pair of positive integers r and k, there exists a graph H having girth(H) = k and the property that every r-colouring of the edges of H yields a monochromatic cycle C-k. The existence of such graphs H was confirmed by the third author and Rucinski. We consider the related numerical problem of estimating the order of the smallest graph H with this property for given integers r and k. We show that there exists a graph H on R-10k2 k(15k3) vertices (where R = R(C-k; r) is the r-colour Ramsey number for the cycle C-k) having girth(H) = k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic C-k. Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1017/S0963548320000383 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 30 | 5 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiêp Hàn | 1 | 0 | 0.34 |
| Troy Retter | 2 | 5 | 2.20 |
| Vojtêch Rödl | 3 | 0 | 0.34 |
| Mathias Schacht | 4 | 0 | 0.68 |