$H$-factors in graphs with small independence number

Note that the extremal example that achieves the optimality of the bound on $\delta(G)$ in the Hajnal–Szemerédi theorem contains a large independent set, which is “regular” and rather rare among all graphs. Following the spirit of the well-known Ramsey–Turán theory (see [11, 9, 10, 31]), a natural question on the Hajnal–Szemerédi theorem is to determine the minimum degree condition forcing a clique factor when the host graph has sublinear independence number. The following Ramsey–Turán type problem was proposed by Balogh, Molla and Sharifzadeh [2].

Balogh, Molla and Sharifzadeh [2] studied the $K_{3}$-factors and showed that the minimum degree condition $\delta(G)\geq\frac{n}{2}+\mu n$ guarantees a triangle factor, for any $\mu>0$ and large $n\in 3\mathbb{N}$.

Later, Nenadov and Pehova [30] generalised Problem 1 to $K_{\ell}$-independence numbers for $\ell\geq 2$: is it true that for every $r,\ell\in\mathbb{N}$ with $r\geq\ell\geq 2$ and $\mu>0$ there exist a constant $\alpha$ and $n_{0}\in\mathbb{N}$ such that every graph $G$ on $n\geq n_{0}$ vertices where $r$ divides $n$ with $\delta(G)\geq\max\left\{\frac{1}{2}+\mu,\frac{r-\ell}{r}+\mu\right\}n$ and $\alpha_{\ell}(G)\leq\alpha n$ has a $K_{r}$-factor? Nenadov and Pehova [30] also proved a general upper bound for the minimum degree conditions, which is asymptotically optimal when $\ell=r-1$. Chang, Han, Kim, Wang and Yang [4] provided a negative answer to this problem. They [4] also determined an asymptotically optimal degree condition for $\ell\geq\frac{3}{4}r$.

Recently, Knierim and Su [21] proved the following result, which solves Problem 1 asymptotically.

It is natural to study Problem 1 for arbitrary $H$ other than cliques. The first attempt would be to prove a result that matches the Alon–Yuster theorem [1], which we shall formulate below. For our problem, we find that the relevant parameter for the minimum degree condition is the vertex arboricity of $H$.

Note that this definition extends that of the chromatic number of $H$, where each color class is required to be an independent set. Our first result provides an analogue of the Alon–Yuster theorem [1] in host graphs with sublinear independence number.

Similar to the Alon–Yuster theorem [1], the minimum degree condition in Theorem 1.3 is asymptotically tight for infinitely many graphs $H$ which we define now. Let $H$ be a graph and $\mathscr{P}$ be a family of vertex partitions of $H$ where each partition has $\ell$ parts. For $\mathcal{P}\in\mathscr{P}$, let $x_{1}\leq x_{2}\leq\cdots\leq x_{\ell}$ denote the sizes of the parts of $\mathcal{P}$. Put $\mathcal{D}(\mathcal{P}):=\{x_{i+1}-x_{i}\mid i=1,\dots,\ell-1\}$. Let $\mathcal{D}(H,\mathscr{P})$ denote the union of all the sets $\mathcal{D}(\mathcal{P})$ taken over all $\mathcal{P}\in\mathscr{P}$. Let $\mathrm{hcf}_{1}(H,\mathscr{P})$ be the highest common factor of all integers in $\mathcal{D}(H,\mathscr{P})$. (If $\mathcal{D}(H,\mathscr{P})=\emptyset$, then we set $\mathrm{hcf}_{1}(H,\mathscr{P}):=\infty$.) Let $\mathrm{hcf}_{2}(H,\mathscr{P})$ be the highest common factor of all the orders of components of $H$. If $\ell=1$ and $\mathrm{hcf}_{2}(H,\mathscr{P})=1$, then $\mathrm{hcf}(H,\mathscr{P})=1$. If $\ell=2$, $\mathrm{hcf}_{2}(H,\mathscr{P})=1$ and $\mathrm{hcf}_{1}(H,\mathscr{P})\leq 2$, then $\mathrm{hcf}(H,\mathscr{P})=1$. If $\ell\geq 3$ and $\mathrm{hcf}_{1}(H,\mathscr{P})=1$, then $\mathrm{hcf}(H,\mathscr{P})=1$.

