Two problems of Burr, Erd\H os, Graham, and S\'os on maximal anti-Ramsey functions for $P_4$
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
Burr, Erd\H os, Graham, and Sós introduced the maximal anti-Ramsey function $\chi_{\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$, $\chi_{\mathrm{S}}\left(n,\lfloor un \rfloor,P_4 \right)<Cu$ holds for all sufficiently large $n$? (ii) Is it true that for all $\epsilon >0$, there exists $c(\epsilon)>0$ such that for all sufficiently large $n$, \\ $\chi_{\mathrm{S}}\left(n,\binom{n}{2}-\lfloor n^{2-\epsilon} \rfloor,P_4 \right)>c(\epsilon)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<\epsilon<1/2$ there exist~$\gamma>0$ and arbitrarily large~$n$ such that~$\chi_{\mathrm{S}}\bigl(n,\tbinom{n}{2}-\lfloor n^{2-\epsilon}\rfloor,P_4\bigr)\;\le\; n^{2-\gamma}=o(n^{2}).$