Density of rainbow triangles and properly colored $K_4$'s

Abstract

We establish a sharp upper bound on the number of properly $3$-edge-colored $K_4$'s in graphs with $R$ red, $G$ green and $B$ blue edges. We give a computer-free flag-algebra proof of this bound, and we also convert our proof into a classical counting proof and an entropy proof. Additionally, for every $k\ge 4$, for a fixed rainbow coloring $F$ of a complete graph $K_k$, we give a sharp upper bound on the number copies of $F$ in a $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$-edge-colored graph. Our proof of this result relies on a new flag-algebra version of Hölder's inequality. We also give a computer-free flag-algebra proof of the fact that a graph with $R$ red, $G$ green, and $B$ blue edges has at most $\sqrt{2RGB}$ rainbow triangles, which was originally proven by T.-W. Chao and H.-H. H. Yu using the entropy method. We also provide an even shorter entropy proof of their result.

arXiv comment15 pages + appendix