Ramsey numbers with prescribed rate of growth

Matías Pavez-Signé, Simón Piga, Nicolás Sanhueza-Matamala

Research output: Working paper/PreprintPreprint

20 Downloads (Pure)

Abstract

Let R(G) be the two-colour Ramsey number of a graph G. In this note, we prove that for any non-decreasing function n≤f(n)≤R(Kn), there exists a sequence of connected graphs (Gn)n∈N, with |V(Gn)|=n for all n≥1, such that R(Gn)=Θ(f(n)). In contrast, we also show that an analogous statement does not hold for hypergraphs of uniformity at least 5.
We also use our techniques to answer a question posed by DeBiasio about the existence of sequences of graphs whose 2-colour Ramsey number is linear whereas their 3-colour Ramsey number has superlinear growth.
Original languageEnglish
Publication statusPublished - 12 Sept 2022

Keywords

  • math.CO

Fingerprint

Dive into the research topics of 'Ramsey numbers with prescribed rate of growth'. Together they form a unique fingerprint.

Cite this