Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold
Preprint
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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Set-Coloring Ramsey Numbers via CodesStudia Scientiarum Mathematicarum Hungarica, 2024
- A lower bound for set‐coloring Ramsey numbersRandom Structures & Algorithms, 2023
- Linear Programming Bounds for Codes of Small SizeEuropean Journal of Combinatorics, 1997
- Krawtchouk polynomials and universal bounds for codes and designs in Hamming spacesIEEE Transactions on Information Theory, 1995
- Bounds for binary codes just outside the plotkin rangeInformation and Control, 1980
- Linear programming bounds for tree codes (Corresp.)IEEE Transactions on Information Theory, 1979
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977
- An Introduction to Algebraic and Combinatorial Coding Theory1976
- On the connection between chromatic number, maximal clique and minimal degree of a graphDiscrete Mathematics, 1974
- Binary codes with specified minimum distanceIEEE Transactions on Information Theory, 1960