The Erdős-Gyárfás function $f(n,4,5)=\frac{5}{6}n+o(n)$ -- so Gyárfás was right

Abstract

A $(4,5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4,5)$-colorings of $K_n$ using $\frac{5}{6}n+o(n)$ colors. This settles a disagreement between Erdős and Gyárfás reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollobás and Erdős, and analyzed by Bohman, Frieze and Lubetzky.