Given a graph $H$, let PC be the family of all proper colorings of $H$ with $\chi(H)$ colors, and let AP be the family of all acyclic partitions of $H$ with $ar(H)$ parts. Then for $\ell\geq 2$, whether $\mathrm{hcf}(H,\text{PC})=1$ or not is the dichotomy found by Kühn and Osthus [26] for the minimum degree conditions for $H$-factors in general graphs. That is, the term $1-\frac{1}{\chi(H)}$ in the Alon–Yuster theorem is asymptotically tight if and only if $\mathrm{hcf}(H,\text{PC})\neq 1$. In the problem of Kühn and Osthus [26], $\ell=1$ implies that $H$ is an independent set, which is a trivial case. However, for our problem, $\ell=1$ means that $H$ is a forest, in which case we have the following result.

Note that the degree condition in Theorem 1.4 is quite small. Its proof follows the lattice-based absorbing method [15] used in previous works as well as in this paper. The proof is omitted here and will appear in the first author’s doctoral thesis.

For our problem, we show that the minimum degree condition in Theorem 1.3 is asymptotically tight for $H$ with $\mathrm{hcf}(H,\text{AP})\neq 1$ and conjecture that the relation is actually “if and only if” (see Conjecture 1.10 below). The proof of the following Proposition 1.5 is presented in full details in Section 2.

Comparing with Theorem 1.3, we actually prove a slightly stronger result. To state it, we first introduce some notation.

Note that all cliques of odd order belong to $\widetilde{\mathcal{H}}$ and $f(K_{r})=r$. Our main result reads as follows.

Since $f(H)\leq 2ar(H)$, Theorem 1.3 follows from Theorem 1.7. Theorem 1.7 unifies and generalises the results of Balogh–Molla–Sharifzadeh [2] and Knierm–Su [21] on clique factors. We remark that the minimum degree condition in Theorem 1.7 is asymptotically sharp for (all graphs $H$ with ${\mathrm{hcf}}(H,\text{AP})\neq 1$ and) infinitely many graphs $H$ with ${\mathrm{hcf}}(H,\text{AP})=1$. To illustrate this we introduce the following notation.

Note that $ar(H)-1<ar_{cr}(H)\leq ar(H)$. We supply the following general lower bound serving as a “space barrier” for this problem.

In particular, Proposition 1.9 implies that the degree condition in Theorem 1.7 is tight for the graphs $H$ with $f(H)=2ar_{cr}(H)$. In particular, when $ar_{cr}(H)<ar(H)$, $f(H)=2ar_{cr}(H)$ implies that $H\in\widetilde{\mathcal{H}}$ and thus $\mathrm{hcf}(H,\text{AP})=1$. The following is an example for such $H$. Let $r\in\mathbb{N}$ and $H$ be an $(r+1)$-partite graph $K_{2r+1,\dots,2r+1}$. By definition we have $K_{2r+1,\dots,2r+1}\in\widetilde{\mathcal{H}},f(K_{2r+1,\dots,2r+1})=2r+1$ and $ar_{cr}(K_{2r+1,\dots,2r+1})=\frac{2r+1}{2}$. The proof of Proposition 1.9 is presented in full details in Section 2.

In summary, the degree condition in Theorem 1.7 is tight for the graphs $H$ with i) ${\mathrm{hcf}}(H,\text{AP})\\ \neq 1$ and ii) $H\in\widetilde{\mathcal{H}}$ and $ar_{cr}(H)=ar(H)-1/2$. Nevertheless, we put forward the following conjecture for the $H$-factor problem.

For complete multi-partite graphs $H$, the smallest open case is $H=K_{3,3,4}$ where $f(H)=5$, $ar_{cr}(H)=\frac{20}{9}$ and ${\mathrm{hcf}}(H,\text{AP})=1$.

