A lower bound for set‐coloring Ramsey numbers

• Published in: Random structures & algorithms 2024-03, Vol.64 (2), p.157-169
• Main Authors: Aragão, Lucas, Collares, Maurício, Marciano, João Pedro, Martins, Taísa, Morris, Robert
• Format: Article
• Language: English
• Subjects: Coloring; Lower bounds; probabilistic method; Ramsey theory; random graphs
• ISSN: 1042-9832; 1098-2418
• DOI: 10.1002/rsa.21173

The set‐coloring Ramsey number Rr,s(k)$$ {R}_{r,s}(k) $$ is defined to be the minimum n$$ n $$ such that if each edge of the complete graph Kn$$ {K}_n $$ is assigned a set of s$$ s $$ colors from {1,…,r}$$ \left\{1,\dots, r\right\} $$, then one of the colors contains a monochromatic clique of size k$$ k $$. The case s=1$$ s=1 $$ is the usual r$$ r $$‐color Ramsey number, and the case s=r−1$$ 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$$ s $$ were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstraëte, who showed that Rr,s(k)=2Θ(kr)$$ {R}_{r,s}(k)={2}^{\Theta (kr)} $$ if s/r$$ s/r $$ is bounded away from 0 and 1. In the range s=r−o(r)$$ s=r-o(r) $$, however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) coloring, and use it to determine Rr,s(k)$$ {R}_{r,s}(k) $$ up to polylogarithmic factors in the exponent for essentially all r$$ r $$, s$$ s $$, and k$$ k $$.