Multicolor $K_r$-Tilings with High Discrepancy

Abstract

We study the minimum degree threshold $\hat{I}{´}_{r,q}$ guaranteeing the existence of $K_r$-tilings of high discrepancy in any $q$-edge-coloring. Balogh, Csaba, Pluhár and Treglown handled the 2-color case, proving that $\hat{I}{´}_{r,2}=\frac{r}{r+1}$ for all $r\ge 3$. Here we determine $\hat{I}{´}_{r,q}$ for all $q$ large enough, namely $q\ge \left(\genfrac{}{}{0ex}{}{r}{2}\right)$. For example, we show that for $r\ge 4$, $\hat{I}{´}_{r,q}=\frac{r}{r+1}$ for $\left(\genfrac{}{}{0ex}{}{r}{2}\right)\le q\le \left(\genfrac{}{}{0ex}{}{r+1}{2}\right)$ and $\hat{I}{´}_{r,q}=\frac{r-1}{r}$ for $q\ge \left(\genfrac{}{}{0ex}{}{r+1}{2}\right)+2$. Thus, $\hat{I}{´}_{r,q}$ has a phase transition at $q=\left(\genfrac{}{}{0ex}{}{r+1}{2}\right)$, where it drops from $\frac{r}{r+1}$ and then stabilizes at the existence threshold $\frac{r-1}{r}$. We also show that $\hat{I}{´}_{r,q}\le \frac{r}{r+1}$ for all $r,q$, supplementing and giving a new proof for the result of Balogh, Csaba, Pluhár and Treglown.