Set-Coloring Ramsey Numbers via Codes
David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques VerstraΓ«te Β· Studia Scientiarum Mathematicarum Hungarica Β· 2024
For positive integers π, π, π with π > π , the set-coloring Ramsey number π (π; π, π ) is the minimum π such that if every edge of the complete graph πΎπ receives a set of π colors from a palette of π colors, then there is guaranteed to be a monochromatic clique on π vertices, that is, a subset of π vertices where all of the edges between them receive a common color. In particular, the case π = 1 corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on π (π; π, π ) which imply that π (π; π, π ) = 2Ξ(ππ) if π /π is bounded away from 0 and 1. The upper bound extends an old result of ErdΕs and SzemerΓ©di, who treated the case π = π β 1, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.