1. Ramsey-type numbers involving graphs and hypergraphs with large girth.
- Author
-
Hàn, Hiêp, Retter, Troy, Rödl, Vojtêch, and Schacht, Mathias
- Subjects
RAMSEY numbers ,HYPERGRAPHS ,ARITHMETIC series ,INTEGERS - 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 R10k ; k2 15k vertices (where R = R(C3 k ; 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. [ABSTRACT FROM AUTHOR]- Published
- 2021
- Full Text
- View/download PDF