Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers
Abstract
The canonical Ramsey theorem establishes that for every positive integer t, there is a sufficiently large n such that every edge-colouring of a complete graph Kn contains a copy of Kt that is canonically coloured, i.e. monochromatic, rainbow, or lexicographic. In this paper we investigate two variations of this theorem. First, we study canonical Ramsey numbers in the multipartite hypergraph setting. We prove that in every edge-colouring of the 3-uniform complete hypergraph on at least t151t2 vertices, there always exists a canonically coloured copy of Kt, t, t(3). This estimate is sharp up to the constant in the exponent. Second, we explore off-diagonal canonical Ramsey numbers. Let $ER(a, b, c)$ denote the minimum number of vertices n required to guarantee a monochromatic Ka, a lexicographic Kb, or a rainbow Kc in every edge-colouring of the complete graph Kn. We establish sharp bounds for these numbers across different parameter regimes. Specifically, we prove that ER(a, b, c)≥ cΩ(ab) when c is sufficiently large relative to a, and that ER(a, b, c)≤ 2Ob(a) when b≥ 4 is a fixed constant and c≤ a. Finally, we analyse the behaviour of the function when avoiding lexicographic triangles (i.e. b=3), showing that ER(a, 3, c)≤ (a−1)(c−2)+O(c6).
Related
BibTeX
@misc{gvozdic2026sharp,
title = {{Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers}},
author = {Strahinja Gvozdić and Zach Hunter and Aleksa Milojević and Benny Sudakov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03358},
eprint = {2610.03358},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03358},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers
AU - Strahinja Gvozdić
AU - Zach Hunter
AU - Aleksa Milojević
AU - Benny Sudakov
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03358
UR - https://arxiv.org/abs/2610.03358
AB - The canonical Ramsey theorem establishes that for every positive integer t, there is a sufficiently large n such that every edge-colouring of a complete graph K_n contains a copy of K_t that is canonically coloured, i.e. monochromatic, rainbow, or lexicographic. In this paper we investigate two variations of this theorem. First, we study canonical Ramsey numbers in the multipartite hypergraph setting. We prove that in every edge-colouring of the 3-uniform complete hypergraph on at least t^151t^2 vertices, there always exists a canonically coloured copy of K_t, t, t^(3). This estimate is sharp up to the constant in the exponent. Second, we explore off-diagonal canonical Ramsey numbers. Let $ER(a, b, c)$ denote the minimum number of vertices n required to guarantee a monochromatic K_a, a lexicographic K_b, or a rainbow K_c in every edge-colouring of the complete graph K_n. We establish sharp bounds for these numbers across different parameter regimes. Specifically, we prove that ER(a, b, c)≥ c^Ω(ab) when c is sufficiently large relative to a, and that ER(a, b, c)≤ 2^O_b(a) when b≥ 4 is a fixed constant and c≤ a. Finally, we analyse the behaviour of the function when avoiding lexicographic triangles (i.e. b=3), showing that ER(a, 3, c)≤ (a−1)(c−2)+O(c^6).
ER -