Graphs without rainbow cliques of orders four and five

Abstract

Let ${\mathcal{G}}_n^k=\{G_1,G_2,\dots ,G_k\}$ be a multiset of graphs on vertex set $[n]$ and let $F$ be a fixed graph with edge set $F=\{e_1,e_2,\dots ,e_m\}$ and $k\ge m$. We say ${\mathcal{G}}_n^k$ is rainbow $F$-free if there is no $\{i_1,i_2,\dots ,i_m\}\subseteq [k]$ satisfying $e_j\in G_{i_j}$ for every $j\in [m]$. Let $\ex_k(n,F)$ be the maximum ${\sum }_{i=1}^k|G_i|$ among all the rainbow $F$-free multisets ${\mathcal{G}}_n^k$. Keevash, Saks, Sudakov, and Verstraëte (2004) determined the exact value of $\ex_k(n, K_r)$ when $n$ is sufficiently large and proposed the conjecture that the results remain true when $n\ge C{r}^2$ for some constant $C$. Recently, Frankl (2022) confirmed the conjecture for $r=3$ and all possible values of $n$. In this paper, we determine the exact value of $\ex_k(n, K_r)$ for $n\ge r-1$ when $r=4$ and $5$, i.e. the conjecture of Keevash, Saks, Sudakov, and Verstraëte is true for $r\in \{4,5\}$.