Entropy Methods for Rainbow Triangles and Properly Colored Cliques

Our work begins with the following question about rainbow triangles, inspired by the joints problem: If G is a graph with m edges, each colored with one of r colors, then what is the maximum number of rainbow triangles G can have (as a function of m)? In 2023, Chao and Yu answered this question for r=3, showing that the optimal construction is a blowup of a properly edge-colored K_4, by analyzing the entropy of vertices sampled in a somewhat complicated manner. Two more proofs of this fact have appeared in the literature since; however, like Chao and Yu's original proof, they are specific to the case r=3. In this talk, we'll prove an upper bound for all r that is tight whenever there is a projective plane of order r-1. For any fixed d>=4, we also upper-bound the number of properly colored copies of K_d. Surprisingly the optimal construction is the same for all d>=4, but differs from the optimal construction for d=3. 

One key entropic tool we use is the mixture lemma of Chao and Yu, which informally allows us to analyze the entropy of a mixture of random variables X_1, ..., X_k, i.e., a random variable obtained by sampling X_i with probability p_i. This lemma is a very general-purpose tool and I hope to convey some intuition on how it can be used more generally. All results are joint with Ting-Wei Chao and Hung-Hsun Hans Yu.