On Almost Gallai Colorings in Complete Graphs

We investigate a rainbow analog of the Ruzsa–Szemerédi problem. For , we say that a coloring of is almost ‐Gallai if no two rainbow ‐cliques share an edge. Motivated by a lemma of Berkowitz on bounding the modulus of the characteristic function of clique counts in random graphs, we study the maximum number of rainbow ‐cliques in an almost ‐Gallai coloring of . For every , we show that . For , surprisingly, the behavior is substantially different. Our main result establishes that which gives the first nontrivial improvements over the simple lower and upper bounds. Our proof combines various applications of the probabilistic method and a generalization of the edge‐isoperimetric inequality for the hypercube.