Phase transitions of the Erdős-Gyárfás function

Abstract

Given positive integers $p,q$. For any integer $k\ge 2$, an edge coloring of the complete $k$-graph $K_n^{(k)}$ is said to be a $(p,q)$-coloring if every copy of $K_p^{(k)}$ receives at least $q$ colors. The Erdős-Gyárfás function $f_k(n,p,q)$ is the minimum number of colors that are needed for $K_n^{(k)}$ to have a $(p,q)$-coloring. Conlon, Fox, Lee and Sudakov (\emph{IMRN, 2015}) conjectured that for any positive integers $p,k$ and $i$ with $k\ge 3$ and $1\le i<k$, $f_k(n,p,(\genfrac{}{}{0ex}{}{p-i}{k-i}))=({\log }_{(i-1)}n{)}^{o(1)}$, where ${\log }_{(i)}n$ is an iterated $i$-fold logarithm in $n$. It has been verified to be true for $k=3,p=4,i=1$ by Conlon et. al (\emph{IMRN, 2015}), for $k=3,p=5,i=2$ by Mubayi (\emph{JGT, 2016}), and for all $k\ge 4,p=k+1,i=1$ by B. Janzer and O. Janzer (\emph{JCTB, 2024}). In this paper, we give new constructions and show that this conjecture holds for infinitely many new cases, i.e., it holds for all $k\ge 4$, $p=k+2$ and $i=k-1$.

11 pages