On a Ramsey--Turán Variant of the Hajnal--Szemerédi Theorem
Rajko Nenadov, Yanitsa Pehova
Abstract
A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree $\delta(G) \ge (r-1)n/r$ for some integer $r \ge 2$, then $G$ contains a $K_r$-factor, assuming $r$ divides $n$. Extremal examples which show optimality of the bound on $\delta(G)$ are very structured and, in particular, contain large independent sets. In analogy to the Ramsey--Turán theory, Balogh, Molla, and Sharifzadeh initiated the study of how the absence of such large independent sets influences sufficient minimum degree. We show the following two related results: (a) For any $r > \ell \ge 2$, if $G$ is a graph satisfying $\delta(G) \ge \frac{r - \ell}{r - \ell + 1}n + \Omega(n)$ and $\alpha_\ell(G) =o(n)$, that is, a largest $K_\ell$-free induced subgraph has at most $o(n)$ vertices, then $G$ contains a $K_r$-factor. This is optimal for $\ell = r - 1$ and extends a result of Balogh, Molla, and Sharifzadeh who considered the case $r = 3$. (b) If a graph $G$ satisfies $\delta(G) = \Omega(n)$ and $\alpha_r^*(G) =o(n)$, that is, every induced $K_r$-free $r$-partite subgraph of $G$ has at least one vertex class of size $o(n)$, then it contains a $K_r$-factor. A similar statement is proven for a general graph $H$.