A Ramsey-Turán theory for tilings in graphs

Abstract

For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $r\in \mathbb{N}$, the $r$-independence number of $G$, denoted ${\alpha }_r(G)$, is the largest size of a $K_r$-free set of vertices in $G$. In this paper, we discuss Ramsey--Turán-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. For cliques, we show that for any $k\ge 3$ and $\eta >0$, any graph $G$ on $n$ vertices with $\delta (G)\ge \eta n$ and ${\alpha }_k(G)=o(n)$ has a $K_k$-tiling covering all but $\lfloor 1/\eta \rfloor (k-1)$ vertices. All conditions in this result are tight; the number of vertices left uncovered can not be improved and, for $\eta <\frac{1}{k}$, a condition of ${\alpha }_{k-1}(G)=o(n)$ would not suffice. When $\eta >\frac{1}{k}$, we then show that ${\alpha }_{k-1}(G)=o(n)$ does suffice, but not ${\alpha }_{k-2}(G)=o(n)$. These results unify and generalise previous results of Balogh--Molla--Sharifzadeh, Nenadov--Pehova and Balogh--McDowell--Molla--Mycroft on the subject. We further explore the picture when $F$ is a tree or a cycle and discuss the effect of replacing the independence number condition with ${\alpha }^{\ast }(G)=o(n)$ (meaning that any pair of disjoint linear sized sets induce an edge between them) where one can force perfect $F$-tilings covering all the vertices. Finally we discuss the consequences of these results in the randomly perturbed graph setting.

31 pages, final version

References in corpus (2)

• Triangles in randomly perturbed graphs
• Factors in randomly perturbed hypergraphs