论文标题
通过代码设置颜色的Ramsey号码
Set-coloring Ramsey numbers via codes
论文作者
论文摘要
For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the它们之间的边缘会获得共同的颜色。特别是，$ s = 1 $的情况对应于经典的多色拉姆齐号。如果$ r（n; r，s）= 2^{θ（nr）} $，我们证明了$ r（n; r，s）$上的一般上限和下限，如果$ s/r $从$ 0 $和$ 1 $限制。上限扩展了ErdőS和Szemerédi的旧结果，他们处理了该案例$ S = R-1 $，而下限漏洞利用了与错误校正的代码的连接。我们还研究了超图的类似问题。
For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.
