Ramsey-type numbers involving graphs and hypergraphs with large girth. (12th September 2021) - Hàn, Hiêp; Retter, Troy; Rödl, Vojtêch; Schacht, Mathias
Abstract: Erdős asked if, for every pair of positive integers g 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 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 R 10 k 2 ; k 15 k 3 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.