Ramsey-type numbers involving graphs and hypergraphs with large girth. (12th September 2021)

• Record Type: Journal Article
• Authors: Hàn, Hiêp; Retter, Troy; Rödl, Vojtêch; Schacht, Mathias
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 5(2021)
• Page Start: 722
• Page End: 740
• Publication Date: 2021-09-12
• Subjects: 05C55 -- 05D10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000383
• Languages: English
• ISSNs: 0963-5483

Abstract

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.