On almost Gallai colourings in complete graphs

Abstract

For $t\in \mathbb{N}$, we say that a colouring of $E(K_n)$ is $\text{almost}$ $t$-$\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 $\ddot{I}{„}_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 \ddot{I}{„}_t(n)=o(n^2)$. For $t=3$, surprisingly, the behaviour is substantially different. Our main result establishes that $$\left(\frac{1}{2}-o(1)\right)n\log n\le \ddot{I}{„}_3(n)=O\left(n^{\sqrt{2}}\log n\right),$$ 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.

23 pages