Partite Saturation of Complete Graphs

We study the problem of determining sat$(n,k,r)$, the minimum number of edges in a $k$-partite graph $G$ with $n$ vertices in each part such that $G$ is $K_r$-free but the addition of an edge joining any two nonadjacent vertices from different parts creates a $K_r$. Improving recent results of Ferrara, Jacobson, Pfender, and Wenger, and generalizing a recent result of Roberts, we show that sat$(n,k,r) = \alpha(k,r)n + O(1)$ as $n \rightarrow \infty$. Moreover, for every $3 \leq r \leq k$ we prove that $k(2k - 4) \leq \alpha(k,r) \leq (k-1)(4 r - \ell -6),$ where $\ell = \mbox{min}\{k, 2r-3\}$, and show that the lower bound is tight for infinitely many values of $r$ and every $k\geq 2r-1$. This allows us to prove that, for these values, sat$(n,k,r) = k(2r-4)n + O(1)$ as $n \rightarrow \infty$. Along the way, we disprove a conjecture and answer a question of the first set of authors mentioned above.