Tilings in quasi-random $k$ -partite hypergraphs

Shumin Sun Shumin Sun is supported by the Warwick Mathematics Institute Centre for Doctoral Training, and gratefully acknowledges funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101020255-FDC-ERC-2020-ADG) Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK

Abstract

Given $k\geq 2$ and two $k$ -graphs ( $k$ -uniform hypergraphs) $F$ and $H$ , an $F$ -factor in $H$ is a set of vertex disjoint copies of $F$ that together cover the vertex set of $H$ . Lenz and Mubayi were first to study the $F$ -factor problems in quasi-random $k$ -graphs with a minimum degree condition. Recently, Ding, Han, Sun, Wang and Zhou gave the density threshold for having all $3$ -partite $3$ -graphs factors in quasi-random $3$ -graphs with vanishing minimum codegree condition $\Omega(n)$ .

In this paper, we consider embedding factors when the host $k$ -graph is $k$ -partite and quasi-random with partite minimum codegree condition. We prove that if $p>1/2$ and $F$ is a $k$ -partite $k$ -graph with each part having $m$ vertices, then for $n$ large enough and $m\mid n$ , any $p$ -dense $k$ -partite $k$ -graph with each part having $n$ vertices and partite minimum codegree condition $\Omega(n)$ contains an $F$ -factor. We also present a construction showing that $1/2$ is best possible. Furthermore, for $1\leq\ell\leq k-2$ , by constructing a sequence of $p$ -dense $k$ -partite $k$ -graphs with partite minimum $\ell$ -degree $\Omega(n^{k-\ell})$ having no $K_{k}(m)$ -factor, we show that the partite minimum codegree constraint can not be replaced by other partite minimum degree conditions. On the other hand, we prove that $n/2$ is the asymptotic partite minimum codegree threshold for having all fixed $k$ -partite $k$ -graph factors in sufficiently large host $k$ -partite $k$ -graphs even without quasi-randomness.

1 Introduction

For a positive integer $a$ , we denote by $[a]$ the set $\{1,\dots,a\}$ . For $k\geq 2$ , a $k$ -uniform hypergraph (in short, $k$ -graph) $H$ consists of a vertex set $V(H)$ and an edge set $E(H)\subseteq\binom{V(H)}{k}$ , that is, every edge is a $k$ -element subset of $V(H)$ . For a $k$ -graph $H$ and a subset $S\subset\binom{V(H)}{s}$ , with $1\leq s\leq k-1$ , let $N_{H}(S)$ (or $N(S)$ ) be the set of $(k-s)$ -sets $S^{\prime}\in\binom{V(H)}{k-s}$ such that $S^{\prime}\cup S\in E(H)$ . We call elements of $N_{H}(S)$ neighbors of $S$ . Define the degree of $S$ as $|N_{H}(S)|$ , denoted by $\deg_{H}(S)\ (\text{or}\deg(S))$ . For a subset $U\subseteq V(H)$ , let $H[U]$ be the induced subgraph of $H$ on the vertex set $U$ .

A $k$ -graph $H$ is $t$ -partite if there exists a partition of the vertex set $V(H)$ into $t$ parts $V(H)=V_{1}\cup\cdots\cup V_{t}$ such that every edge intersects each part in at most one vertex. We say $H$ is balanced if $|V_{1}|=|V_{2}|=\cdots=|V_{t}|$ . A subset $S\subseteq V(H)$ is said to be legal if $|S\cap V_{i}|\leq 1$ for all $i\in[t]$ . In a $k$ -partite $k$ -graph $H$ , we define the partite minimum $s$ -degree $\delta^{\prime}_{s}(H)$ as the minimum of $\deg_{H}(S)$ taken over all legal $s$ -subsets $S\subseteq V(H)$ . In particular, we call the partite minimum $(k-1)$ -degree of $H$ as partite minimum codegree of $H$ . If $S=\{v\}$ is a singleton, then we simply write $\deg(v)$ and $N(v)$ instead.

Given two $k$ -graphs $F$ and $H$ , a perfect $F$ -tiling (or $F$ -factor) in $H$ is a set of vertex disjoint copies of $F$ that together cover the vertex set of $H$ . The study of perfect tilings in graph theory has a long and profound history with a number of results, from the classical results of Corradi–Hajnal [6] and Hajnal–Szemerédi [11] on $K_{k}$ -factors to the famous result of Johansson–Kahn–Vu [16] on perfect tilings in random graphs. One type of perfect tiling problem is under the constraint of the host (hyper)graphs being multipartite. The investigation on this topic has been studied by many researchers [10, 27, 24, 29, 1, 7, 18, 22, 15, 25].

In this paper, we focus on $F$ -factor problem in quasi-random $k$ -partite hypergraphs. The study of quasi-random graphs was launched in late 1980s by Chung, Graham and Wilson [4]. They proposed several well-defined notions of quasi-random graphs which are equivalent. We note that the $F$ -factor issue for quasi-random graphs with positive density and a minimum degree $\Omega(n)$ has been implicitly addressed by Komlós–Sárközy–Szemerédi [20] in the course of developing the famous Blow-up Lemma. Unlike graphs, there are several non-equivalent notions for quasi-random hypergraphs (see [31]). One basic notion to define quasi-randomness is uniform edge-distribution which has been studied in [30, 23], and this can be applied naturally to multipartite hypergraphs.

Definition 1.1 (( $p,\mu$ )-denseness).

Given integers $n\geq k\geq 2$ , let $0<\mu,p<1$ , and $H$ be an $n$ -vertex $k$ -partite $k$ -graph with partition $V(H)=V_{1}\cup\cdots\cup V_{k}$ . We say that $H$ is ( $p,\mu$ )-dense if for all $X_{1}\subseteq V_{1},\dots,X_{k}\subseteq V_{k}$ ,

e_{H}(X_{1},\dots,X_{k})\geq p|X_{1}|\cdots|X_{k}|-\mu n^{k},

(1)

where $e_{H}(X_{1},\dots,X_{k})$ is the number of $(x_{1},\dots,x_{k})\in X_{1}\times\cdots\times X_{k}$ such that $\{x_{1},\dots,x_{k}\}\in E(H)$ .

In particular, we say a $k$ -partite $k$ -graph $H$ is $p$ -dense if $H$ is ( $p,\mu$ )-dense for some small $\mu$ .

Lenz and Mubayi [23] were the first to study the $F$ -factor problems in quasi-random hypergraphs. Recently, Ding, Han, Sun, Wang and Zhou [8] gave the density threshold for having all $3$ -partite $3$ -graph factors in quasi-random $3$ -graphs with vanishing minimum codegree condition. In this paper, we investigate on denseness and partite codegree conditions for the host $k$ -partite $k$ -graph to ensure $F$ -factors.

Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. We first prove that $p>1/2$ is enough for a $p$ -dense $k$ -partite $k$ -graph $H$ with vanishing partite minimum codegree to have an $F$ -factor.

Theorem 1.1.

Let $k\geq 3$ be an integer. Given $0<\varepsilon,\alpha<1$ , and a $k$ -partite $k$ -graph $F$ with each part having $m$ vertices, there exist an $n_{0}$ and $\mu>0$ such that the following holds for $n\geq n_{0}$ . If a $(\frac{1}{2}+\varepsilon,\mu)$ -dense $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies that $\delta^{\prime}_{k-1}(H)\geq\alpha n$ and $n\in m\mathbb{N}$ , then $H$ has an $F$ -factor.

Our next construction shows that $1/2$ is the density threshold for containing all fixed balanced $k$ -partite $k$ -graphs in a $p$ -dense $k$ -partite $k$ -graphs with partite minimum codegree condition. Let $K_{k}(m)$ denote the complete $k$ -partite $k$ -graph with each part having $m$ vertices.

Theorem 1.2.

For any $\mu>0$ and integer $m\geq 2$ , there exists an $n_{0}$ such that for all $n\geq n_{0}$ , there exists a $(\frac{1}{2},\mu)$ -dense $k$ -partite $k$ -graph $H$ with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}-\mu)n$ and $H$ has no $K_{k}(m)$ -factor.

Next possible question is if we can get a similar density threshold in Theorem 1.1 under other vanishing partite degree assumptions. However, the answer appears to be negative. Our following result shows that, for $1\leq\ell\leq k-2$ , there exists a $p$ -dense $k$ -partite $k$ -graph $H$ having partite minimum $\ell$ -degree $\Omega(n^{k-\ell})$ and $p$ close to $1$ such that $H$ has no $K_{k}(m)$ -factor.

Theorem 1.3.

For any $p\in(0,1)$ , $\mu>0$ and integers $k\geq 3$ , $1\leq\ell\leq k-2$ , $m\geq 2$ , there exist an $n_{0}$ and $\alpha>0$ such that for all $n\geq n_{0}$ , there exists a $(p,\mu)$ -dense $k$ -partite $k$ -graph $H$ with each part having $n$ vertices such that $\delta^{\prime}_{\ell}(H)\geq\alpha n^{k-\ell}$ and $H$ has no $K_{k}(m)$ -factor.

Compared with the construction in Theorem 1.2, Theorem 1.1 tells that in a $p$ -dense $k$ -partite $k$ -graph, if the density $p$ is larger than $1/2$ , one can relax the partite minimum codegree to be vanishing for ensuring all $k$ -partite $k$ -graph factors. We naturally consider another direction, i.e. whether we can relax denseness condition to guarantee $k$ -parite $k$ -graph factors, given the partite minimum codegree larger than $n/2$ . Our last result proves that denseness condition actually can be removed in this situation.

Theorem 1.4.

Let $k\geq 3$ be an integer. Given $\varepsilon>0$ , and a $k$ -partite $k$ -graph $F$ with each part having $m$ vertices, there exists an $n_{0}$ such that the following holds for $n\geq n_{0}$ . If a $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ and $n\in m\mathbb{N}$ , then $H$ has an $F$ -factor.

The remainder of this paper is organised as follows. In Section 2, we will present probabilistic constructions to prove Theorem 1.2 and Theorem 1.3. Section 3 contains absorbing lemmas, which are the key techniques to prove Theorem 1.1 and Theorem 1.4. We review the hypergraph regularity lemma in Section 4. The proof of Theorem 1.1 follows in Section 5. Section 6 has an introduction of weak hypergraph regularity lemma and also the proof of Theorem 1.4. We give some remarks in the final section.

2 Avoiding $F$ -factors

In this section, we shall prove Theorem 1.2 and Theorem 1.3.

Proof of Theorem 1.2.

We prove the theorem by the following construction.
Construction. Let integer $m\geq 2$ . For $n\in\mathbb{N}$ , define a probability distribution $H(n)$ on $k$ -partite $k$ -graphs with each part having $n$ vertices as follows. Let $K:=K_{k-1}(n)$ be the complete $(k-1)$ -partite $(k-1)$ -graph with partition $V(K)=V_{1}\cup\cdots\cup V_{k-1}$ and $|V_{1}|=\cdots=|V_{k-1}|=n$ . Define a random 2-coloring $\phi:E(K)\longmapsto\{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}red},~{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}blue}\}$ where each color is assigned to every edge independently with probability $\frac{1}{2}$ . Then let $V(H(n))$ = $V(K)\cup V_{k}$ , where $V_{k}$ is a new part with $n$ vertices. Now we partition $V_{k}$ into two pieces $V_{k,1}$ and $V_{k,2}$ . Let $|V_{k,1}|=\lfloor\frac{n}{2}\rfloor$ if $m\nmid\lfloor\frac{n}{2}\rfloor$ , otherwise let $|V_{k,1}|=\lfloor\frac{n}{2}\rfloor-1$ . The edge set $E(H(n))$ is defined as follows. For a vertex $v\in V_{k}$ and an edge $e\in E(K)$ , make $\{v\}\cup e$ into a hyperedge of $H(n)$ when

$\bullet$ $v\in V_{k,1}$ and $e$ has color red, or

$\bullet$ $v\in V_{k,2}$ and $e$ has color blue.

Given such construction, for any $X_{1}\subseteq V_{1},\dots,X_{k}\subseteq V_{k}$ , the expectation of $e(X_{1},\dots,X_{k})$ is

\frac{1}{2}|X_{1}|\cdots|X_{k-1}|\cdot|X_{k}\cap V_{k,1}|+\frac{1}{2}|X_{1}|\cdots|X_{k-1}|\cdot|X_{k}\cap V_{k,2}|=\frac{1}{2}|X_{1}|\cdots|X_{k-1}|\cdot|X_{k}|.

For any legal $(k-1)$ -set $S\in V_{1}\times\cdots\times V_{k-1}$ , the degree of $S$ is at least $\lfloor\frac{n}{2}\rfloor-1$ . For any other legal $(k-1)$ -set $S$ of $V(H(n))$ , the expectation of $\deg(S)$ is $\frac{1}{2}n$ . By concentration inequality (e.g. Chernoff’s bound) and the union bound, for any $\mu>0$ and sufficiently large $n$ , there exists $H\in H(n)$ such that $H$ is $(\frac{1}{2},\mu)$ -dense and $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}-\mu)n$ .

We claim that $H$ has no $K_{k}(m)$ -factor. Note that for any $u\in V_{k,1}$ and $v\in V_{k,2}$ , there is no legal $(k-1)$ -set $S\in V_{1}\times\cdots\times V_{k-1}$ such that $\{u\}\cup S,\{v\}\cup S\in E(H)$ , otherwise $S$ receives two colors at the same time. This implies that any copy of $K_{k}(m)$ in $H$ must have one part entirely lying in $V_{k,1}$ or $V_{k,2}$ . Therefore if $H$ has a $K_{k}(m)$ -factor, then $m\mid|V_{k,1}|$ , which contradicts to the condition $m\nmid|V_{k,1}|$ .

