Set-Coloring Ramsey Numbers and Error-Correcting Codes Near the Zero-Rate Threshold

Authors:
Publisher website
Google Scholar
Abstract
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 a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac {s}{r}$ is less than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is known to grow exponentially in $r$ , while if $\frac {s}{r}$ is greater than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac {s}{r}$ is close to $1 - \frac {1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.
Funding Information
  • NSF (DMS-2054452)
  • Packard Fellowship
  • NSF (DMS-1953990, DMS-2154129)
  • Clay Fellowship
  • Two Sigma Fellowship
  • NSF (DMS-2044606)
  • Sloan Research Fellowship
  • MIT Solomon Buchsbaum Fund

This publication has 9 references indexed in Scilit: