New Upper Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers

Abstract

A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ which assigns at least $q$ colors to each $p$-clique. The problem of determining the minimum number of colors, $f(n,p,q)$, needed to give a $(p,q)$-coloring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$. The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in \{4,5\}$, each of which was proved by giving a deterministic construction which combined a $(p,p-1)$-coloring using few colors with an algebraic coloring. In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colorings of $p$-cliques with $p-1$ colors which can appear in our modified version of the $(p,p-1)$-coloring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$-colorings, which would otherwise make this problem intractable for large values of $p$. In addition, we generalize our algebraic coloring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$.