We next prove Theorem 1.3.

Proof of Theorem 1.3.

We use the following construction to prove Theorem 1.3.
Construction. Let integers $m\geq 2$ , $k\geq 3$ and $1\leq\ell\leq k-2$ . For $n\in\mathbb{N}$ , define a probability distribution $H(n)$ on $k$ -partite $k$ -graphs with each part having $n$ vertices as follows. Let $G$ be a complete $k$ -partite $(\ell+1)$ -graph with vertex partition $V(G)=V^{\prime}_{1}\cup\cdots\cup V^{\prime}_{k}$ where $|V^{\prime}_{1}|=n-1$ and $|V^{\prime}_{i}|=n$ for $2\leq i\leq k$ . Now consider a random 2-coloring $\phi:E(G)\longmapsto\{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}red},~{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}blue}\}$ where every edge independently has red with probability $q$ and blue with probability $1-q$ . In particular, we say a subgraph in $G$ is red/blue if every edge in the subgraph has color red/blue. We define $V(H(n))=V_{1}\cup\cdots\cup V_{k}$ with $V_{1}=V^{\prime}_{1}\cup\{v\}$ and $V_{i}=V^{\prime}_{i}$ for $2\leq i\leq k$ , i.e. we add one new vertex in the first part of $V(G)$ . For a legal $k$ -set $S$ of $H(n)$ , we make $S$ into a hyperedge of $H(n)$ when

$\bullet$ $S$ does not contain $v$ and $G[S]$ is red, or

$\bullet$ $S$ contains $v$ and there exists a blue edge in $G[S\setminus\{v\}]$ .

For any $X_{1}\subseteq V_{1},\dots,X_{k}\subseteq V_{k}$ , the expectation of $e(X_{1},\dots,X_{k})$ is at least

q^{\binom{k}{\ell+1}}(|X_{1}|-1)|X_{2}|\cdots|X_{k}|.

For any legal $\ell$ -set $U$ , if $U$ does not contain $v$ , then the expected value of $\deg(U)$ is at least $q^{\binom{k}{\ell+1}}(n-1)n^{k-\ell-1}$ . On the other hand, if $U$ contains $v$ , the expected value of $\deg(U)$ is at least $(1-q^{\binom{k-1}{\ell+1}})n^{k-\ell}$ . Let $p=q^{\binom{k}{\ell+1}}$ and $2\alpha=\min\{q^{\binom{k}{\ell+1}},1-q^{\binom{k-1}{\ell+1}}\}$ . By probabilistic concentration inequality (e.g. Janson’s inequality [2]) and the union bound, for any $\mu>0$ and $n$ large enough, there exists $H\in H(n)$ such that $H$ is $(p,\mu)$ -dense and $\delta^{\prime}_{\ell}(H)\geq\alpha n^{k-\ell}$ .

We next show that $H$ has no $K_{k}(m)$ -factor. Suppose not, let $K^{\prime}$ be the copy of $K_{k}(m)$ which covers vertex $v$ . As $m\geq 2$ , there exists a vertex $u\in V(K^{\prime})$ such that $u\in V^{\prime}_{1}$ . Therefore, there exists a legal $(k-1)$ -set $T\in V_{2}\times\cdots\times V_{k}$ such that $T\cup\{v\}\in E(H)$ and $T\cup\{u\}\in E(H)$ , which implies that $G[T]$ is red and $G[T]$ has a blue edge respectively. A contradiction.

3 The Absorption Technique

The main tool to prove Theorem 1.1 and Theorem 1.4 is the absorbing method. This technique, developed initially by Rödl, Ruciński and Szemerédi [32], is a powerful tool in finding spanning structures in graphs and hypergraphs. In this paper, we shall apply a variant of the absorbing method - the lattice-based absorption method, which was proposed by Han [12]. Throughout the rest of paper, we use $a\ll b$ to indicate that we select the positive constants $a,b$ from right to left. More concretely, there is an increasing positive function $f$ such that, given $b$ , whenever we choose some $0<a\leq f(b)$ such that the subsequent statement holds. Hierarchies of other lengths are defined similarly.

Given a $k$ -partite $k$ -graph $H$ with vertex partition $V(H)=V_{1}\cup\cdots\cup V_{k}$ , we say a vertex subset $S$ is balanced if $|S\cap V_{1}|=\cdots=|S\cap V_{k}|$ .

Our first absorbing lemma deals with the case when the host $k$ -partite $k$ -graph is $p$ -dense with $p>1/2$ and has vanishing partite minimum codegree, which is the main lemma to prove Theorem 1.1.

Lemma 3.1 (Absorbing Lemma I).

Suppose that $1/n\ll\mu,\gamma^{\prime}\ll\gamma\ll\varepsilon,\alpha<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that a $(\frac{1}{2}+\varepsilon,\mu)$ -dense $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies $\delta^{\prime}_{k-1}(H)\geq\alpha n$ and $n\in m\mathbb{N}$ . Then there exists a balanced vertex set $W\subseteq V(H)$ with $|W|\leq\gamma n$ such that for any balanced vertex set $U\subseteq V(H)\setminus W$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , both $H[W]$ and $H[W\cup U]$ contain $F$ -factors.

Our second absorbing lemma is for Theorem 1.4, which treats the situation when the host $k$ -partite $k$ -graph has large partite minimum codegree without denseness condition.

Lemma 3.2 (Absorbing Lemma II).

Suppose that $1/n\ll\gamma^{\prime}\ll\gamma\ll\varepsilon<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that a $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ and $n\in m\mathbb{N}$ . Then there exists a balanced vertex set $W\subseteq V(H)$ with $|W|\leq\gamma n$ such that for any balanced vertex set $U\subseteq V(H)\setminus W$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , both $H[W]$ and $H[W\cup U]$ contain $F$ -factors.

The rest of the section is devoted to the proof of Lemma 3.1 and Lemma 3.2, for which we shall state and prove some necessary lemmas.

Lemma 3.3.

Suppose that $1/n\ll\mu,\eta\ll\alpha<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that a $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies $\delta^{\prime}_{k-1}(H)\geq\alpha n$ . Then for any vertex $v\in V(H)$ , $v$ is contained in at least $\eta n^{km-1}$ copies of $F$ .

The proof of Lemma 3.3 bases on a classical counting result, called supersaturation initially from Erdős [9].

Proposition 3.4.

Suppose that $1/n\ll\eta\ll p^{\prime}<1$ and $f,k,n\in\mathbb{N}$ . Let $F$ be a $k$ -partite $k$ -graph with $|V(F)|=f$ . Suppose that $H$ is a $k$ -partite $k$ -graph with $|V(H)|=n$ and a vertex partition $V_{1}\cup\cdots\cup V_{k}$ . If $H$ contains at least $p^{\prime}n^{k}$ edges, then $H$ contains at least $\eta n^{f}$ copies of $F$ whose $j$ -th part is contained in $V_{j}$ for all $j\in[k]$ .

Proof of Lemma 3.3.

It is enough to prove Lemma 3.3 for $F=K_{k}(m)$ , as any $F$ in the statement is a subgraph of $K_{k}(m)$ . Suppose that $H$ has vertex partition $V(H)=V_{1}\cup\cdots\cup V_{k}$ . Without loss of generality, we assume $v\in V_{1}$ . By partite minimum codegree condition, we have $\deg(v)\geq n^{k-2}\cdot\alpha n=\alpha n^{k-1}$ .

Construct an auxiliary $k$ -partite $k$ -graph $H^{\prime}$ as follows. Define the vertex set $V(H^{\prime})=(V_{1}\setminus\{v\})\cup V_{2}\cup\cdots\cup V_{k}$ and let $E(H^{\prime}):=\{e\in E(H):v\notin e\ {\text{and}}\ \exists S\in N(v)\ {\text{such that}}\ S\subseteq e\}$ , i.e. we keep those edges in $E(H)$ which do not cover $v$ but contain some neighbor of $v$ as subset. Note that $|E(H^{\prime})|\geq\alpha n^{k-1}\cdot(\alpha n-1)\geq\frac{\alpha^{2}n^{k}}{2}$ as $n$ sufficiently large. Let $K^{\prime}$ be a $k$ -partite $k$ -graph obtained from $K_{k}(m)$ by removing arbitrary one vertex $u$ from the first part. Then, by Proposition 3.4 with $p^{\prime}=\frac{\alpha^{2}}{2k^{k}}$ , there exists some small $\eta$ such that $H^{\prime}$ contains at least $\eta n^{km-1}$ copies of $K^{\prime}$ . Consider a copy of $K^{\prime}$ in $H^{\prime}$ , denoted by $K^{\prime\prime}$ . Assume $V(K^{\prime\prime})=V^{\prime}_{1}\cup\cdots\cup V^{\prime}_{k}$ with $V^{\prime}_{i}\subseteq V_{i}$ for $i\in[k]$ . By the construction, in $K^{\prime\prime}$ any legal $(k-1)$ -set $S\in V^{\prime}_{2}\times\cdots\times V^{\prime}_{k}$ is a neighbor of $v$ . Thus we obtain a copy of $K_{k}(m)$ in $H$ , from $K^{\prime\prime}$ with $u$ embedded into $v$ . Therefore, $v$ is contained in at least $\eta n^{km-1}$ copies of $K_{k}(m)$ and we are done.

We need some notions which are useful in the next proof. The following concepts are introduced by Lo and Markström [26]. Let $H$ be a $k$ -partite $k$ -graph with vertex partition $V(H)=V_{1}\cup\cdots\cup V_{k}$ and each part having $n$ vertices. Given a $k$ -partite $k$ -graph $F$ with each part having $m$ vertices, a constant $\beta>0$ , an integer $i\geq 1$ and $j\in[k]$ , we say that two vertices $u,v\in V_{j}$ in $H$ are $(F,\beta,i)$ -reachable (in $H$ ) if there are at least $\beta n^{ikm-1}$ $(ikm-1)$ -sets $W$ such that both $H[\{u\}\cup W]$ and $H[\{v\}\cup W]$ contain $F$ -factors. In this case we call $W$ a reachable set for $\{u,v\}$ . A vertex subset $U\subseteq V_{j}$ is said to be $(F,\beta,i)$ -closed if every two vertices in $U$ are $(F,\beta,i)$ -reachable in $H$ . For $v\in V(H)$ , denote by $\tilde{N}_{F,\beta,i}(v)$ the set of vertices that are $(F,\beta,i)$ -reachable to $v$ .

Lemma 3.5.

Suppose that $1/n\ll\beta\ll\eta$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that $H$ is a $k$ -partite $k$ -graph with vertex partition $V_{1}\cup\cdots\cup V_{k}$ and each part having $n$ vertices such that every vertex $v$ in $V(H)$ is contained in at least $\eta n^{km-1}$ copies of $F$ . Then for any $j\in[k]$ , every set of $\lfloor 1/\eta\rfloor+1$ vertices in $V_{j}$ contains two vertices that are $(F,\beta,1)$ -reachable in $H$ .

Proof.

Set $c:=\lfloor 1/\eta\rfloor$ . We choose $\beta$ small enough such that $(c+1)\eta\geq 1+(c+1)^{2}\beta$ . For any vertex $v\in V(H)$ , denote by $C_{F}(v)$ the family of $(km-1)$ -sets $W$ such that $H[W\cup\{v\}]$ has a copy of $F$ . Consider $j\in[k]$ and any $c+1$ vertices $v_{1},\dots,v_{c+1}\in V_{j}$ . As every vertex in $H$ is contained in at least $\eta n^{km-1}$ copies of $F$ , we have $\sum_{i=1}^{c+1}|C_{F}(v_{i})|\geq(c+1)\eta n^{km-1}\geq(1+(c+1)^{2}\beta)n^{km-1}$ . Therefore, by the inclusion-exclusion principle, there exist two vertices $u,v$ such that $|C_{F}(u)\cap C_{F}(v)|\geq\beta n^{km-1}$ , which implies that there are at least $\beta n^{km-1}$ $(km-1)$ -sets $W$ such that both $H[W\cup\{u\}]$ and $H[W\cup\{v\}]$ have copies of $F$ . Namely $u,v$ are $(F,\beta,1)$ -reachable in $H$ .

The following lemma says that if the host $k$ -parite $k$ -graph $H$ satisfies the conclusion above, i.e. in each part every constant-sized subset contains two reachable vertices, then we are able to find a large set $S_{i}$ in each part such that every vertex in $S_{i}$ has a large reachable neighborhood.

Lemma 3.6.

Suppose that $\delta,\beta>0$ and integers $c,m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that $H$ is a $k$ -partite $k$ -graph with vertex partition $V_{1}\cup\cdots\cup V_{k}$ and each part having $n$ vertices such that for any $i\in[k]$ every set of $c+1$ vertices in $V_{i}$ contains two vertices that are $(F,\beta,1)$ -reachable in $H$ . Then there exists $S_{i}\subseteq V_{i}$ with $|S_{i}|\geq(1-c\delta)n$ such that $|\tilde{N}_{F,\beta,1}(v)\cap S_{i}|\geq\delta n$ for any $v\in S_{i}$ .

