Aragão Lucas, Collares Maurício, Marciano João Pedro, Martins Taísa, Morris Robert
Instituto de Matemática Pura e Aplicada Rio de Janeiro Brazil.
Institute of Discrete Mathematics Graz University of Technology Graz Austria.
Random Struct Algorithms. 2024 Mar;64(2):157-169. doi: 10.1002/rsa.21173. Epub 2023 Aug 3.
The set-coloring Ramsey number is defined to be the minimum such that if each edge of the complete graph is assigned a set of colors from , then one of the colors contains a monochromatic clique of size . The case is the usual -color Ramsey number, and the case 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 were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstraëte, who showed that if is bounded away from 0 and 1. In the range , however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) coloring, and use it to determine up to polylogarithmic factors in the exponent for essentially all , , and .
集染色拉姆齐数被定义为最小的(n)，使得如果完全图(K_n)的每条边都被赋予一组来自([k])的(k)种颜色，那么其中一种颜色包含一个大小为(r)的单色团。(k = 2)的情况是通常的(2 -)染色拉姆齐数，(k = 3)的情况在1965年由埃尔德什、哈伊纳尔和拉多研究过，1972年由埃尔德什和塞梅雷迪研究过。对于一般的(k)，第一个重要结果直到最近才由康伦、福克斯、贺、穆巴伊、苏克和韦斯特拉埃特得到，他们表明如果(k)远离(0)和(1)，则(R^{(k)}(r) \leq (1 + o(1))r^{k - 1})。然而，在(2 < k < r)的范围内，他们的上下界有显著差异。在本笔记中，我们引入一种新的（随机）染色，并使用它来确定对于基本上所有的(k)、(r)和(n)，在指数中至多相差多对数因子的(R^{(k)}(r))。
