On the maximal anti-Ramsey problem of Burr, Erdős, Graham, and Sós for $P_4$

Abstract

Given a graph $L$, the maximal anti-Ramsey function $\chiS(n,e,L)$ denotes the minimum integer $\chiS$ for which there exists an $n$-vertex graph $G$ with at least $e$ edges admitting an edge-coloring with $\chiS$ colors in which each copy of $L$ in $G$ is rainbow. In 1989, Burr, Erdős, Graham, and Sós posed the following problem: Is it true that for all $\epsilon >0$, there exists $c(\epsilon )>0$ such that for all sufficiently large $n$, $ \chiS\left(n,\binom{n}{2}-\lfloor n^{2-ε}\rfloor,P_4\right)>c(ε)n^2. $ Very recently, Li, Ning, and Xie gave a negative answer to the problem for all $0<\epsilon <1/2$. In this note, we establish that a quadratic lower bound holds in the complementary regime $\epsilon \ge 1/2$. More specifically, we prove that for all $\epsilon \ge 1/2$ and sufficiently large $n$, there is an absolute constant $c>0$ such that $ \chiS\left(n,\binom{n}{2}-\lfloor n^{2-ε}\rfloor,P_4\right)>c n^2. $

7 pages