A lower bound for set-colouring Ramsey numbers

EUROCOMB’23

Lucas Aragão Maurício Collares João Pedro Marciano Taísa Martins Robert Morris

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-007

PDF
Abstract
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ëte, 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$.

Pages:
50–56
References

N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica, 25 (2005), 125-141.
https://doi.org/10.1007/s00493-005-0011-9

D. Conlon, J. Fox, X. He, D. Mubayi, A. Suk and J. Verstraëte, Set-coloring Ramsey numbers via codes, arXiv:2206.11371

D. Conlon, J. Fox, X. He, D. Mubayi, A. Suk and J. Verstraëte, Hypergraph Ramsey numbers of cliques versus stars, Random Structures Algorithms, to appear, arXiv:2210.03545

D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, Surveys in Combinatorics, 424 (2015), 49-118.
https://doi.org/10.1017/CBO9781316106853.003

P. Erdős, A. Hajnal and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci., 16 (1965), 93-196.
https://doi.org/10.1007/BF01886396

P. Erdős and A. Szemerédi, On a Ramsey type theorem, Period Math. Acad., 2 (1972), 295-299.
https://doi.org/10.1007/BF02018669

X. He and Y. Wigderson, Multicolor Ramsey numbers via pseudorandom graphs, Electron. J. Combin., 27 (2020), Article No. P1.32.
https://doi.org/10.37236/9071

D. Mubayi and J. Verstraëte, A note on pseudorandom Ramsey graphs, J. Eur. Math. Soc., to appear, arXiv:1909.01461.

W. Sawin, An improved lower bound for multicolor Ramsey numbers and a problem of Erdős, J. Combin. Theory Ser. A, 188 (2022), Paper No. 105579, 11 pp.
https://doi.org/10.1016/j.jcta.2021.105579

Y. Wigderson, An improved lower bound on multicolor Ramsey numbers, Proc. Amer. Math. Soc., 149 (2021), 2371-2374.
https://doi.org/10.1090/proc/15447

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Lucas Aragão, Maurício Collares, João Pedro Marciano, Taísa Martins, Robert Morris

PDF