Georgia Institute of Technology College of Sciences

What is the maximum number of rainbow triangles in an edge-colored graph with m edges and r colors? Using entropic techniques, we prove an upper bound of C(r)*m^{3/2} rainbow triangles — the explicit constant C(r) we derive is best possible whenever there is an affine plane of order r-1. We also show that constructions attaining at least (C(r)−eps)*m^{3/2} rainbow triangles must exhibit an affine plane structure for sufficiently small epsilon, which further improves the upper bound if no such affine plane exists. Lastly, we consider the problem of counting properly edge-colored copies of K_d with d≥4. Surprisingly the optimal construction is the same for any d≥4, but differs from the affine plane construction that was optimal for d=3.