2016/04/18 by Hàn, H., Retter, T., Rödl, V. +1 · 1 citation
#05C55 (primary) #05D10 (secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1604.05066
A question of Erdős asks if for every pair of positive integers r and k, there exists a graph H having \textrmgirth(H)=k and the property that every r-colouring of the edges of H yields a monochromatic cycle Ck. The existence of such graphs was confirmed by the third author and Ruciński. We consider the related numerical problem of determining the smallest such graph with this property. We show that for integers r and k, there exists a graph H on R10k2 k15k3 vertices (where R = R(Ck;r) is the r-colour Ramsey number for the cycle Ck) having \textrmgirth(H)=k and the Ramsey property that every r-colouring of E(H) yields a monochromatic Ck. Two related numerical problems regarding arithmetic progressions in sets and cliques in graphs are also considered.