Proof.

For each part $V_{i}$ with $i\in[k]$ , our strategy is step by step deleting one vertex with few “reachable neighbors” and also removing the vertices that are reachable to it from $V_{i}$ . Set $V_{i}^{0}:=V_{i}$ . If there is a vertex $v_{0}\in V_{i}^{0}$ such that $|\tilde{N}_{F,\beta,1}(v_{0})\cap V_{i}^{0}|<\delta n$ , then let $A_{0}:=\{v_{0}\}\cup\tilde{N}_{F,\beta,1}(v_{0})$ and let $V_{i}^{1}:=V_{i}^{0}\setminus A_{0}$ . Next, we check $V_{i}^{1}$ – if there still exists a vertex $v_{1}\in V_{i}^{1}$ such that $|\tilde{N}_{F,\beta,1}(v_{1})\cap V_{i}^{1}|<\delta n$ , then let $A_{1}:=\{v_{1}\}\cup\tilde{N}_{F,\beta,1}(v_{1})$ and let $V_{i}^{2}:=V_{i}^{1}\setminus A_{1}$ and repeat the procedure until no such $v_{j}$ exists. Suppose we stop with a set of vertices $v_{0},\dots,v_{s}$ . Note that every two vertices of $v_{0},\dots,v_{s}$ are not $(F,\beta,1)$ -reachable in $V_{i}$ , which implies $s<c$ and $|\bigcup_{0\leq j\leq s}A_{j}|\leq c\delta n$ . Set $S_{i}=V_{i}\setminus\bigcup_{0\leq j\leq s}A_{j}$ , then $|\tilde{N}_{F,\beta,1}(v)\cap S_{i}|\geq\delta n$ for any $v\in S_{i}$ .

The following lemma from [13] can give a partition of each part of $H$ such that every smaller part possesses a good reachable property.

Lemma 3.7.

([13, Theorem 6.3]). Suppose that $1/n_{0}\ll\beta_{0}\ll\beta\ll\delta,1/c,1/m<1$ and $c,m,k,n_{0}\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -graph on $f$ vertices. Suppose that $H$ is a $k$ -graph on $n_{0}$ vertices, and a subset $S\subseteq V(H)$ satisfies that $|\tilde{N}_{F,\beta,1}(v)\cap S|\geq\delta n_{0}$ for any $v\in S$ . Further, suppose every set of $c+1$ vertices in $S$ contains two vertices that are $(F,\beta,1)$ -reachable in $H$ . Then we can find a partition $\mathcal{P}$ of $S$ into $W_{1},\dots,W_{r}$ with $r\leq\min\{c,\lfloor 1/{\delta}\rfloor\}$ such that for any $i\in[r]$ , $|W_{i}|\geq(\delta-\beta)n_{0}$ and $W_{i}$ is $(F,\beta_{0},2^{c-1})$ -closed in $H$ .

In order to prove the whole $S_{i}$ in Lemma 3.6 is closed, we need the following lemma from [14] which gives a sufficient condition to merge different closed parts. Before stating the lemma formally, we introduce the following concepts from Keevash and Mycroft [17]. Let $H$ be a $k$ -partite $k$ -graph with each part having $n$ vertices. Suppose that $\mathcal{P}=\{W_{0},W_{1},\dots,W_{r}\}$ is a partition of $V(H)$ with $r\geq k$ which is a refinement of the original $k$ -partition of $V(H)$ . Let $F$ be a $k$ -partite $k$ -graph with $f$ vertices. For a subset $S\subseteq V(H)$ , the index vector of $S$ with respect to $\mathcal{P}$ is the vector

\mathbf{i}_{\mathcal{P}}(S):=(|S\cap W_{1}|,\dots,|S\cap W_{r}|)\in\mathbb{Z}^{r}.

Given a vector $\mathbf{i}\in\mathbb{Z}^{r}$ , we use $\mathbf{i}|_{W_{j}}$ to denote the coordinate which corresponds to $W_{j}$ . We call a vector $\mathbf{i}\in\mathbb{Z}^{r}$ an $s$ -vector if all its coordinates are non-negative and their sum is $s$ . Given $\lambda>0$ , an $f$ -vector $\mathbf{v}\in\mathbb{Z}^{r}$ is called a $\lambda$ -robust $F$ -vector if at least $\lambda n^{f}$ copies $F^{\prime}$ of $F$ in $H$ satisfy $\mathbf{i}_{\mathcal{P}}(V(F^{\prime}))=\mathbf{v}$ . Let $I^{\lambda}_{\mathcal{P},F}(H)$ be the set of all $\lambda$ -robust $F$ -vectors and $L^{\lambda}_{\mathcal{P},F}(H)$ be the lattice generated by the vectors of $I^{\lambda}_{\mathcal{P},F}(H)$ . Let $\mathbf{u}_{W_{j}}\in\mathbb{Z}^{r}$ be the unit vector such that $\mathbf{u}_{W_{j}}|_{W_{j}}=1$ and $\mathbf{u}_{W_{j}}|_{W_{i}}=0$ for $i\neq j$ .

The next lemma is actually a variant of [14, Lemma 3.9] and can be derived from the the proof of [14, Lemma 3.9].

Lemma 3.8.

([14, Lemma 3.9]). Let $i_{0},k,r,f>0$ be integers and let $F$ be a $k$ -graph with $f:=v(F)$ . Given constants $\zeta,\beta_{0},\lambda>0$ , there exists $\beta_{0}^{\prime}>0$ and integers $i^{\prime}_{0}$ such that the following holds for sufficiently large $n_{0}$ . Let $H$ be a $k$ -graph on $n_{0}$ vertices with a partition $\mathcal{P}=\{W_{0},W_{1},\dots,W_{r}\}$ of $V(H)$ such that for each $j\in[r]$ , $|W_{j}|\geq\zeta n$ and $W_{j}$ is $(F,\beta_{0},i_{0})$ -closed in $H$ . If $\mathbf{u}_{W_{j}}-\mathbf{u}_{W_{l}}\in L^{\lambda}_{\mathcal{P},F}(H)$ where $1\leq j<l\leq r$ , then $W_{j}\cup W_{l}$ is $(F,\beta^{\prime}_{0},i^{\prime}_{0})$ -closed in $H$ .

We state the following crucial lemma for the proof of Lemma 3.1.

Lemma 3.9.

Suppose that $1/n\ll\mu\ll\lambda\ll\zeta,\varepsilon<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that $H$ is a $(\frac{1}{2}+\varepsilon,\mu)$ -dense $k$ -partite $k$ -graph with vertex partition $V_{1}\cup\cdots\cup V_{k}$ and each part having $n$ vertices. Let $\mathcal{P}_{i}=\{W_{i}^{0},W_{i}^{1},\dots,W_{i}^{r_{i}}\}$ be a partition of $V_{i}$ , and let $\mathcal{P}:=\cup_{i\in[k]}\mathcal{P}_{i}$ which is a refinement of the original $k$ -partition of $V(H)$ . Assume for every $i\in[k]$ and $j\in[r_{i}]$ , $|W_{i}^{j}|\geq\zeta n$ . Then for any $i\in[k]$ and $j_{1},j_{2}\in[r_{i}]$ , we have $\mathbf{u}_{W_{i}^{j_{1}}}-\mathbf{u}_{W_{i}^{j_{2}}}\in L^{\lambda}_{\mathcal{P},F}(H)$ .

The proof of Lemma 3.9 relies on the hypergraph regularity method, therefore we postpone the proof to Section 4.

Given a $k$ -partite $k$ -graph $F$ with each part having $m$ vertices, a $(km)$ -set $S$ and $a\in\mathbb{N}$ , we say an $a$ -set $A\subseteq V(H)$ is an absorbing $a$ -set for $S$ if $A\cap S=\varnothing$ and both $H[A]$ and $H[A\cup S]$ have $F$ -factors. Let $\mathcal{A}_{a}(S)$ be the family of all absorbing $a$ -sets for $S$ . The proofs of two absorbing lemmas depend on the following lemma whose proof idea is similar to the non-multipartite version from [14, Lemma 3.6].

Lemma 3.10.

Suppose that $1/n\ll\gamma^{\prime}\ll\eta,\beta_{0}^{\prime}\ll 1/k,1/m$ , and $i^{\prime}_{0},k,m\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that $H$ is a $k$ -partite $k$ -graph with vertex partition $V_{1}\cup\cdots\cup V_{k}$ and each part having $n$ vertices. Furthermore, $H$ satisfies the following two properties:

(i)

For any $v\in V(H)$ , $v$ is contained in at least $\eta n^{km-1}$ copies of $F$ ;
(ii)

For each $V_{i}$ , there exists $V_{i}^{0}\subseteq V_{i}$ with $|V^{0}_{i}|\leq\eta^{2}n$ such that $V_{i}\setminus V^{0}_{i}$ is $(F,\beta^{\prime}_{0},i^{\prime}_{0})$ -closed in $H$ .

Then there exists a balanced vertex set $W$ with $(\cup_{i\in[k]}V_{i}^{0})\subseteq W\subseteq V(H)$ and $|W|\leq\eta n$ such that for any balanced vertex set $U\subseteq V(H)\setminus W$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , both $H[W]$ and $H[U\cup W]$ contain $F$ -factors.

Proof.

The strategy is as follows. We first show that for any balanced $(km)$ -set $S$ in $V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ , there is a robust number of absorbing sets for $S$ , which allows us to build an absorbing family $\mathcal{F}_{1}$ randomly. Then we cover vertices in $(\cup_{i\in[k]}V_{i}^{0})\setminus V(\mathcal{F}_{1})$ greedily into a family $\mathcal{F}_{2}$ of copies of $F$ . The union $V(\mathcal{F}_{1}\cup\mathcal{F}_{2})$ is the absorbing set we desire.

Fix a balanced $(km)$ -set $S\subseteq V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ . Assume that $S=\cup_{i\in[k]}\{v_{i}^{1},\dots,v_{i}^{m}\}$ such that for each $i\in[k]$ , $\{v_{i}^{1},\dots,v_{i}^{m}\}$ are $m$ vertices lying in $V_{i}$ . Set $a:=i^{\prime}_{0}km(km-1)$ and $\eta_{1}:=\frac{\eta}{2}\cdot(\frac{\beta^{\prime}_{0}}{2})^{km-1}$ . We claim that there are at least $\eta_{1}n^{a}$ absorbing $a$ -sets for $S$ , i.e. $|\mathcal{A}_{a}(S)|\geq\eta_{1}n^{a}$ . We first consider a balanced $(km)$ -set $S^{\prime}:=\cup_{i\in[k]}\{u_{i}^{1},\dots,u_{i}^{m}\}\subseteq V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ with $u_{1}^{1}=v_{1}^{1}$ such that $S\cap S^{\prime}=\{v^{1}_{1}\}$ and $S^{\prime}$ has a copy of $F$ . By the property (i) in the statement and each $|V^{0}_{i}|\leq\eta^{2}n$ , there are at least

\eta n^{km-1}-(km-1)n^{km-2}-(k\eta^{2}n)n^{km-2}\geq\frac{\eta}{2}n^{km-1}

choices of such $S^{\prime}$ , where $(km-1)n^{km-2}$ is the number of $(km)$ -sets overlapping one more vertex with $S$ and $(k\eta^{2}n)n^{km-2}$ is the number of $(km)$ -sets sharing some vertex with $\cup_{i\in[k]}V_{i}^{0}$ . For any distinct vertex pair $\{v_{i}^{j},u_{i}^{j}\}$ with $i\in[k]$ and $j\in[m]$ , they are $(F,\beta^{\prime}_{0},i^{\prime}_{0})$ -reachable in $H$ by the property (ii). Therefore there are at least $\beta^{\prime}_{0}n^{i^{\prime}_{0}km-1}$ reachable $(i^{\prime}_{0}km-1)$ -sets $S_{i}^{j}$ for $\{v_{i}^{j},u_{i}^{j}\}$ . We aim to find disjoint $S_{j}^{i}$ greedily for all $i\in[k],j\in[m]$ except $i=j=1$ such that $S_{j}^{i}$ is also disjoint from $S$ and $S^{\prime}$ . During the selection, there are at most $(2km-1)+(km-1)(i^{\prime}_{0}km-1)$ vertices to avoid in each step. Thus there are at least $\beta^{\prime}_{0}n^{i^{\prime}_{0}km-1}/2$ choices for each $S_{i}^{j}$ . Let $A$ be the union of all such $S_{i}^{j}$ and $S^{\prime}\setminus\{v_{1}^{1}\}$ . We claim that $A$ is an absorbing $a$ -set for $S$ . For $H[A]$ , each $S_{i}^{j}$ forms an $F$ -factor with $u_{i}^{j}$ by the reachable property, so $H[A]$ has an $F$ -factor. For $H[S\cup A]$ , each $S_{i}^{j}$ forms an $F$ -factor with $v_{j}^{i}$ and $S^{\prime}$ has a copy of $F$ , which together give an $F$ -factor in $H[S\cup A]$ . In total, the number of such absorbing sets $A$ is at least

\frac{\eta}{2}n^{km-1}\cdot(\frac{\beta^{\prime}_{0}}{2}n^{i^{\prime}_{0}km-1})^{km-1}\geq\eta_{1}n^{a},

namely $|\mathcal{A}_{a}(S)|\geq\eta_{1}n^{a}$ .

