Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

amsey-type numbers involving graphs and hypergraphs with large girt

Full text
Author(s):
Han, Hiep [1] ; Retter, Troy [2] ; Roedl, Vojtech [2] ; Schacht, Mathias [3]
Total Authors: 4
Affiliation:
[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
Total Affiliations: 3
Document type: Journal article
Source: COMBINATORICS PROBABILITY & COMPUTING; v. 30, n. 5, p. 722-740, SEP 2021.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 10/16526-3 - Quasi-random hypergraphs and spanning subhypergraph containment
Grantee:Hiep Han
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 13/11353-1 - Degenerate extremal problems for random discrete structures
Grantee:Hiep Han
Support Opportunities: Scholarships abroad - Research Internship - Post-doctor