A new variant of the Erdős-Gyárfás problem on $K_5$

Abstract

Motivated by an extremal problem on graph-codes that links coding theory and graph theory, Alon recently proposed a question aiming to find the smallest number $t$ such that there is an edge coloring of $K_n$ by $t$ colors with no copy of given graph $H$ in which every color appears an even number of times. When $H=K_4$, the question of whether $n^{o(1)}$ colors are enough, was initially emphasized by Alon. Through modifications to the coloring functions originally designed by Mubayi, and Conlon, Fox, Lee and Sudakov, the question of $K_4$ has already been addressed. Expanding on this line of inquiry, we further study this new variant of the generalized Ramsey problem and provide a conclusively affirmative answer to Alon's question concerning $K_5$.

Note added: Heath and Zerbib also proved the result on $K_5$ independently. arXiv:2307.01314