We next build a family of $\mathcal{F}_{1}$ of balanced $a$ -sets randomly. Choose a family of $\mathcal{F}$ of balanced $a$ -sets by selecting $\binom{n}{a/k}^{k}$ possible balanced $a$ -sets independently with probability $p=\eta_{1}n^{1-a}/(8a)$ . By Chernoff’s bound and the union bound, with probability $1-o(1)$ as $n\rightarrow\infty$ , the $\mathcal{F}$ satisfies

|\mathcal{F}|\leq 2p\binom{n}{a/k}^{k}\leq\frac{\eta_{1}}{4a}n\ {\rm and}\ |\mathcal{A}_{a}(S)\cap\mathcal{F}|\geq\frac{p}{2}|\mathcal{A}_{a}(S)|\geq\frac{\eta_{1}^{2}}{16a}n

(a)

for all balanced $(km)$ -set $S$ in $V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ .

The expected number of pairs of intersecting balanced $a$ -sets in $\mathcal{F}$ is at most

\binom{n}{a/k}^{k}\cdot a\cdot\binom{n}{a/k-1}\binom{n}{a/k}^{k-1}\cdot p^{2}\leq\frac{\eta_{1}^{2}}{64a}n.

Therefore, by Markov’s inequality, with probability at least $1/2$ ,

\mathcal{F}\ {\rm has}\ {\rm at}\ {\rm most}\ \frac{\eta_{1}^{2}}{32a}n\ {\rm pairs}\ {\rm of}\ {\rm intersecting}\ {\rm balanced}\ a{\text{-sets}}.

(b)

Thus there exists a family $\mathcal{F}$ satisfying both (a) and (b). We obtain a subfamily $\mathcal{F}_{1}$ by removing one balanced $a$ -set from intersecting pairs and also removing those $a$ -sets which are not absorbing $a$ -sets for any balanced $(km)$ -set $S$ in $V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ . Then $|V(\mathcal{F}_{1})|\leq a|\mathcal{F}_{1}|\leq a|\mathcal{F}|\leq\eta_{1}n/4$ and $H[V(\mathcal{F}_{1})]$ has an $F$ -factor. For any balanced $(km)$ -set $S$ in $V(H)\setminus(\cup_{i\in[k]}V_{i}^{0})$ , we get

|\mathcal{A}_{a}(S)\cap\mathcal{F}_{1}|\geq\frac{\eta_{1}^{2}}{16a}n-\frac{\eta_{1}^{2}}{32a}n\geq\frac{\eta_{1}^{2}}{32a}n.

For any balanced vertex set $U\subseteq V(H)\setminus(\cup_{i\in[k]}V_{i}^{0}\cup V(\mathcal{F}_{1}))$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , we split arbitrarily $U$ into at most $\gamma^{\prime}n/(km)$ balanced $(km)$ -sets. Since $\eta_{1}^{2}n/(32a)\geq\gamma^{\prime}n/(km)$ , for all such balanced $(km)$ -sets, we can find disjoint absorbing $a$ -sets, which means that $H[U\cup V(\mathcal{F}_{1})]$ has an $F$ -factor.

We then greedily pick disjoint copies of $F$ covering vertices in $(\cup_{i\in[k]}V_{i}^{0})\setminus V(\mathcal{F}_{1})$ , denoted by $\mathcal{F}_{2}$ the family of such copies of $F$ . Our aim is to avoid vertices belonging to $V(\mathcal{F}_{1})$ in this process. For any vertex $v_{0}\in(\cup_{i\in[k]}V_{i}^{0})\setminus V(\mathcal{F}_{1})$ , there are at least $\eta n^{km-1}$ copies of $F$ containing $v_{0}$ from the property (i) in the assumption. Furthermore, there are at most $k\eta^{2}n\cdot km+\eta_{1}n/4$ vertices to avoid in each step. Thus, we can always find the desired copy of $F$ one by one and finally obtain $\mathcal{F}_{2}$ , since $(k\eta^{2}n\cdot km+\eta_{1}n/4)n^{km-2}<\eta n^{km-1}$ .

Let $W=V(\mathcal{F}_{1})\cup V(\mathcal{F}_{2})$ , and $W$ is the desired balanced vertex set with $|W|\leq k\eta^{2}n\cdot km+\eta_{1}n/4\leq\eta n$ .

Now we are ready to give the proof of Lemma 3.1 and 3.2.

Proof of Lemma 3.1.

We choose parameters in the following hierarchy:

1/n\ll\mu\ll\gamma^{\prime}\ll\beta^{\prime}_{0}\ll\beta_{0},\lambda\ll\zeta,\beta\ll\delta\ll\eta,\gamma\ll\varepsilon,\alpha,1/m,1/k

and $m,n,k\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices, and $H$ be a $(\frac{1}{2}+\varepsilon,\mu)$ -dense $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq\alpha n$ and $n\in m\mathbb{N}$ as in the statement. Let the vertex partition of $H$ be $V_{1}\cup\cdots\cup V_{k}$ . By Lemma 3.3, every vertex $v\in V(H)$ is contained in at least $\eta n^{km-1}$ copies of $F$ . Then by Lemma 3.5, for any $i\in[k]$ , every set of $\lfloor 1/\eta\rfloor+1$ vertices in $V_{i}$ contains two vertices that are $(F,\beta,1)$ -reachable in $H$ . Set $c:=\lfloor 1/\eta\rfloor$ . By Lemma 3.6, for each $i\in[k]$ , there exists $S_{i}\subseteq V_{i}$ with $|S_{i}|\geq(1-c\delta)n$ such that $|\tilde{N}_{F,\beta,1}(v)\cap S_{i}|\geq\delta n$ for any $v\in S_{i}$ . We then apply Lemma 3.7 to each $S_{i}$ with $n_{0}=kn$ and $\delta/k$ in place of $\delta$ , and obtain a partition $\{W_{i}^{1},\dots,W_{i}^{r_{i}}\}$ of $S_{i}$ . Let $\mathcal{P}_{i}=\{W_{i}^{0},W_{i}^{1},\dots,W_{i}^{r_{i}}\}$ be the partition of $V_{i}$ where $W_{i}^{0}=V_{i}\setminus S_{i}$ . Set $\mathcal{P}:=\cup_{i\in[k]}\mathcal{P}_{i}$ , which is a refinement of the original $k$ -partition of $V(H)$ . By Lemma 3.9, for any $i\in[k]$ and $j_{1},j_{2}\in[r_{i}]$ , we have $\mathbf{u}_{W_{i}^{j_{1}}}-\mathbf{u}_{W_{i}^{j_{2}}}\in L^{\lambda}_{\mathcal{P},F}(H)$ . Therefore, following Lemma 3.8 with $\mathcal{P}$ , we conclude that each $S_{i}$ is $(F,\beta^{\prime}_{0},i^{\prime}_{0})$ -closed. We end with Lemma 3.10 where $V_{i}^{0}=W_{i}^{0}=V_{i}\setminus S_{i}$ , and eventually find the desired set $W$ which possesses good absorbing property as in the statement.

The proof of Lemma 3.2 is simpler, where we verify reachable property in a direct way.

Proof of Lemma 3.2.

The parameters have the following hierarchy:

1/n\ll\gamma^{\prime}\ll\gamma,\beta,\eta\ll\epsilon,1/m,1/k

and $m,n,k\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices, and $H$ be a $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ and $n\in m\mathbb{N}$ . Let the vertex partition of $H$ be $V_{1}\cup\cdots\cup V_{k}$ . By Lemma 3.3 with $(\frac{1}{2}+\varepsilon)$ in place of $\alpha$ , every vertex $v\in V(H)$ is contained in at least $\eta n^{km-1}$ copies of $F$ . Thus the property (i) in the Lemma 3.10 holds. It is sufficient to show that each $V_{i}$ is $(F,\beta,1)$ -closed. If so, Lemma 3.2 follows from Lemma 3.10 with $i^{\prime}_{0}=1$ and $\beta$ in place of $\beta^{\prime}_{0}$ .

Without loss of generality, we prove closeness property for $V_{1}$ . For arbitrary two vertices $u,v\in V_{1}$ , since $\delta^{\prime}_{k-1}(H)\geq(1/2+\varepsilon)n$ , we have $\deg(u),\deg(v)\geq n^{k-2}\cdot(1/2+\varepsilon)n=(1/2+\varepsilon)n^{k-1}$ , which implies that $|N(u)\cap N(v)|\geq\varepsilon n^{k-1}$ . We construct an auxiliary $k$ -partite $k$ -graph $H^{\prime}$ as follows. Set the vertex set $V(H^{\prime})=(V_{1}\setminus\{u,v\})\cup V_{2}\cup\cdots\cup V_{k}$ . Define the edge set $E(H^{\prime}):=\{e\in E(H):u,v\notin e\ {\text{and}}\ \exists S\in N(u)\cap N(v)\ {\text{such that}}\ S\subseteq e\}$ , i.e. we retain edges of $E(H)$ which do not cover $u$ nor $v$ but contain some element of $N(u)\cap N(v)$ as subset. Since $\delta^{\prime}_{k-1}(H)\geq(1/2+\varepsilon)n$ , we have $|E(H^{\prime})|\geq\varepsilon n^{k-1}\cdot((1/2+\varepsilon)n-2)\geq\frac{\varepsilon^{2}n^{k}}{4}$ . Let $K^{\prime}$ be a $k$ -partite $k$ -graph obtained from $K_{k}(m)$ with arbitrary one vertex $u^{\prime}$ removed from the first part. Then, by Proposition 3.4, there exists some small $\beta$ such that $H^{\prime}$ contains at least $\beta n^{km-1}$ copies of $K^{\prime}$ . By our construction, for each such copy $K^{\prime\prime}$ , both $V(K^{\prime\prime})\cup\{u\}$ and $V(K^{\prime\prime})\cup\{v\}$ span copies of $K_{k}(m)$ with $u^{\prime}$ embedded to $u$ and $v$ respectively, hence span copies of $F$ as $F$ is a subgraph of $K_{k}(m)$ . This means that there are at least $\beta n^{km-1}$ $(km-1)$ -sets $W$ such that both $H[\{u\}\cup W]$ and $H[\{v\}\cup W]$ contain $F$ -factors, i.e. $u,v$ are $(F,\beta,1)$ -reachable. Therefore $V_{1}$ is $(F,\beta,1)$ -closed.

4 The Hypergraph Regularity Lemma

In this section, we introduce the hypergraph regularity lemma, and an accompanying counting lemma. Then we shall prove Lemma 3.9. We utilise the approach from Rödl and Schacht [34, 33], as well as the results from [5] and [21]. Before stating the hypergraph regularity lemma, we introduce some necessary notation below. For reals $x,y,z$ we write $x=y\pm z$ to denote that $y-z\leq x\leq y+z$ .

4.1 Regular complexes

A hypergraph $\mathcal{H}$ consists of a vertex set $V(\mathcal{H})$ and an edge set $E(\mathcal{H})$ , where every edge $e\in E(\mathcal{H})$ is a non-empty subset of $V(\mathcal{H})$ . So a $k$ -graph as defined earlier is a $k$ -uniform hypergraph in which every edge has size $k$ . A hypergraph $\mathcal{H}$ is a complex if whenever $e\in E(\mathcal{H})$ and $e^{\prime}$ is a non-empty subset of $e$ we have that $e^{\prime}\in E(\mathcal{H})$ . All the complexes considered in this paper have the property that all vertices are contained in an edge. A complex $\mathcal{H}^{\leq k}$ is a $k$ -complex if all the edges of $\mathcal{H}^{\leq k}$ consist of at most $k$ vertices. Given a $k$ -complex $\mathcal{H}^{\leq k}$ , for each $i\in[k]$ , the edges of size $i$ are called $i$ -edges of $\mathcal{H}^{\leq k}$ and we denote by $H^{(i)}$ the underlying $i$ -graph of $\mathcal{H}^{\leq k}$ : the vertices of $H^{(i)}$ are those of $\mathcal{H}^{\leq k}$ and the edges of $H^{(i)}$ are the $i$ -edges of $\mathcal{H}^{\leq k}$ . Note that a $k$ -graph $H$ can be turned into a $k$ -complex by making every edge into a complete $i$ -graph $K^{(i)}_{k}$ (i.e., consisting of all $\binom{k}{i}$ different $i$ -tuples on $k$ vertices), for each $i\in[k]$ .

Given positive integers $s\geq k$ , an $(s,k)$ -graph $H^{(k)}_{s}$ is an $s$ -partite $k$ -graph, by which we mean that the vertex set of $H^{(k)}_{s}$ can be partitioned into sets $V_{1},\dots,V_{s}$ such that every edge of $H^{(k)}_{s}$ meets each $V_{i}$ in at most one vertex for $i\in[s]$ . Similarly, an $(s,k)$ -complex $\mathcal{H}^{\leq k}_{s}$ is an $s$ -partite $k$ -complex.

Given $i\geq 2$ , let $H^{(i)}_{i}$ and $H^{(i-1)}_{i}$ be on the same vertex set. We denote by $\mathcal{K}_{i}(H^{(i-1)}_{i})$ for the family of $i$ -sets of vertices which form a copy of the complete $(i-1)$ -graph $K^{(i-1)}_{i}$ in $H^{(i-1)}_{i}$ . We define the density of $H^{(i)}_{i}$ w.r.t. (with respect to) $H^{(i-1)}_{i}$ to be

