Size and Degree Anti-Ramsey Numbers

A copy of a graph H in an edge colored graph G is called rainbow if all edges of H have distinct colors. The size anti-Ramsey number of H, denoted by ARs(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$AR_s(H)$$\end{document}, is the smallest number of edges in a graph G such that any of its proper edge-colorings contains a rainbow copy of H. We show that ARs(Kk)=Θ(k6/log2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$AR_s(K_k) = \varTheta (k^6 / \log ^2 k)$$\end{document}. This settles a problem of Axenovich, Knauer, Stumpp and Ueckerdt. The proof is probabilistic and suggests the investigation of a related notion, which we call the degree anti-Ramsey number of a graph.