Lower Bounds on the Erdős-Gyárfás Problem

Abstract: Given positive integers $p$ and $q$, a $(p,q)$-coloring of the complete graph $K_n$ is an edge-coloring in which every $p$-clique receives at least $q$ colors. Erdős and Shelah posed the question of determining $f(n,p,q)$, the minimum number of colors needed for a $(p,q)$-coloring of $K_n$. Recently, Pohoata and Sheffer introduced the color energy technique to find lower bounds on this function. In this talk, we will present new lower bounds for several families of $(p,q)$ which we obtain by further developing their method.

Back to Search Research Symposium Abstracts