A lower bound for set-colouring Ramsey numbers

The set-colouring Ramsey number \(R_{r,s}(k)\) is defined to be the minimum \(n\) such that if each edge of the complete graph \(K_n\) is assigned a set of \(s\) colours from \(\{1,\ldots,r\}\), then one of the colours contains a monochromatic clique of size \(k\). The case \(s = 1\) is the usual \(...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-01
Main Authors: Lucas Aragão, Collares, Maurício, João Pedro Marciano, Martins, Taísa, Morris, Robert
Format: Article
Language:English
Subjects:
Coloring
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The set-colouring Ramsey number \(R_{r,s}(k)\) is defined to be the minimum \(n\) such that if each edge of the complete graph \(K_n\) is assigned a set of \(s\) colours from \(\{1,\ldots,r\}\), then one of the colours contains a monochromatic clique of size \(k\). The case \(s = 1\) is the usual \(r\)-colour Ramsey number, and the case \(s = r - 1\) was studied by Erdős, Hajnal and Rado in 1965, and by Erdős and Szemerédi in 1972. The first significant results for general \(s\) were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstra\"ete, who showed that \(R_{r,s}(k) = 2^{\Theta(kr)}\) if \(s/r\) is bounded away from \(0\) and \(1\). In the range \(s = r - o(r)\), however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) colouring, and use it to determine \(R_{r,s}(k)\) up to polylogarithmic factors in the exponent for essentially all \(r\), \(s\) and \(k\).
ISSN:2331-8422