We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A lower bound for set‐coloring Ramsey numbers.
- Authors
Aragão, Lucas; Collares, Maurício; Marciano, João Pedro; Martins, Taísa; Morris, Robert
- Abstract
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 $$.
- Subjects
RAMSEY numbers; COMPLETE graphs; RAMSEY theory; RANDOM graphs
- Publication
Random Structures & Algorithms, 2024, Vol 64, Issue 2, p157
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21173