Set-Coloring Ramsey Numbers and Error-Correcting Codes Near the Zero-Rate Threshold
David Conlon, Jacob Fox, Huy Tuan Pham, Yufei Zhao · IEEE Transactions on Information Theory · 2023
For positive integersn, r, swithr>s, the setcoloring Ramsey numberR(n; r, s) is the minimumNsuch that if every edge of the complete graphKNreceives a set ofscolors from a palette ofrcolors, then there is a subset ofnvertices where all of the edges between them receive a common color. Ifnis fixed ands/ris less than and bounded away from 1 - 1/n-1, thenR(n; r, s) is known to grow exponentially in r, while ifs/ris greater than and bounded away from 1 - 1/n-1, thenR(n; r, s) is bounded. Here we prove bounds forR(n; r, s) in the intermediate range wheres/ris close to 1 - 1/n-1 by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.