Set-Coloring Ramsey Numbers and Error-Correcting Codes Near the Zero-Rate Threshold
-
1.
California Institute of Technology
-
2.
Stanford University
-
3.
Massachusetts Institute of Technology
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 KN 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 sr is less than and bounded away from 1−1n−1 , then R(n;r,s) is known to grow exponentially in r , while if sr is greater than and bounded away from 1−1n−1 , then R(n;r,s) is bounded. Here we prove bounds for R(n;r,s) in the intermediate range where sr is close to 1−1n−1 by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.
Copyright and License
© 2023 IEEE.
Acknowledgement
The authors would like to thank Xiaoyu He, Dhruv Mubayi, Andrew Suk, and Jacques Verstraëte for helpful conversations. They would also like to thank Maria Axenovich for bringing the work of Yen Hoang Le to their attention.
Funding
The work of David Conlon was supported by the NSF under Award DMS-2054452. The work of Jacob Fox was
supported in part by a Packard Fellowship and in part by the NSF under Awards DMS-1953990 and DMS-2154129. The work of Huy Tuan Pham was supported in part by a Clay Fellowship and in part by a Two Sigma
Fellowship. The work of Yufei Zhao was supported by the NSF under Career Award DMS-2044606, in part by a Sloan Research Fellowship, and in part by an MIT Solomon Buchsbaum Fund.
Additional details
Related works
- Is new version of
- Discussion Paper: arXiv:2305.14132 (arXiv)
Funding
- National Science Foundation
- DMS-2054452
- Packard Fellowship
- National Science Foundation
- DMS-1953990
- National Science Foundation
- DMS-2154129
- Clay Fellowship
- Two Sigma Fellowship
- National Science Foundation
- DMS-2044606
- Sloan Research Fellowship
- MIT Solomon Buchsbaum Fund
Dates
- Submitted
-
2023-05-23
- Accepted
-
2023-10-09
- Available
-
2023-10-26Published online
- Available
-
2024-05-21Date of current version