Two problems of Burr, Erd\H os, Graham, and Sós on maximal anti-Ramsey functions for $P_4$

Abstract

Burr, Erd\H os, Graham, and Sós introduced the maximal anti-Ramsey function $\ddot{I}{‡}_{\mathrm{S}}(n,e,L)$, the minimum number of colors required over all $n$-vertex graphs with at least $e$ edges such that every copy of $L$ is rainbow. In \cite{BEGS1989}, they posed the following two problems: (i) Is it true that there exists $C>0$, such that for all $u\ge 1$, $\ddot{I}{‡}_{\mathrm{S}}\left(n,\lfloor un\rfloor ,P_4\right)<Cu$ holds for all sufficiently large $n$? (ii) Is it true that for all $\hat{I}\mu >0$, there exists $c(\hat{I}\mu )>0$ such that for all sufficiently large $n$, \\ $\ddot{I}{‡}_{\mathrm{S}}\left(n,\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\lfloor n^{2-\hat{I}\mu }\rfloor ,P_4\right)>c(\hat{I}\mu )n^2$? In this note, we give an affirmative answer to the first problem and a negative answer to the second problem. For the first problem, our proof uses a local density inequality with strong edge-colorings of odd Kneser graphs. In particular, our proof uses the characterization by Lužar, Máčajová, Å koviera, and Soták of~$k$-regular graphs whose strong chromatic index equals~$2k-1$. For the second result, our main tool is the construction of Alon, Moitra, and Sudakov. We show that for every fixed~$0<\hat{I}\mu <1/2$ there exist~${\hat{I}}^3>0$ and arbitrarily large~$n$ such that~$\ddot{I}{‡}_{\mathrm{S}}(n,(\genfrac{}{}{0ex}{}{n}{2})-\lfloor n^{2-\hat{I}\mu }\rfloor ,P_4)\le n^{2-{\hat{I}}^3}=o(n^2).$

10 pages