On almost Gallai colourings in complete graphs

For $t\in \mathbb{N}$, we say that a colouring of $E(K_n)$ is $\mathit{\text{almost}}$ $t$-$\mathit{\text{Gallai}}$ if no two rainbow $t$-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 ${\tau }_t(n)$ of rainbow $t$-cliques in an almost $t$-Gallai colouring of $E(K_n)$. For every $t\ge 4$, we show that $n^{2-o(1)}\le {\tau }_t(n)=o(n^2)$. For $t=3$, surprisingly, the behaviour is substantially different. Our main result establishes that $$(\frac{1}{2}-o(1))n\log n\le {\tau }_3(n)=O(n^{\sqrt{2}}\log n),$$ which gives the first non-trivial improvements over the simple lower and upper bounds. Our proof combines various applications of the probabilistic method and a generalisation of the edge-isoperimetric inequality for the hypercube.