A sub-exponential transition of the chromatic generalized Ramsey numbers

Abstract

A simple graph-product type construction shows that for all natural numbers $r\ge q$, there exists an edge-coloring of the complete graph on $2^r$ vertices using $r$ colors where the graph consisting of the union of arbitrary $q$ color classes has chromatic number $2^q$. We show that for each fixed natural number $q$, if there exists an edge-coloring of the complete graph on $n$ vertices using $r$ colors where the graph consisting of the union of arbitrary $q$ color classes has chromatic number at most $2^q-1$, then $n$ must be sub-exponential in $r$. This answers a question of Conlon, Fox, Lee, and Sudakov.