{"id":"arxiv/2603.29277","url":"https://arxiv.org/abs/2603.29277","tags":["math.CO"],"score":0,"title":"Multicolor $K_r$-Tilings with High Discrepancy","domain":"math.CO","source":"arxiv","authors":["Henry Chan","Daniel Cheng","Lior Gishboliner","Xiangyu Li"],"reviews":0,"subject":"math.CO","summary":"We study the minimum degree threshold $δ_{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 $δ_{r,2} = \\frac{r}{r+1}$ for all $r \\geq 3$. Here we determine $δ_{r,q}$ for all $q$ large enough, namely $q \\geq \\binom{r}{2}$. For example, we show that for $r \\geq 4$, $δ_{r,q} = \\frac{r}{r+1}$ for $\\binom{r}{2} \\leq q \\leq \\binom{r+1}{2}$ and $δ_{r,q} = \\frac{r-1}{r}$ for $q \\geq \\binom{r+1}{2}+2$. Thus, $δ_{r,q}$ has a phase transition at $q = \\binom{r+1}{2}$, where it drops…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-31","reactions":{}}