Ramsey-Type Numbers Involving Graphs and Hypergraphs with Large Girth

Erdős 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 Ck. The existence of such graphs H was confirmed by the third author and Ruciński. 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 R10k2k15k3 vertices (where R=R(Ck; r) is the r-colour Ramsey number for the cycle Ck) having girth(H)=k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic Ck. Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered. © The Author(s), 2021. Published by Cambridge University Press.