Rainbow common graphs must be forests (Q6925706)

A graph \(H\) is common if the number of copies of \(H\) in any \(n\) vertex graph \(G\) and its complement \(\overline{G}\) is minimized asymptotically by the Erdős-Renyi random graph \(G(n, 1/2)\). This research considers the problem of maximizing the number of rainbow copies of \(H\), where all edges have distinct colors, instead of minimizing the number of monochromatic copies of \(H\). For a graph \(H\) and an integer \(r \ge |E(G)|\), \(H\) is \(r\)-rainbow common if the maximum number of rainbow copies of \(H\) in an \(r\)-coloring of edges of the complete graph \(K_n\) is achieved asymptotically by coloring each edge independently with a uniform random color. Otherwise, \(H\) is \(r\)-rainbow uncommon. Settling the cycle conjecture in [\textit{J. De Silva} et al., Australas. J. Comb. 73, Part 2, 357--371 (2019; Zbl 1411.05086)], it is proved that every graph containing a cycle is rainbow uncommon. This also extends a former result of [\textit{P. Erdős} and \textit{A. Hajnal}, ``On Ramsey like theorems, problems and results'', in: Combinatorics. Proceedings of the conference on combinatorial mathematics held at the Mathematical Institute, Oxford, 3--7 July, 1972. Southend-on-Sea: The Institute of Mathematics and its Applications. 123--140 (1972), \url{https://users.renyi.hu/~p_erdos/1972-10.pdf}].