Embedding clique-factors in graphs with low $\ell$-independence number

Abstract

The following question was proposed by Nenadov and Pehova and reiterated by Knierim and Su: Given integers $\ell ,r$ and $n$ with $n\in r\mathbb{N}$, is it true that every $n$-vertex graph $G$ with $\delta (G)\ge \max \{\frac{1}{2},\frac{r-\ell }{r}\}n+o(n)$ and ${\alpha }_{\ell }(G)=o(n)$ contains a $K_r$-factor? We give a negative answer for the case when $\ell \ge \frac{3r}{4}$ by giving a family of constructions using the so-called cover thresholds and show that the minimum degree condition given by our construction is asymptotically best possible. That is, for all integers $r,\ell$ with $r>\ell \ge \frac{3}{4}r$ and $\mu >0$, there exist $\alpha >0$ and $N$ such that for every $n\in r\mathbb{N}$ with $n>N$, every $n$-vertex graph $G$ with $\delta (G)\ge \left(\frac{1}{2-{\varrho }_{\ell }(r-1)}+\mu \right)n$ and ${\alpha }_{\ell }(G)\le \alpha n$ contains a $K_r$-factor. Here ${\varrho }_{\ell }(r-1)$ is the Ramsey--Turán density for $K_{r-1}$ under the $\ell$-independence number condition.

23 pages,2 figures

References in corpus (2)

• Forcing quasirandomness with triangles
• $F$-factors in Quasi-random Hypergraphs