Rainbow common graphs must be forests
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}].
- Anti-Ramsey Multiplicities
- Graph Theory and Additive Combinatorics
- Large networks and graph limits
- Mathematics of Ramsey theory. Collected papers of the Prague symposium on graph theory held in Prague, Czechoslovakia
- On the local approach to Sidorenko's conjecture
- On the minimum number of monochromatic generalized Schur triples
- Rainbow solutions to the Sidon equation
- Rainbow triangles in three-colored graphs
- Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
- Szemerédi's lemma for the analyst
- The anti-Ramsey problem for the Sidon equation
This page was built for publication: Rainbow common graphs must be forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6925706)