Our proof makes use of the absorption method and builds on the techniques developed in [14, 15, 19]. The absorption method was introduced by Rödl, Ruciński and Szemerédi about a decade ago in [31]. Since then, it has turned out to be an important tool for studying the existence of spanning structures in graphs, digraphs and hypergraphs.

Now we sketch the proof idea. The main tasks are to (i) build an absorbing set and (ii) cover almost all of the remaining vertices with an $H$-tiling. For (i), we need the following notation of absorbers and absorbing sets in [30].

Widely used constructions of absorbing set by Rödl, Ruciński and Szemerédi [31] and Hàn, Person and Schacht [13] rely on the property that

every $h$-subset $S$ has $\Omega(n^{ht})$ $(H,t)$-absorbers for $S$.

However, as pointed out in [2], in our setting this is usually impossible because when we construct the absorbers using the independence number condition, it does not give such a strong counting. Instead, a new approach due to Nenadov and Pehova [30] guarantees an absorbing set provided that

every $h$-set $S$ has $\Omega(n)$ vertex-disjoint $(H,t)$-absorbers for $S$.

However, it is still unclear how to verify this for our problem and the bulk of the work on building absorbing sets is to handle this. Here we instead build a partition $V(G)=B\cup U$ satisfying that

$|B|=o(n)$ and every $h$-set in $U$ has $\Omega(n)$ vertex-disjoint absorbers.

Similar ideas already appeared in our recent work, e.g. [4]. Then the arguments reduce to finding an absorbing set $A$ in $G[U]$ and then covering vertices of $B$ by a small $H$-tiling vertex disjoint from $A$ so as to yield a desired absorbing set. Our proof for this is also significantly more involved than that in [21] and uses the lattice-based absorption method by the second author [15].

Our second task is to establish an almost perfect $H$-tiling. Following a standard application of the regularity lemma, we obtain an $\varepsilon$-regular partition and then build a reduced multigraph where two vertices are connected by a double-edge if the corresponding clusters form a regular pair of density larger than $\frac{1}{2}$. Our proof uses a crucial notion of $K_{r}$-embeddable structures (see Definition 4.1) from the work of Knierim and Su [21], which was used to model all possible ways how $K_{r}$ is embedded into a collection of clusters. To be more precise, a $K_{r}$-embeddable structure, say $\mathcal{K}$, is a clique in the reduced multigraph such that for $a,b\in\mathbb{N}$ with $a+b=|V(\mathcal{K})|$ and $a+2b=r$, $\mathcal{K}$ has $b$ vertices that are pairwise connected by multiple edges (if $b>1$). Another key ingredient in their approach is that they build an almost perfect fractional tiling with $K_{r}$-embeddable structures via a novel idea (see Definition 4.2 and Lemma 4.3). We adapt this approach to $H$-tilings which roughly boils down to embedding vertex-disjoint copies of $H$ in different $K_{r}$-embeddable structures where $r=f(H)$. To apply Lemma 4.3 in our proof, it suffices to show that for every $K_{r}$-embeddable structure $\mathcal{K}$ with $a,b$ given as above and $V(\mathcal{K})=\{V_{1},V_{2},\ldots,V_{a+b}\}$, we can find an almost perfect $H$-tiling in an arbitrary collection of subclusters $V^{\prime}_{i}\subseteq V_{i}$, where $2|V_{i}^{\prime}|=|V_{j}^{\prime}|$ for every $i\in[a],j\in[a+1,a+b]$.

Unlike in [21] where they embed a copy of $K_{r}$ each containing exactly one vertex in $V_{i}$ and one edge in $V_{j}$ for every $i\in[a],j\in[a+1,a+b]$, we instead need to embed an independent set in each $V_{i}$ and a forest in $V_{j}$ for every $i\in[a]$ and $j\in[a+1,a+b]$. For this we shall use a result of Erdős, Hajnal, Sós and Szemerédi [10] which allows us to embed two forests in a regular pair with density above $\frac{1}{2}$, one in each side, such that they are complete to each other. Note that the $K_{r}$-embeddable structures may have different orders ranging from $\lceil\frac{r}{2}\rceil$ to $r$. For every $K_{r}$-embeddable structure $\mathcal{K}$ with integers $a,b$ as above, we define a suitably-chosen auxiliary graph $Q(a,b)$ which admits an acyclic partition $\{T_{1},T_{2},\ldots,T_{a+b}\}$ such that $T_{i}$ induces an independent set and $2|T_{i}|=|T_{j}|$¹¹1This is the origin of the family $\widetilde{H}$. for every $i\in[a],j\in[a+1,a+b]$. In particular, $Q(a,b)$ has an $H$-factor, and thus it suffices to find an almost perfect $Q(a,b)$-tilings in the same context (see Lemma 4.6 and Corollary 4.7).