d(H^{(i)}_{i}|H^{(i-1)}_{i}):=\begin{cases}\frac{|E(H^{(i)}_{i})\cap\mathcal{K}_{i}(H^{(i-1)}_{i})|}{|\mathcal{K}_{i}(H^{(i-1)}_{i})|}&\text{if\ }|\mathcal{K}_{i}(H^{(i-1)}_{i})|>0,\\ 0&\text{otherwise}.\end{cases}

More generally, if $\mathbf{Q}:=(Q(1),Q(2),\dots,Q(r))$ is a collection of $r$ subgraphs of $H^{(i-1)}_{i}$ , we define $\mathcal{K}_{i}(\mathbf{Q}):=\bigcup^{r}_{j=1}\mathcal{K}_{i}(Q(j))$ and

d(H^{(i)}_{i}|\mathbf{Q}):=\begin{cases}\frac{|E(H^{(i)}_{i})\cap\mathcal{K}_{i}(\mathbf{Q})|}{|\mathcal{K}_{i}(\mathbf{Q})|}&\text{if\ }|\mathcal{K}_{i}(\mathbf{Q})|>0,\\ 0&\text{otherwise}.\end{cases}

We say that an $H^{(i)}_{i}$ is $(d_{i},\delta,r)$ -regular w.r.t. an $H^{(i-1)}_{i}$ if every $r$ -tuple $\mathbf{Q}$ with $|\mathcal{K}_{i}(\mathbf{Q})|\geq\delta|\mathcal{K}_{i}(H^{(i-1)}_{i})|$ satisfies $d(H^{(i)}_{i}|\mathbf{Q})=d_{i}\pm\delta$ . Instead of $(d_{i},\delta,1)$ -regular, we refer to $(d_{i},\delta)$ -regular. Moreover, for $s\geq i\geq 2$ , we say that $H^{(i)}_{s}$ is $(d_{i},\delta,r)$ -regular w.r.t. $H^{(i-1)}_{s}$ if for every $\Lambda_{i}\in[s]^{i}$ the restriction $H^{(i)}_{s}[\Lambda_{i}]=H^{(i)}_{s}[\cup_{\lambda\in\Lambda_{i}}V_{\lambda}]$ is $(d_{i},\delta,r)$ -regular w.r.t. the restriction $H^{(i-1)}_{s}[\Lambda_{i}]=H^{(i-1)}_{s}[\cup_{\lambda\in\Lambda_{i}}V_{\lambda}]$ .

Definition 4.1 ( $(d_{2},\dots,d_{k},\delta_{k},\delta,r)$ -regular complexes).

For $3\leq k\leq s$ and an $(s,k)$ -complex $\mathcal{H}$ , we say that $\mathcal{H}$ is $(d_{2},\dots,d_{k},\delta_{k},\delta,r)$ -regular if the following conditions hold:

$\bullet$ for every $i=2,\dots,k-1$ and every $i$ -tuple $\Lambda_{i}$ of vertex classes, either $H_{s}^{(i)}[\Lambda_{i}]$ is $(d_{i},\delta)$ -regular w.r.t $H_{s}^{(i-1)}[\Lambda_{i}]$ or $d(H_{s}^{(i)}[\Lambda_{i}]|H^{(i-1)}_{s}[\Lambda_{i}])=0$ ;

$\bullet$ for every $k$ -tuple $\Lambda_{k}$ of vertex classes either $H^{(k)}_{s}[\Lambda_{k}]$ is $(d_{k},\delta_{k},r)$ -regular w.r.t $H^{(k-1)}_{s}[\Lambda_{k}]$ or $d(H^{(k)}_{s}[\Lambda_{k}]|H^{(k-1)}_{s}[\Lambda_{k}])=0$ .

4.2 Equitable partition

Suppose that $V$ is a finite set of vertices and $\mathcal{P}^{(1)}$ is a partition of $V$ into sets $V_{1},\dots,V_{a_{1}}$ , which will be called clusters. Given $k\geq 3$ and any $j\in[k]$ , we denote by $\mathrm{Cross}_{j}=\mathrm{Cross}_{j}(\mathcal{P}^{(1)})$ , the set of all those $j$ -subsets of $V$ that meet each $V_{i}$ in at most one vertex for $1\leq i\leq a_{1}$ . For every subset $\Lambda\subseteq[a_{1}]$ with $2\leq|\Lambda|\leq k-1$ , we write $\mathrm{Cross}_{\Lambda}$ for all those $|\Lambda|$ -subsets of $V$ that meet each $V_{i}$ with $i\in\Lambda$ . Let $\mathcal{P}_{\Lambda}$ be a partition of $\mathrm{Cross}_{\Lambda}$ . We refer to the partition classes of $\mathcal{P}_{\Lambda}$ as cells. For each $i=2,\dots,k-1$ , let $\mathcal{P}^{(i)}$ be the union of all the $\mathcal{P}_{\Lambda}$ with $|\Lambda|=i$ . So $\mathcal{P}^{(i)}$ is a partition of $\mathrm{Cross}_{i}$ into several $(i,i)$ -graphs.

Set $1\leq i\leq j$ . For every $i$ -set $I\in\mathrm{Cross}_{i}$ , there exists a unique cell $P^{(i)}(I)\in\mathcal{P}^{(i)}$ so that $I\in P^{(i)}(I)$ . We define for every $j$ -set $J\in\mathrm{Cross}_{j}$ the polyad of $J$ as:

\hat{P}^{(i)}(J):=\bigcup\big{\{}P^{(i)}(I):I\in[J]^{i}\big{\}}.

So we can view $\hat{P}^{(i)}(J)$ as a $(j,i)$ -graph (whose vertex classes are clusters intersecting $J$ ). Let $\mathcal{\hat{P}}^{(j-1)}$ be the set consisting of all the $\hat{P}^{(j-1)}(J)$ for all $J\in\mathrm{Cross}_{j}$ . It is easy to verify $\{\mathcal{K}_{j}(\hat{P}^{(j-1)}):\hat{P}^{(j-1)}\in\mathcal{\hat{P}}^{(j-1)}\}$ is a partition of $\mathrm{Cross}_{j}$ .

Given a vector of positive integers $\mathbf{a}=(a_{1},\dots,a_{k-1})$ , we say that $\mathcal{P}=\mathcal{P}(k-1,\mathbf{a})=\{\mathcal{P}^{(1)},\dots,\mathcal{P}^{(k-1)}\}$ is a family of partitions on $V$ , if the following conditions hold:

$\bullet$ $\mathcal{P}^{(1)}$ is a partition of $V$ into $a_{1}$ clusters.

$\bullet$ $\mathcal{P}^{(i)}$ is a partition of $\mathrm{Cross}_{i}$ satisfying $|\{P^{(i)}\in\mathcal{P}^{(i)}:P^{(i)}\subseteq\mathcal{K}_{i}(\hat{P}^{(i-1)})\}|=a_{i}$ for every $\hat{P}^{(i-1)}\in\mathcal{\hat{P}}^{(i-1)}$ . Moreover for every $P^{(i)}\in\mathcal{P}^{(i)}$ , there exists a $\hat{P}^{(i-1)}\in\mathcal{\hat{P}}^{(i-1)}$ such that $P^{(i)}\subseteq\mathcal{K}_{i}(\hat{P}^{(i-1)})$ .

So for each $J\in\mathrm{Cross}_{j}$ we can view $\bigcup^{j-1}_{i=1}\hat{P}^{(i)}(J)$ as a $(j,j-1)$ -complex.

Definition 4.2 ( $(\eta,\delta,t)$ -equitable).

Suppose $V$ is a set of $n$ vertices, $\mathbf{a}=(a_{1},\dots,a_{k-1})$ is a vector of positive integers, $t$ is a positive integer and $\eta,\delta>0$ . We say a family of partitions $\mathcal{P}=\mathcal{P}(k-1,\mathbf{a})$ is $(\eta,\delta,t)$ -equitable if it satisfies the following:

1.

$\mathcal{P}^{(1)}$ is a partition of $V$ into $a_{1}$ clusters of equal size, where $1/\eta\leq a_{1}\leq t$ and $a_{1}$ divides $n$ ;
2.

for all $i=2,\dots,k-1$ , $\mathcal{P}^{(i)}$ is a partition of $\mathrm{Cross}_{i}$ into at most $t$ cells;
3.

for every $k$ -set $K\in\mathrm{Cross}_{k}$ , the $(k,k-1)$ -complex $\bigcup^{k-1}_{i=1}\hat{P}^{(i)}(K)$ is $(\mathbf{d},\delta,\delta,1)$ -regular, with $\mathbf{d}=(d_{2},\dots,d_{k-1})$ where $d_{i}=1/a_{i}$ .

Note that the final condition implies that the cells of $\mathcal{P}^{(i)}$ have almost equal size for all $i=2,\dots,k-1$ . By the so-called dense counting lemma from [19, Corollary 6.11], conditions in the above definition actually yield a counting result: for any $j\in[k-1]$ and for every $k$ -set $K\in\mathrm{Cross}_{k}$ , provided $\delta$ small enough we have

|\mathcal{K}_{k}(\hat{P}^{(j)}(K))|=(1\pm\eta)\prod_{i=1}^{j}(\frac{1}{a_{i}})^{\binom{k}{i}}n^{k}

where $\mathcal{K}_{k}(\hat{P}^{(j)}(K))$ is the family of all $k$ -sets of $V$ that span a clique in $\hat{P}^{(j)}(K)$ .

4.3 Statement of the regularity lemma.

Let $\delta_{k}>0$ and $r\in\mathbb{N}$ . Suppose that $H$ is a $k$ -graph on $V$ and $\mathcal{P}=\mathcal{P}(k-1)$ is a family of partitions on $V$ . Given a polyad $\hat{P}^{(k-1)}\in\hat{\mathcal{P}}^{(k-1)}$ , we say that $H$ is $(\delta_{k},r)$ -regular w.r.t. $\hat{P}^{(k-1)}$ if $H$ is $(d_{k},\delta_{k},r)$ -regular w.r.t. $\hat{P}^{(k-1)}$ for some $d_{k}$ . Finally, we define that $H$ is $(\delta_{k},r)$ -regular w.r.t. $\mathcal{P}$ .

Definition 4.3 ( $(\delta_{k},r)$ -regular w.r.t. $\mathcal{P}$ ).

We say that a $k$ -graph $H$ is $(\delta_{k},r)$ -regular w.r.t. $\mathcal{P}=\mathcal{P}(k-1)$ if

\big{|}\bigcup\big{\{}\mathcal{K}_{k}(\hat{P}^{(k-1)}):\hat{P}^{(k-1)}\in\mathcal{\hat{P}}^{(k-1)}\\ \text{and\ }H\text{\ is\ not\ }(\delta_{k},r)\text{-regular\ w.r.t.\ }\hat{P}^{(k-1)}\big{\}}\big{|}\leq\delta_{k}|V|^{k}.

This means that no more than a $\delta_{k}$ -fraction of the $k$ -subsets of $V$ form a $K_{k}^{(k-1)}$ that lies within a polyad with respect to which $H$ is not regular.

Now we are ready to state the regularity lemma.

Theorem 4.4 (Regularity lemma [34, Theorem 17]).

Let $k\geq 2$ be a fixed integer. For all positive constants $\eta$ and $\delta_{k}$ and all functions $r:\mathbb{N}\rightarrow\mathbb{N}$ and $\delta:\mathbb{N}\rightarrow(0,1]$ , there are integers $t$ and $n_{0}$ such that the following holds. For every $k$ -graph $H$ of order $n\geq n_{0}$ and $t!$ dividing $n$ , there exists a vector of positive integers $\mathbf{a}=(a_{1},\dots,a_{k-1})$ and a family of partitions $\mathcal{P}=\mathcal{P}(k-1,\mathbf{a})$ of $V(H)$ such that

$(1)$ $\mathcal{P}$ is $(\eta,\delta(t),t)$ -equitable and

$(2)$ $H$ is $(\delta_{k},r(t))$ -regular w.r.t. $\mathcal{P}$ .

Note that the constants in Theorem 4.4 can be chosen to satisfy the following hierarchy:

\frac{1}{n_{0}}\ll\frac{1}{r}=\frac{1}{r(t)},\delta=\delta(t)\ll\min\{\delta_{k},1/t\}\ll\eta.

Given $d\in(0,1)$ , we say that an edge $e$ of $H$ is $d$ -useful if it lies in $\mathcal{K}_{k}(\hat{P}^{(k-1)})$ for some $\hat{P}^{(k-1)}\in\hat{\mathcal{P}}^{(k-1)}$ such that $H$ is $(d_{k},\delta_{k},r)$ -regular w.r.t $\hat{P}^{(k-1)}$ for some $d_{k}\geq d$ . If we choose $\eta\ll d$ , then the following lemma will be helpful in later proofs.

Lemma 4.5.

([21, Lemma 4.4]). At most $2dn^{k}$ edges of $H$ are not $d$ -useful.

4.4 Statement of a counting lemma.

We state a counting lemma accompanying Theorem 4.4. Before that, we need the following definitions.

