amsey-type numbers involving graphs and hypergraphs with large girt

Autor(es)

Han, Hiep ^[1] ; Retter, Troy ^[2] ; Roedl, Vojtech ^[2] ; Schacht, Mathias ^[3]

Afiliação do(s) autor(es)

^[1] Univ Santiago Chile, Dept Matemat & Ciencia Computat, Santiago - Chile

^[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA

^[3] Univ Hamburg, Fachbereich Math, Hamburg - Germany

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICS PROBABILITY & COMPUTING; v. 30, n. 5, p. 722-740, SEP 2021.
• Citações Web of Science: 0

Resumo

Erdos 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 C-k. The existence of such graphs H was confirmed by the third author and Rucinski. 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-10k2 k(15k3) 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. (AU)

• Processo FAPESP: 10/16526-3 - Hipergrafos quase-aleatórios e imersão de subhipergrafos geradores
• Beneficiário: Hiep Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/11353-1 - Problemas extremais degenerados para estruturas aleatórias discretas
• Beneficiário: Hiep Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado