Problem 1105

Erdős Problem #1105: declared status 'proved'. Formalized: yes. The anti-Ramsey number $\mathrm{AR}(n,G)$ is the maximum possible number of colours in which the edges of $K_n$ can be coloured without creating a rainbow copy of $G$ (i.e. one in which all edges have different colours). Let $C_k$ be the cycle on $k$ vertices. Is it true that$$\mathrm{AR}(n,C_k)=\left(\frac{k-2}{2}+\frac{1}{k-1}\right)n+O(1)?$$Let $P_k$ be the path on $k$ vertices and $\ell=\lfloor\frac{k-1}{2}\rfloor$. If $n\geq k\geq 5$ then is $\mathrm{AR}(n,P_k)$ equal to$$\max\left(\binom{k-2}{2}+1, \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\right)$$where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise? Current best: In this paper they announced proofs of the claimed formula for $\mathrm{AR}(n,P_k)$ for $n\geq \frac{5}{4}k+C$ for some large constant $C$, and also for all $n\geq k$ if $k$ is sufficiently large, but these never appeared. Simonovits and S\'{o}s [SiSo84] published a proof that the claimed formula for $\mathrm{AR}(n,P_k)$ is true for $n\geq ck^2$ for some constant $c>0$. A proof of the formula for $\mathrm{AR}(n,P_k)$ for all $n\geq k\geq 5$ has been announced by Yuan [Yu21] References [ESS75] Erd\H{o}s, P. Prize: no. Tags: graph theory, ramsey theory.