Loading…
A lower bound for set‐coloring Ramsey numbers
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...
Saved in:
Published in: | Random structures & algorithms 2024-03, Vol.64 (2), p.157-169 |
---|---|
Main Authors: | , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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 $$. |
---|---|
ISSN: | 1042-9832 1098-2418 |
DOI: | 10.1002/rsa.21173 |