Suppose that $\mathcal{H}$ is an $(s,k)$ -complex with vertex classes $V_{1},\dots,V_{s}$ , which all have size $m$ . Suppose also that $\mathcal{G}$ is an $(s,k)$ -complex with vertex classes $X_{1},\dots,X_{s}$ of size at most $m$ . We write $E_{i}(\mathcal{G})$ for the set of all $i$ -edges of $\mathcal{G}$ and $e_{i}(\mathcal{G}):=|E_{i}(\mathcal{G})|$ . We say that $\mathcal{H}$ respects the partition of $\mathcal{G}$ if whenever $\mathcal{G}$ contains an $i$ -edge with vertices in $X_{j_{1}},\dots,X_{j_{i}}$ , then there is an $i$ -edge of $\mathcal{H}$ with vertices in $V_{j_{1}},\dots,V_{j_{i}}$ . On the other hand, we say that a labelled copy of $\mathcal{G}$ in $\mathcal{H}$ is partition-respecting if for each $i\in[s]$ the vertices corresponding to those in $X_{i}$ lie within $V_{i}$ . We denote by $|\mathcal{G}|_{\mathcal{H}}$ the number of labelled, partition-respecting copies of $\mathcal{G}$ in $\mathcal{H}$ .

Lemma 4.6.

(Counting lemma [5, Lemma 4]). Let $k,s,r,t,n_{0}$ be positive integers and let $d_{2},\dots,d_{k}$ , $\delta,\delta_{k}$ be positive constants such that $1/{d_{i}}\in\mathbb{N}$ and

1/{n_{0}}\ll 1/r,\delta\ll\min\{\delta_{k},d_{2},\dots,d_{k-1}\}\ll\delta_{k}\ll d_{k},1/s,1/t.

Then the following holds for all integers $n\geq n_{0}$ . Suppose that $\mathcal{G}$ is an $(s,k)$ -complex on $t$ vertices with vertex classes $X_{1},\dots,X_{s}$ . Suppose also that $\mathcal{H}$ is a $(\mathbf{d},\delta_{k},\delta,r)$ -regular $(s,k)$ -complex with vertex classes $V_{1},\dots,V_{s}$ all of size $n$ , which respects the partition of $\mathcal{G}$ . Then

|\mathcal{G}|_{\mathcal{H}}\geq\frac{1}{2}n^{t}\prod\limits_{i=2}^{k}d^{e_{i}(\mathcal{G})}_{i}.

4.5 Reduced Hypergraphs.

To count subgraphs in the host hypergraph, we will use the hypergraph regularity method and then transform the problem into finding certain structure in the reduced hypergraphs, which encode the distribution of dense and regular polyads. The concepts below follow [31, Section 4].

For a $k$ -graph $H$ on $n$ vertices with $n$ sufficiently large, by Theorem 4.4 on $H$ , there exists a family of partitions $\mathcal{P}=\mathcal{P}(k-1,\mathbf{a})$ of $V(H)$ such that

$(1)$ $\mathcal{P}$ is $(\eta,\delta(t),t)$ -equitable and

$(2)$ $H$ is $(\delta_{k},r(t))$ -regular w.r.t. $\mathcal{P}$ .

Having the family of partitions $\mathcal{P}$ , we define index set $I=[a_{1}]$ , where $a_{1}$ is the number of clusters in the regular partition. For any $(k-1)$ -subset $\mathcal{X}$ of $I$ , define the vertex class $\mathcal{P}^{\mathcal{X}}$ to be the set of all cells in $\mathcal{P}_{\mathcal{X}}$ , i.e. we view each cell in $\mathcal{P}_{\mathcal{X}}$ as a vertex of $\mathcal{P}^{\mathcal{X}}$ . Furthermore, for any distinct $(k-1)$ -subsets $\mathcal{X},\mathcal{X}^{\prime}$ of $I$ , $\mathcal{P}^{\mathcal{X}}$ and $\mathcal{P}^{\mathcal{X}^{\prime}}$ are disjoint. For any $k$ -subset $\mathcal{Y}$ of $I$ , we define a $k$ -uniform $k$ -partite hypergraph $\mathcal{A}_{\mathcal{Y}}$ with vertex partition $\bigcup_{\mathcal{X}\in\binom{\mathcal{Y}}{k-1}}\mathcal{P}^{\mathcal{X}}$ , and let $E(\mathcal{A}_{\mathcal{Y}})$ be the collection of all $k$ -subsets of $\bigcup_{\mathcal{X}\in\binom{\mathcal{Y}}{k-1}}\mathcal{P}^{\mathcal{X}}$ that form a $(k-1)$ -uniform $k$ -partite polyad w.r.t which $H$ is $(\delta_{k},r(t))$ -regular and has density at least $d_{k}$ . Then the $k$ -uniform $\binom{a_{1}}{k-1}$ -partite hypergraph $\mathcal{A}$ with

V(\mathcal{A})=\bigcup_{\mathcal{X}\in\binom{I}{k-1}}\mathcal{P}^{\mathcal{X}}\ \ \text{and}\ \ E(\mathcal{A})=\bigcup_{\mathcal{Y}\in\binom{I}{k}}E(\mathcal{A}_{\mathcal{Y}})

is a reduced hypergraph of $H$ .

4.6 Proof of Lemma 3.9.

Now we are ready to prove Lemma 3.9 using the hypergraph regularity lemma and a counting lemma.

Proof of Lemma 3.9.

Without loss of generality, we prove the Lemma for $i=1$ , $j_{1}=1$ and $j_{2}=2$ . We choose parameters satisfying the following hierarchy:

1/n\ll\mu\ll\lambda\ll 1/r,\delta\ll\min\{\delta_{k},d_{2},\dots,d_{k-1}\}\ll\eta,\delta_{k}\ll d_{k}\ll\zeta,\varepsilon,1/m,1/k

where $\mathbf{d}=(d_{2},\dots,d_{k-1})$ . Set $r^{\prime}:=\sum_{i\in[k]}r_{i}$ . Let $\mathbf{u}\in\mathbb{Z}^{r^{\prime}}$ be the $(km)$ -vector where $\mathbf{u}|_{W_{j}^{1}}=m$ for $j\in[k]$ and other coordinates are zero. Let $\mathbf{v}\in\mathbb{Z}^{r^{\prime}}$ be the $(km)$ -vector where $\mathbf{v}|_{W_{1}^{1}}=m-1$ , $\mathbf{v}|_{W_{1}^{2}}=1$ , $\mathbf{v}|_{W_{j}^{1}}=m$ for $j=2,\cdots,k$ and remaining coordinates are zero. Note that $\mathbf{u}_{W_{1}^{1}}-\mathbf{u}_{W_{1}^{2}}=\mathbf{u}-\mathbf{v}$ .

Since $H$ is $(\frac{1}{2}+\varepsilon,\mu)$ -dense, we have

e_{H}(W_{1}^{1},W_{2}^{1},\dots,W_{k}^{1})\geq(\frac{1}{2}+\varepsilon)|W_{1}^{1}|\cdots|W_{k}^{1}|-\mu(kn)^{k}\geq\frac{1}{2}\zeta^{k}n^{k}.

By Proposition 3.4 on $H[W_{1}^{1}\cup\cdots\cup W_{k}^{1}]$ , there exists a constant $\lambda_{1}$ such that there are at least $\lambda_{1}n^{km}$ copies of $F$ with $j$ -th part embedded in $W_{j}^{1}$ for $j\in[k]$ . This implies that $\mathbf{u}\in I^{\lambda_{1}}_{\mathcal{P},F}(H)$ .

We then prove $\mathbf{v}$ is also a robust vector. Recall that the hypergraph regularity lemma is proved by iterated refinements starting with an arbitrary initial partition. Hence, applying Theorem 4.4 to $H$ with the initial partition $\mathcal{P}$ , we obtain a family of partitions $\mathcal{P^{\prime}}=\{\mathcal{P}^{(1)},\dots,\mathcal{P}^{(k-1)}\}$ such that $H$ is $(\delta_{k},r)$ -regular w.r.t. $\mathcal{P^{\prime}}$ where $\mathcal{P}^{(1)}$ is a partition of $V(H)$ into $a_{1}$ clusters $\cup_{i\in[a_{1}]}X_{i}$ and $1/\eta\leq a_{1}\leq t$ . With density $d_{k}$ , we construct the accompanying reduced hypergraph $\mathcal{A}$ of $H$ . Without loss of generality, assume $X_{j}\subseteq W_{j}^{1}$ is a cluster which lies in $W_{j}^{1}$ for $j\in[k]$ , and $X_{k+1}$ is a cluster lying in $W_{1}^{2}$ .

For convenience, set $\mathcal{X}:=[k]$ and $\mathcal{Y}:=[k+1]\setminus\{1\}$ . Below we show that

|E(\mathcal{A}_{*})|>\frac{1}{2}\cdot\prod_{\mathbf{x}\in\binom{*}{k-1}}|\mathcal{P}^{\mathbf{x}}|\quad{\rm{for}}\quad*=\mathcal{X},\mathcal{Y}.

We only prove the above when $*=\mathcal{X}$ while the other case follows in the same way. By $(\frac{1}{2}+\varepsilon,\mu)$ -denseness of $H$ and Lemma 4.5, the number of $d_{k}$ -useful edges in $H[X_{1}\cup\cdots\cup X_{k}]$ is at least

(\frac{1}{2}+\varepsilon)|X_{1}|\cdots|X_{k}|-\mu(kn)^{k}-2d_{k}(kn)^{k}\geq(\frac{1}{2}+\frac{\varepsilon}{2})|X_{1}|\cdots|X_{k}|.

On the other hand, every polyad satisfies

|\mathcal{K}_{k}(\hat{P}^{(k-1)})|=(1\pm\eta)\prod_{i=1}^{k-1}(\frac{1}{a_{i}})^{\binom{k}{i}}(kn)^{k},

which leads to

(\frac{1}{2}+\frac{\varepsilon}{2})|X_{1}|\cdots|X_{k}|\leq|E(\mathcal{A}_{\mathcal{X}})|\cdot|\mathcal{K}_{k}(\hat{P}^{(k-1)})|\leq|E(\mathcal{A}_{\mathcal{X}})|\cdot(1+\eta)\prod_{i=1}^{k-1}(\frac{1}{a_{i}})^{\binom{k}{i}}(kn)^{k}.

By choices of parameters, this yields

|E(\mathcal{A}_{\mathcal{X}})|\geq(\frac{1}{2}+\frac{\varepsilon}{2})\cdot\frac{1}{1+\eta}\cdot\prod_{i=2}^{k-1}a_{i}^{\binom{k}{i}}>\frac{1}{2}\cdot\prod_{\mathbf{x}\in\binom{\mathcal{X}}{k-1}}|\mathcal{P}^{\mathbf{x}}|.

Consider vertex class $\mathcal{P}^{\mathcal{X}\setminus\{1\}}=\mathcal{P}^{\mathcal{Y}\setminus\{k+1\}}$ in the reduced hypergraph. Let $\mathcal{S}_{1}:=\{v\in\mathcal{P}^{\mathcal{X}\setminus\{1\}}:\deg_{\mathcal{A}_{\mathcal{X}}}(v)>0\}$ and $\mathcal{S}_{2}:=\{v\in\mathcal{P}^{\mathcal{Y}\setminus\{k+1\}}:\deg_{\mathcal{A}_{\mathcal{Y}}}(v)>0\}$ . Since $|E(\mathcal{A}_{\mathcal{X}})|>\frac{1}{2}\cdot\prod_{\mathbf{x}\in\binom{\mathcal{X}}{k-1}}|\mathcal{P}^{\mathbf{x}}|$ , we derive that $|\mathcal{S}_{1}|>\frac{1}{2}|\mathcal{P}^{\mathcal{X}\setminus\{1\}}|$ . Similarly, $|\mathcal{S}_{2}|>\frac{1}{2}|\mathcal{P}^{\mathcal{Y}\setminus\{k+1\}}|=\frac{1}{2}|\mathcal{P}^{\mathcal{X}\setminus\{1\}}|$ . Therefore, there exists a vertex $v^{*}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$ . In other words, there are two edges $e_{1}\in E(\mathcal{A}_{\mathcal{X}})$ and $e_{2}\in E(\mathcal{A}_{\mathcal{Y}})$ sharing exactly one vertex. This configuration corresponds to a regular $(k+1,k-1)$ -complex on $X_{1}\cup\cdots\cup X_{k+1}$ , denoted by $\mathcal{C}$ , to whose “ $(k-1)$ -th level” $H$ is $(d,\delta_{k},r)$ -regular for some $d\geq d_{k}$ . We are able to make $\mathcal{C}$ into a $(\mathbf{d},d_{k},\delta_{k},\delta,r)$ -regular $(k+1,k)$ -complex $\mathcal{C^{\prime}}$ by adding $E(H)\cap\mathcal{K}_{k}(C^{(k-1)})$ as the “ $k$ -th level”. Let $\mathcal{F}^{\leq}$ be a $(k+1)$ -partite $k$ -complex obtained from $F$ by making every edge a complete $i$ -graph $K^{(i)}_{k}$ for each $1\leq i\leq k$ , where we view arbitrary one vertex $u$ from the first part as $(k+1)$ -th part. By Lemma 4.6, there are at least $\frac{1}{2}(\frac{kn}{a_{1}})^{km}\prod\limits_{i=2}^{k}d^{e_{i}(\mathcal{\mathcal{F}^{\leq}})}_{i}\geq\lambda_{2}n^{km}$ copies of $F$ in $H[X_{1}\cup\cdots\cup X_{k+1}]$ where $u$ is embedded in $X_{k+1}$ . This implies that $\mathbf{v}\in I^{\lambda_{2}}_{\mathcal{P},F}(H)$ . Let $\lambda:=\min\{\lambda_{1},\lambda_{2}\}$ , then $\mathbf{u},\mathbf{v}\in I^{\lambda}_{\mathcal{P},F}(H)$ . It follows that $\mathbf{u}_{W_{1}^{1}}-\mathbf{u}_{W_{1}^{2}}=\mathbf{u}-\mathbf{v}\in L^{\lambda}_{\mathcal{P},F}(H)$ and we are done.