We first introduce some notation throughout the paper. For a graph $G:=G(V,E)$, we write $e(G)=|E(G)|$. We say an independent set $I$ is an $\ell$-independent set if $|I|=\ell$. Similarly, we can define an $\ell$-tree and an $\ell$-forest. The girth $g(G)$ of a graph $G$ is the length of a shortest cycle. For $U\subseteq V$, let $G[U]$ be the induced subgraph of $G$ on $U$. Let $G-U:=G[V\backslash U]$. For two subsets $A,B\subseteq V(G)$, we use $E(A,B)$ to denote the set of edges joining $A$ and $B$. We write $N_{G}(v)$ for the set of neighbors of $v$ in $G$. For convenience, we use $d_{G}(v)$ to denote the number of edges which contain $v$ in $G$. We omit the subscript $G$ if the graph is clear from the context. For $m\in\mathbb{N}$, we write $[V]^{\geq m}$ for the family of all subsets $U\subseteq V$ with $|U|\geq m$. For a vertex set $W$ and a positive integer $\ell$, we write $\tbinom{W}{\ell}$ to denote the set of all $\ell$-subsets of distinct elements of $W$. We write $V(G)=V_{1}\cup V_{2}$ for a bipartition of $G$ if $G[V_{i}]$ is an independent set for each $i\in[2]$. For any integers $a\leq b$, let $[a,b]:=\{i\in\mathbb{Z}:a\leq i\leq b\}$ and $[a]:=[1,a]$.

When we write $\beta\ll\gamma$, we always mean that $\beta,\gamma$ are constants in $(0,1)$, and $\beta\ll\gamma$ means that there exists $\beta_{0}=\beta_{0}(\gamma)$ such that the subsequent arguments hold for all $0<\beta\leq\beta_{0}$. Hierarchies of other lengths are defined analogously.

The rest of the paper is organized as follows. In Section 2, we will prove Proposition 1.5 and Proposition 1.9. In Section 3, we will give a proof of our main result and introduce the regularity lemma. In Section 4, our main work is to find a fractional tiling and establish an embedding lemma. We will prove Lemma 3.1 in Section 4.3. In Section 5, we present some necessary results and tools to introduce the latticed-based absorbing method and prove Lemma 3.2.

In this subsection, we introduce the central lemmas that are needed for the proof of our main theorem. This subsection is devoted to explaining how they work together to give the proof of Theorem 1.7. The proofs of these lemmas are then presented in full details in Section 4 and Section 5 respectively.

A crucial and necessary step in our proof is to find an $H$-tiling in the graph $G$ which covers all but a small set of vertices. The following result guarantees the existence of such an $H$-tiling. The proof of Lemma 3.1 will be presented in Section 4.

Lemma 3.2 provides an absorbing set in the graph $G$, whose proof can be found in Section 5.

Now we give the proof of Theorem 1.7 using Lemma 3.1 and Lemma 3.2.

To find an almost perfect tiling, an important ingredient in our proof is Szemerédi’s Regularity Lemma. In this paper, we make use of a degree form of the regularity lemma [24]. We shall first introduce some notation. Given a graph $G$ and a pair $(V_{1},V_{2})$ of vertex-disjoint subsets in $V(G)$, the density of $(V_{1},V_{2})$ is defined as

$d(V_{1},V_{2})=\frac{e(V_{1},V_{2})}{|V_{1}||V_{2}|}$.