Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold

arXiv2305.14132MaRDI QIDQ6437673FDOQ6437673

Authors: David Conlon, Jacob Fox, Huy-Tuan Pham, Yufei Zhao 

Publication date: 23 May 2023

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 $fracsr$ is less than and bounded away from $1-frac1n-1$, then $R(n;r,s)$ is known to grow exponentially in $r$, while if $fracsr$ is greater than and bounded away from $1-frac1n-1$, then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $fracsr$ is close to $1-frac1n-1$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

This page was built for publication: Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437673)