5 Proof of Theorem 1.1

In this section, we will prove Theorem 1.1 by the absorption approach, which splits the proof into two parts. One is on finding an almost perfect $F$ -tiling in the host $k$ -partite $k$ -graph $H$ by the following lemma, and the other is on using Lemma 3.1 to “complete” the perfect $F$ -tiling.

Lemma 5.1 (Almost Perfect Tiling I).

Suppose that $1/n\ll\mu\ll p,\omega<1$ and $f,k,n\in\mathbb{N}$ . Let $F$ be a $k$ -partite $k$ -graph with $|V(F)|=f$ . Suppose that $H$ is a $(p,\mu)$ -dense $k$ -partite $k$ -graph with each part having $n$ vertices. Then there exists an $F$ -tiling that covers all but at most $\omega n$ vertices in each part of $H$ .

Proof.

For any induced $k$ -partite subgraph $H^{\prime}$ of $H$ with each part having at least $\omega n$ vertices, we have $|E(H^{\prime})|\geq p\omega^{k}n^{k}-\mu(kn)^{k}$ since $H$ is $(p,\mu)$ -dense. By Proposition 3.4, $H^{\prime}$ contains at least one copy of $F$ . Hence, we greedily pick vertex-disjoint copies of $F$ from $H$ until at most $\omega n$ vertices in each part are left.

Proof of Theorem 1.1.

Suppose that $1/n\ll\mu\ll\gamma^{\prime}\ll\gamma\ll\varepsilon,\alpha<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices, and let $H$ be a $(\frac{1}{2}+\varepsilon,\mu)$ -dense $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq\alpha n$ and $n\in m\mathbb{N}$ . By Lemma 3.1, there exists a balanced vertex set $W\subseteq V(H)$ with $|W|\leq\gamma n$ such that for any balanced vertex set $U\subseteq V(H)\setminus W$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , both $H[W]$ and $H[W\cup U]$ contain $F$ -factors. Let $H^{\prime}:=H[V(H)\setminus W]$ be the induced subgraph of $H$ . Note that $H^{\prime}$ is $(\frac{1}{2}+\varepsilon,\mu_{1})$ -dense $k$ -parite $k$ -graph for some $\mu_{1}$ since

\mu(kn)^{k}=\mu\cdot(\frac{k}{k-\gamma})^{k}\cdot(k-\gamma)^{k}n^{k}\leq\mu\cdot(\frac{k}{k-\gamma})^{k}|V(H^{\prime})|^{k}=\mu_{1}|V(H^{\prime})|^{k}.

Applying Lemma 5.1 on $H^{\prime}$ with $\omega=\gamma^{\prime}/k$ , we obtain an $F$ -tiling that covers all but a balanced set $U$ of at most $\gamma^{\prime}n$ vertices. By the absorbing property of $W$ , $H[W\cup U]$ contains $F$ -factor, which gives an $F$ -factor of $H$ .

6 Proof of Theorem 1.4

In this section, we give the proof of Theorem 1.4. Similar to the last section, the proof consists of two lemmas: almost perfect tiling lemma as follows and the absorbing lemma (Lemma 3.2).

Lemma 6.1 (Almost Perfect Tiling II).

Suppose that $1/n\ll\omega,\varepsilon<1$ and $m,k,n\in\mathbb{N}$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices. Suppose that a $k$ -partite $k$ -graph $H$ with each part having $n$ vertices satisfies $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ . Then there exists an $F$ -tiling covers all but at most $\omega n$ vertices in each part of $H$ .

The proof of Lemma 6.1 depends on the so-called weak hypergraph regularity lemma, a straightforward generalization of Szemerédi regularity lemma for graphs.

6.1 Weak regularity lemma for hypergraphs

Let $H$ be a $k$ -graph. Given $k$ pairwise disjoint subsets $A_{1}\dots,A_{k}\subseteq V(H)$ , we define the density of $H$ with respect to $(A_{1},\dots,A_{k})$ as

d_{H}(A_{1},\dots,A_{k})=\frac{e_{H}(A_{1},\dots,A_{k})}{|A_{1}|\cdots|A_{k}|}.

Given $\varepsilon>0$ and $d\geq 0$ , a $k$ -tuple $(V_{1},\dots,V_{k})$ of mutually disjoint subsets $V_{1},\dots,V_{k}\subseteq V(H)$ is called $(\varepsilon,d)$ -regular if for all $A_{i}\subseteq V_{i}$ with $|A_{i}|\geq\varepsilon|V_{i}|$ , $i\in[k]$ , we have

|d_{H}(A_{1},\dots,A_{k})-d|\leq\varepsilon.

We say a $k$ -tuple $(V_{1},\dots,V_{k})$ is $\varepsilon$ -regular if it is $(\varepsilon,d)$ -regular for some $d\geq 0$ .

A straightforward extension of the graph regularity lemma is given as follows, which was proved by Chung [3].

Lemma 6.2 (Weak regularity lemma for hypergraphs).

For all integers $k\geq 2$ and $t_{0}\geq 1$ , and every $\varepsilon>0$ , there exists $T_{0}$ and $n_{0}$ such that the following holds. For every $k$ -uniform hypergraph $H$ on $n\geq n_{0}$ vertices, there exists a constant $t\in\mathbb{N}$ with $t_{0}\leq t\leq T_{0}$ and a partition $V(H)=V_{0}\cup V_{1}\cup\cdots\cup V_{t}$ such that

$({\rm i})$ $|V_{1}|=|V_{2}|=\cdots=|V_{t}|$ and $|V_{0}|\leq\varepsilon n$ ,

$({\rm ii})$ for all but at most $\varepsilon t^{k}$ sets $\{i_{1},\dots,i_{k}\}\in\binom{[t]}{k}$ , the $k$ -tuple $(V_{i_{1}},\dots,V_{i_{k}})$ is $\varepsilon$ -regular.

A partition as given in the Lemma 6.2 is called an $\varepsilon$ -regular partition of $H$ . We call $V_{1},\dots,V_{t}$ in the above lemma clusters. For an $\varepsilon$ -regular partition $\mathcal{P}=\{V_{0},V_{1},\dots,V_{t}\}$ of $H$ , the cluster hypergraph $\mathcal{R}=\mathcal{R}(\varepsilon,d)$ is defined with vertex set $[t]$ and a $k$ -tuple $\{i_{1},\dots,i_{k}\}\in\binom{[t]}{k}$ forming an edge if an only if $(V_{i_{1}},\dots,V_{i_{k}})$ is $\varepsilon$ -regular and $d_{H}(V_{i_{1}},\dots,V_{i_{k}})\geq d$ .

6.2 Proof of Lemma 6.1

Proof of Lemma 6.1.

We pick constants with the following hierarchy:

1/n\ll\xi^{\prime},\xi,\varepsilon_{0},\varepsilon^{*}\ll d\ll\omega,\varepsilon,1/m,1/k.

Let $H$ be a $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ . Note that an $\varepsilon$ -regular partition can be obtained by iterated refinements starting with an arbitrary initial partition of $H$ . Applying Lemma 6.2 on $H$ with $\varepsilon_{0}$ and the original partition $V(H)=V_{1}\cup\cdots\cup V_{k}$ , we suppose that the given $\varepsilon_{0}$ -regular partition is $\mathcal{P}=V^{\prime}_{0}\cup(\cup_{i\in[k]}\mathcal{P}_{i})$ , where $\mathcal{P}_{i}$ partitions each $V_{i}$ into $t_{i}$ clusters, $i\in[k]$ . Assume each cluster except $V^{\prime}_{0}$ has $m_{0}$ vertices. By removing at most $k^{2}\varepsilon_{0}n/m_{0}$ clusters into $V^{\prime}_{0}$ if necessary, we obtain a new partition $\mathcal{P}^{\prime}=V_{0}\cup(\cup_{i\in[k]}\mathcal{P}^{\prime}_{i})$ where $\mathcal{P}^{\prime}_{i}\subseteq\mathcal{P}_{i}$ splits each $V_{i}$ into exactly $t$ clusters where $t=\min\{t_{1},\dots,t_{k}\}$ . By choosing $\varepsilon_{0}$ small enough, $\mathcal{P}^{\prime}$ is a $(k\varepsilon_{0})$ -regular partition of $H$ . Set $\varepsilon^{*}:=k\varepsilon_{0}$ , and let $\mathcal{R}=\mathcal{R}(\varepsilon^{*},d)$ be the corresponding cluster hypergraph. Note that $\mathcal{R}$ is a $k$ -partite $k$ -graph with each part having $t$ vertices.

The next proposition shows that the cluster hypergraph inherits the partite minimum codegree condition of $H$ .

Proposition 6.3.

Suppose that $1/n\ll\xi,\varepsilon^{*}\ll d\ll\varepsilon<1$ . Let $H$ be a $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ . Suppose that $\mathcal{P^{\prime}}$ is an $\varepsilon^{*}$ -regular partition and the corresponding cluster hypergraph $\mathcal{R}=\mathcal{R}(\varepsilon^{*},d)$ is a $k$ -partite $k$ -graph with each part having $t$ vertices. Then the number of legal $(k-1)$ -sets $S$ violating

\deg_{\mathcal{R}}(S)\geq(\frac{1}{2}+\frac{\varepsilon}{4})t

is at most $\xi t^{k-1}$ .

Proof.

Assume that $\mathcal{P}^{\prime}=\{V_{0},W_{1},W_{2},\dots,W_{kt}\}$ . The cluster hypergraph $\mathcal{R}$ can be viewed as the intersection of two $k$ -partite $k$ -graphs $\mathcal{D}=\mathcal{D}(d)$ and $\mathcal{G}=\mathcal{G}(\varepsilon^{*})$ . Both of them have the same vertex set $[kt]$ and

$\bullet$ $\mathcal{D}(d)$ consists of all legal sets $\{i_{1},\dots,i_{k}\}$ with $d(W_{i_{1}},\dots,W_{i_{k}})\geq d.$

$\bullet$ $\mathcal{G}(\varepsilon^{*})$ consists of all legal sets $\{i_{1},\dots,i_{k}\}$ with $(W_{i_{1}},\dots,W_{i_{k}})$ being $\varepsilon^{*}$ -regular.

Given any legal $(k-1)$ -set $S=\{i_{1},\dots,i_{k-1}\}\subseteq V(\mathcal{R})$ , we first show that $\deg_{\mathcal{D}}(S)\geq(\frac{1}{2}+\frac{\varepsilon}{2})t$ . Consider the $(k-1)$ -tuple $(W_{i_{1}},\dots,W_{i_{k-1}})$ corresponding to $S$ with $m_{0}:=|W_{i_{j}}|\leq n/t$ . Then the number of edges

e_{H}(W_{i_{1}},\cdots,W_{i_{k-1}},V(H)\setminus V_{0})\geq m_{0}^{k-1}\cdot(\frac{1}{2}+\varepsilon-k\varepsilon^{*})n.

Assume that $\deg_{\mathcal{D}}(S)<(\frac{1}{2}+\frac{\varepsilon}{2})t$ . We obtain

e_{H}(W_{i_{1}},\cdots,W_{i_{k-1}},V(H)\setminus V_{0})<(\frac{1}{2}+\frac{\varepsilon}{2})tm_{0}^{k}+tdm_{0}^{k}\leq m_{0}^{k-1}\cdot(\frac{1}{2}+\frac{\varepsilon}{2}+d)n,

which gives a contradiction since we can select $d+k\varepsilon^{*}\leq\varepsilon/2$ .

On the other hand, since there are at most $k^{k}\varepsilon^{*}t^{k}$ irregular $k$ -tuples, by double counting, the number of legal $(k-1)$ -sets $S$ such that $\deg_{\mathcal{G}}(S)<(1-\sqrt{\varepsilon^{*}})t$ is at most

\frac{k\cdot k^{k}\varepsilon^{*}t^{k}}{\sqrt{\varepsilon^{*}}t}:=\xi t^{k-1}.

Since $\mathcal{R}=\mathcal{D}\cap\mathcal{G}$ , for those legal $(k-1)$ -sets $S$ satisfying both $\deg_{\mathcal{D}}(S)\geq(\frac{1}{2}+\frac{\varepsilon}{2})t$ and $\deg_{\mathcal{G}}(S)\geq(1-\sqrt{\varepsilon^{*}})t$ , we have $\deg_{\mathcal{R}}(S)\geq(\frac{1}{2}+\frac{\varepsilon}{2}-\sqrt{\varepsilon^{*}})t$ . Hence the proposition follows.

The following theorem from [22] guarantees the existence of an almost perfect matching in the cluster hypergraph.

Theorem 6.1 ( [22, Theorem 11]).

Let $t_{0}$ be an integer and $R$ be a $k$ -partite $k$ -graph with each part having $t$ vertices. Put

\delta^{\prime}:=\begin{cases}\lceil t/k\rceil&\text{if\ }t\equiv 0\bmod k\text{\ or\ }t\equiv k-1\bmod k\\ \lfloor t/k\rfloor&\text{otherwise}.\end{cases}

Suppose that there are fewer than $t_{0}^{k-1}$ legal $(k-1)$ -sets $S$ satisfying $\deg_{R}(S)<\delta^{\prime}$ . Then $R$ has a matching which covers all but at most $(k-1)t_{0}-1$ vertices in each part of $R$ .

We apply Theorem 6.1 with the cluster hypergraph $\mathcal{R}$ and $t_{0}:=\lfloor\xi^{\frac{1}{k-1}}t\rfloor$ and obtain an almost perfect matching of $\mathcal{R}$ covering all but at most $\xi^{\prime}t$ vertices in each part, where $\xi^{\prime}:=(k-1)\xi^{\frac{1}{k-1}}$ .

The next fact says that we are able to find almost $F$ -tiling in a $(\varepsilon^{*},d)$ -regular $k$ -tuples.

Fact 6.4.

Suppose that $\varepsilon^{*}\ll d$ and $m_{0}$ is sufficiently large. Suppose that $(W_{1},\dots,W_{k})$ is $(\varepsilon^{*},d)$ -regular and each $|W_{i}|=m_{0}$ for $i\in[k]$ . Then there exists an $F$ -tiling on $W_{1}\cup\cdots\cup W_{k}$ covering all but at most $\varepsilon^{*}m_{0}$ vertices in each $W_{i}$ .

Proof.

Since $(W_{1},\dots,W_{k})$ is $(\varepsilon^{*},d)$ -regular, then for any $A_{i}\subseteq W_{i}$ with $|A_{i}|\geq\varepsilon^{*}|W_{i}|$ , $i\in[k]$ , $e_{H}(A_{1},\dots,A_{k})\geq(d-\varepsilon^{*})|A_{1}|\cdots|A_{k}|$ . By Proposition 3.4, $H[A_{1}\cup\cdots\cup A_{k}]$ contains at least one copy of $F$ . Thus, we greedily pick vertex-disjoint copy of $F$ from $W_{1}\cup\cdots\cup W_{k}$ until at most $\varepsilon^{*}m_{0}$ vertices left in each part.

Fact 6.4 implies that for every edge in the almost perfect matching of $\mathcal{R}$ , there is an almost $F$ -tiling in the corresponding $k$ -tuple. Overall, we finally get an $F$ -tiling of $H$ covering all but at most

k\varepsilon_{0}n+\xi^{\prime}tm_{0}+\varepsilon^{*}m_{0}t\leq(k\varepsilon_{0}+\xi^{\prime}+\varepsilon^{*})n\leq\omega n

vertices in each part of $H$ .

6.3 Proof of Theorem 1.4

We now prove Theorem 1.4.

Proof of Theorem 1.4.

Suppose that $1/n\ll\omega,\gamma^{\prime}\ll\gamma\ll\varepsilon<1$ and $m,k,n\in\mathbb{N}$ with $k\geq 3$ . Let $F$ be a $k$ -partite $k$ -graph with each part having $m$ vertices, and let $H$ be a $k$ -partite $k$ -graph with each part having $n$ vertices such that $\delta^{\prime}_{k-1}(H)\geq(\frac{1}{2}+\varepsilon)n$ and $n\in m\mathbb{N}$ . By Lemma 3.2, there exists a balanced vertex set $W\subseteq V(H)$ with $|W|\leq\gamma n$ such that for any balanced vertex set $U\subseteq V(H)\setminus W$ with $|U|\leq\gamma^{\prime}n$ and $|U|\in km\mathbb{N}$ , both $H[W]$ and $H[W\cup U]$ contain $F$ -factors. Let $H^{\prime}:=H[V(H)\setminus W]$ be the induced subgraph of $H$ . Note that $H^{\prime}$ is a balanced $k$ -parite $k$ -graph with each part having at least $(1-\gamma/k)n$ vertices and

\delta^{\prime}_{k-1}(H^{\prime})\geq(\frac{1}{2}+\varepsilon-\frac{\gamma}{k})n.

Applying Lemma 6.1 on $H^{\prime}$ with $\omega=\gamma^{\prime}/k$ and $\varepsilon-\frac{\gamma}{k}$ in place of $\varepsilon$ , we obtain an $F$ -tiling that covers all but a balanced set $U$ of at most $\gamma^{\prime}n$ vertices. By the absorbing property of $W$ , $H[W\cup U]$ contains $F$ -factor, which together give an $F$ -factor of $H$ .

7 Concluding Remarks

In this paper, we focus on the density condition and partite minimum codegree condition for embedding balanced factors. Note that our arguments with minor adjustments actually apply to non-balanced case to get that the density threshold for embedding all non-balanced $k$ -partite $k$ -graphs is also $1/2$ under the condition of the host $k$ -partite $k$ -graph possessing the corresponding divisibility assumption and vanishing partite minimum codegree.

We also note that Mycroft gave the non-multipartite version of Theorem 1.4 in [28, Theorem 1.1] (including non-balanced case) and in particular showed that the asymptotic minimum codegree threshold of balanced complete $k$ -partite $k$ -graphs in non-multipartite host $k$ -graphs is $n/2$ . Our results from Theorem 1.2 and Theorem 1.4 gave the same value of asymptotic partite minimum codegree threshold of balanced complete $k$ -partite $k$ -graphs when the host $k$ -graphs are $k$ -partite, which in fact implies the threshold in non-multipartite case by considering a random partition into $k$ parts.

Acknowledgements. The author would like to thank Oleg Pikhurko for proposing this problem, also for helpful discussions and writing suggestions.

References

[1] R. Aharoni, A. Georgakopoulos, and P. Sprüssel. Perfect matchings in $r$ -partite $r$ -graphs. European J. Combin., 30(1):39–42, 2009.
[2] N. Alon and J. H. Spencer. The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.
[3] F. R. K. Chung. Regularity lemmas for hypergraphs and quasi-randomness. Random Structures Algorithms, 2(2):241–252, 1991.
[4] F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs. Combinatorica, 9(4):345–362, 1989.
[5] O. Cooley, N. Fountoulakis, D. Kühn, and D. Osthus. Embeddings and Ramsey numbers of sparse $k$ -uniform hypergraphs. Combinatorica, 29(3):263–297, 2009.
[6] K. Corradi and A. Hajnal. On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar., 14:423–439, 1963.
[7] B. Csaba and M. Mydlarz. Approximate multipartite version of the Hajnal-Szemerédi theorem. J. Combin. Theory Ser. B, 102(2):395–410, 2012.
[8] L. Ding, J. Han, S. Sun, G. Wang, and W. Zhou. Tiling multipartite hypergraphs in quasi-random hypergraphs. J. Combin. Theory Ser. B, 160:36–65, 2023.
[9] P. Erdős. On extremal problems of graphs and generalized graphs. Israel J. Math., 2:183–190, 1964.
[10] E. Fischer. Variants of the Hajnal-Szemerédi theorem. J. Graph Theory, 31(4):275–282, 1999.
[11] A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. Combinatorial theory and its applications, 2:601–623, 1970.
[12] J. Han. Decision problem for perfect matchings in dense $k$ -uniform hypergraphs. Trans. Amer. Math. Soc., 369(7):5197–5218, 2017.
[13] J. Han and A. Treglown. The complexity of perfect matchings and packings in dense hypergraphs. J. Combin. Theory Ser. B, 141:72–104, 2020.
[14] J. Han, C. Zang, and Y. Zhao. Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs. J. Combin. Theory Ser. A, 149:115–147, 2017.
[15] J. Han, C. Zang, and Y. Zhao. Matchings in $k$ -partite $k$ -uniform hypergraphs. J. Graph Theory, 95(1):34–58, 2020.
[16] A. Johansson, J. Kahn, and V. Vu. Factors in random graphs. Random Structures Algorithms, 33(1):1–28, 2008.
[17] P. Keevash and R. Mycroft. A geometric theory for hypergraph matching. Mem. Amer. Math. Soc., 233(1098):vi+95, 2015.
[18] P. Keevash and R. Mycroft. A multipartite Hajnal-Szemerédi theorem. J. Combin. Theory Ser. B, 114:187–236, 2015.
[19] Y. Kohayakawa, V. Rödl, and J. Skokan. Hypergraphs, quasi-randomness, and conditions for regularity. J. Combin. Theory Ser. A, 97(2):307–352, 2002.
[20] J. Komlós, G. N. Sárközy, and E. Szemerédi. Blow-up lemma. Combinatorica, 17(1):109–123, 1997.
[21] D. Kühn, R. Mycroft, and D. Osthus. Hamilton $l$ -cycles in uniform hypergraphs. J. Combin. Theory Ser. A, 117(7):910–927, 2010.
[22] D. Kühn and D. Osthus. Matchings in hypergraphs of large minimum degree. J. Graph Theory, 51(4):269–280, 2006.
[23] J. Lenz and D. Mubayi. Perfect packings in quasirandom hypergraphs I. J. Combin. Theory Ser. B, 119:155–177, 2016.
[24] A. Lo and K. Markström. A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs. Combin. Probab. Comput., 22(1):97–111, 2013.
[25] A. Lo and K. Markström. Perfect matchings in 3-partite 3-uniform hypergraphs. J. Combin. Theory Ser. A, 127:22–57, 2014.
[26] A. Lo and K. Markström. $F$ -factors in hypergraphs via absorption. Graphs Combin., 31(3):679–712, 2015.
[27] R. Martin and E. Szemerédi. Quadripartite version of the Hajnal-Szemerédi theorem. Discrete Math., 308(19):4337–4360, 2008.
[28] R. Mycroft. Packing $k$ -partite $k$ -uniform hypergraphs. J. Combin. Theory Ser. A, 138:60–132, 2016.
[29] O. Pikhurko. Perfect matchings and $K^{3}_{4}$ -tilings in hypergraphs of large codegree. Graphs Combin., 24(4):391–404, 2008.
[30] C. Reiher, V. Rödl, and M. Schacht. Embedding tetrahedra into quasirandom hypergraphs. J. Combin. Theory Ser. B, 121:229–247, 2016.
[31] C. Reiher, V. Rödl, and M. Schacht. On a generalisation of Mantel’s theorem to uniformly dense hypergraphs. Int. Math. Res. Not. IMRN, (16):4899–4941, 2018.
[32] V. Rödl, A. Ruciński, and E. Szemerédi. A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput., 15(1-2):229–251, 2006.
[33] V. Rödl and M. Schacht. Regular partitions of hypergraphs: counting lemmas. Combin. Probab. Comput., 16(6):887–901, 2007.
[34] V. Rödl and M. Schacht. Regular partitions of hypergraphs: regularity lemmas. Combin. Probab. Comput., 16(6):833–885, 2007.

Tilings in quasi-random kk-partite hypergraphs

Abstract

1 Introduction

Definition 1.1 ((p,μp,\mu)-denseness).

Theorem 1.1.

Theorem 1.2.

Theorem 1.3.

Theorem 1.4.

2 Avoiding FF-factors

Proof of Theorem 1.2.

Proof of Theorem 1.3.

3 The Absorption Technique

Lemma 3.1 (Absorbing Lemma I).

Lemma 3.2 (Absorbing Lemma II).

Lemma 3.3.

Proposition 3.4.

Proof of Lemma 3.3.

Lemma 3.5.

Proof.

Lemma 3.6.

Proof.

Lemma 3.7.

Lemma 3.8.

Lemma 3.9.

Lemma 3.10.

Proof.

Proof of Lemma 3.1.

Proof of Lemma 3.2.

4 The Hypergraph Regularity Lemma

4.1 Regular complexes

Definition 4.1 ((d2,…,dk,δk,δ,r)(d_{2},\dots,d_{k},\delta_{k},\delta,r)-regular complexes).

4.2 Equitable partition

Definition 4.2 ((η,δ,t)(\eta,\delta,t)-equitable).

4.3 Statement of the regularity lemma.

Definition 4.3 ((δk,r)(\delta_{k},r)-regular w.r.t. 𝒫\mathcal{P}).

Theorem 4.4 (Regularity lemma [34, Theorem 17]).

Lemma 4.5.

4.4 Statement of a counting lemma.

Lemma 4.6.

4.5 Reduced Hypergraphs.

4.6 Proof of Lemma 3.9.

Proof of Lemma 3.9.

5 Proof of Theorem 1.1

Lemma 5.1 (Almost Perfect Tiling I).

Proof.

Proof of Theorem 1.1.

6 Proof of Theorem 1.4

Lemma 6.1 (Almost Perfect Tiling II).

6.1 Weak regularity lemma for hypergraphs

Lemma 6.2 (Weak regularity lemma for hypergraphs).

6.2 Proof of Lemma 6.1

Proof of Lemma 6.1.

Proposition 6.3.

Proof.

Theorem 6.1 ( [22, Theorem 11]).

Fact 6.4.

Proof.

6.3 Proof of Theorem 1.4

Proof of Theorem 1.4.

7 Concluding Remarks

References

Tilings in quasi-random $k$ -partite hypergraphs

Definition 1.1 (( $p,\mu$ )-denseness).

2 Avoiding $F$ -factors

Definition 4.1 ( $(d_{2},\dots,d_{k},\delta_{k},\delta,r)$ -regular complexes).

Definition 4.2 ( $(\eta,\delta,t)$ -equitable).

Definition 4.3 ( $(\delta_{k},r)$ -regular w.r.t. $\mathcal{P}$ ).