Covering and tiling hypergraphs with tight cycles
Jie Han Allan Lo Nicolás Sanhueza-Matamala



a4paper,tmargin=2.6cm,bmargin=2.6cm,lmargin=2.6cm,rmargin=2.6cm,headheight=1cm,headsep=1cm,footskip=1cm












 







theoremTheorem
plain
acknowledgementAcknowledgement
algorithmAlgorithm
axiomAxiom
caseCase
claim[theorem]Claim
*claim*Claim
conclusionConclusion
construction[theorem]Construction
conditionCondition
conjecture[theorem]Conjecture
corollary[theorem]Corollary
criterionCriterion
definition[theorem]Definition
example[theorem]Example
exerciseExercise
fact[theorem]Fact
lemma[theorem]Lemma
notationNotation
problem[theorem]Problem
proposition[theorem]Proposition
question[theorem]Question
*question*Question
remark[theorem]Remark
solutionSolution
summarySummary
obs[theorem]Observation
equationsection
theoremsection
casesection
subcaseCase
subcasecase

𝒜
ℬ
𝒞
ℰ
ℱ
𝒢
𝒦
𝒥
ℳ
𝒩
𝒬
α
ε
ε
γ̊
𝒫
𝒫
ℕ
𝒯
𝐝
𝐢
𝐮
𝐯
H
ℛ
𝒴
ḍẹg̣



=
e.g.


proofclaim[1][Proof of the claim]

#1
#1
=[]=[

]
calc





Covering and tiling hypergraphs with tight cycles]Covering and tiling hypergraphs with tight cycles

Department of Mathematics, University of Rhode Island, Kingston, RI, USA, 02881
jie_han@uri.edu

The research leading to these results was partially supported by FAPESP (Proc. 2013/03447-6, 2014/18641-5, 2015/07869-8) (J. Han) EPSRC, grant no. EP/P002420/1 (A. Lo) and the Becas Chile scholarship scheme from CONICYT (N. Sanhueza-Matamala).

School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
s.a.lo@bham.ac.uk, NIS564@bham.ac.uk




 
	A k-uniform tight cycle C^k_s is a hypergraph on s > k vertices with a cyclic ordering such that every k consecutive vertices under this ordering form an edge.
	The pair (k,s) is admissible if (k,s) = 1 or k/(k,s) is even.
	We prove that if s ≥ 2k^2 and H is a k-uniform hypergraph with minimum codegree at least (1/2 + o(1))|V(H)|, then every vertex is covered by a copy of C^k_s.
	The bound is asymptotically sharp if (k,s) is admissible.
	Our main tool allows us to arbitrarily rearrange the order of which a tight path wraps around a complete k-partite k-uniform hypergraph, which may be of independent interest.
	
	For hypergraphs F and H, a perfect F-tiling in H is a spanning collection of vertex-disjoint copies of F.
	For k ≥ 3, there are currently only a handful of known F-tiling results when F is k-uniform but not k-partite.
	If s ≢0 k, then C^k_s is not k-partite.
	Here we prove an F-tiling result for a family of non k-partite k-uniform hypergraphs F.
	Namely, for s ≥ 5k^2, every k-uniform hypergraph H with minimum codegree at least (1/2 + 1/(2s) + o(1))|V(H)| has a perfect C^k_s-tiling.
	Moreover, the bound is asymptotically sharp if k is even and (k,s) is admissible.


[
    Nicolás Sanhueza-Matamala
    December 30, 2023
=============================





§ INTRODUCTION


Let  and F be graphs.
An F-tiling in H is a set of vertex-disjoint copies of F.
An F-tiling is perfect if it spans the vertex set of .
Note that a perfect F-tiling is also known as an F-factor or a perfect F-matching.
The following question in extremal graph theory has a long and rich story: given F and n, what is the maximum δ such that there exists a graph H on n vertices with minimum degree at least δ without a perfect F-tiling?
We call such δ the tiling degree threshold for F and denote it by t(n, F).
Note that if n ≢0  |V(F)| then a perfect F-tiling cannot exist, so this case is not interesting.
Hence we will always assume that n ≡ 0  |V(F)| whenever we discuss t(n, F).


A first result in the study of tiling thresholds in graphs comes from the celebrated theorem of Dirac <cit.> on Hamiltonian cycles, which easily shows that t(n, K_2) = n/2 - 1.
Corrádi and Hajnal <cit.> proved that t(n, K_3) = 2n/3 - 1,
and Hajnal and Szemerédi <cit.> generalized this result for complete graphs of any size, showing that t(n, K_t) = (1 - 1/t)n -1.
For a general graph F, Kühn and Osthus <cit.> determined t(n, F) up to an additive constant depending only on F. This improved previous results due to Alon and Yuster <cit.>, Komlós, Sárközy and Szemerédi <cit.> and Komlós <cit.>.

We study tilings in the setting of k-graphs, i.e. hypergraphs where every edge has exactly k vertices, for some k ≥ 2.
We focus on tilings using “tight cycles”, which are k-graphs that generalise the usual notion of cycles in graphs.
We also study the related problem of finding F-coverings in a hypergraph , that is, finding copies of F, not necessarily vertex-disjoint, which together cover every vertex of .
After choosing a notion of “minimum degree” for k-uniform hypergraphs, both tilings and coverings give rise to corresponding questions in extremal hypergraph theory, which generalise the “tiling thresholds” in graphs to the setting of hypergraphs.
In what follows, we describe precisely all of the problems under consideration.



 §.§ Tiling thresholds


A hypergraph = (V(),E()) consists of a vertex set V() and an edge set E(), where each edge e ∈ E() is a subset of V().
We will simply write V and E for V(H) and E(H), respectively, if it is clear from the context.
Given a set V and a positive integer k, Vk denotes the set of subsets of V with size exactly k.
We say that  is a k-uniform hypergraph or k-graph, for short, if E ⊆Vk. 
Note that 2-graphs are usually known simply as graphs.

Given a hypergraph  and a set S ⊆ V, let the neighbourhood N_(S) of S be the set { T ⊆ V ∖ S : T ∪ S ∈ E } and let _(S) = |N_ (S)| denote the number of edges of  containing S.
If w ∈ V, then we also write N_(w) for N_( {w} ).
We will omit the subscript if  is clear from the context.
We denote by δ_i() the minimum i-degree of , that is, the minimum of _(S) over all i-element sets S ∈Vi.
Note that δ_0() is equal to the number of edges of .
Given a k-graph , δ_k-1() and δ_1() are referred to as the minimum codegree and the minimum vertex degree of , respectively.

For k-graphs  and F, an F-tiling in H is a set of vertex-disjoint copies of F;
and an F-tiling is perfect if it spans the vertex set of .
For a k-graph F, define the codegree tiling threshold t(n, F) to be the maximum of δ_k-1() over all k-graphs  on n vertices without a perfect F-tiling.
We implicitly assume n ≡ 0  |V(F)| whenever we discuss t(n, F).

We describe known results on tiling thresholds for k-graphs, when k ≥ 3.
Let K^k_t denote the complete k-graph on t vertices.
For k ≥ 3, Kühn and Osthus <cit.> determined t(n, K^k_k) asymptotically;
the exact value was determined by Rödl, Ruciński and Szemerédi <cit.> for sufficiently large n.
Lo and Markström <cit.> determined t(n, K^3_4) asymptotically, and independently, Keevash and Mycroft <cit.> determined t(n, K^3_4) exactly for sufficiently large n.

We say that a k-graph H is t-partite (or that  is a (k,t)-graph, for short) if V has a partition { V_1, …, V_t} such that |e ∩ V_i| ≤ 1 for all edges e ∈ E and all 1 ≤ i ≤ t.
A (k,t)-graph H is complete if E consists of all k-sets e such that |e ∩ V_i| ≤ 1, for all 1 ≤ i ≤ t.
Recently, Mycroft <cit.> determined the asymptotic value of t(n, K) for all complete (k,k)-graphs K.
However, much less is known for non-k-partite k-graphs. 
For more results on tiling thresholds for k-graphs, see the survey of Zhao <cit.>.



 §.§ Covering thresholds


Given a k-graph F, an F-covering in H is a spanning set of copies of F.

Similarly, define the codegree covering threshold c(n, F) of F to be the maximum of δ_k-1() over all k-graphs  on n vertices not containing an F-covering.



Trivially, a perfect F-tiling is an F-covering, and an F-covering has a copy of F.
Thus, 
    _k-1(n, F) ≤ c(n, F) ≤ t(n, F),

where _k-1(n, F) is codegree Turán threshold, that is, the maximum of δ_k-1() over all F-free k-graphs H on n vertices.
In this sense, the covering problem is an intermediate problem between the Turán and the tiling problems.

As for results on covering thresholds, for any non-empty (2-)graph F, we have c(n, F) = ( χ(F) - 2/χ(F) - 1 + o(1) )n, see <cit.>,
where χ(F) is the chromatic number of F.
Han, Zang and Zhao <cit.> studied the vertex-degree variant of the covering problem, for complete (3,3)-graphs K.
Falgas-Ravry and Zhao <cit.> studied c(n, F) when F is K^3_4, K^3_4 with one edge removed, K^3_5 with one edge removed and other 3-graphs.
	


 §.§ Cycles in hypergraphs


Given 1 ≤ℓ < k, we say that a k-graph on more than k vertices is an ℓ-cycle if every vertex lies in some edge and there is a cyclic ordering of the vertices such that under this ordering, every edge consists of k consecutive vertices and two consecutive edges intersect in exactly ℓ vertices.
Note that an ℓ-cycle on s vertices can exist only if k - ℓ divides s.
If ℓ = 1 we call the cycle loose, if ℓ = k-1 we call the cycle tight.
We write C^k_s for the k-uniform tight cycle on s vertices.

When k = 2, ℓ-cycles reduce to the usual notion of cycles in graphs.
Corrádi and Hajnal <cit.> determined t(n, C^2_3) and Wang Wang2010, Wang2012 determined t(n, C^2_4) and t(n, C^2_5).
In fact, El-Zahar <cit.> gave the following conjecture on cycle tilings.

	Let G be a graph on n vertices and let n_1, …, n_r ≥ 3 be integers such that n_1 + … + n_r = n.
	If δ(G) ≥∑_i=1^r ⌈ n_i / 2 ⌉, then G contains r vertex-disjoint cycles of lengths n_1, …, n_r respectively.

The bound on the minimum degree, if true, would be best possible.
In particular, the conjecture would imply that t(n, C^2_s) =  ⌈ s / 2 ⌉ n / s - 1.
The conjecture was verified for r = 2 by El-Zahar and a proof (for large n) was announced by Abbasi <cit.> as well as by Abbasi, Khan, Sárközy and Szemerédi (see <cit.>).

Given integers ℓ, k such that 1 ≤ℓ≤ (k-1)/2, it is easy to see that a k-uniform ℓ-cycle on s vertices C satisfies c(n, C) ≤ s+1 (by constructing C greedily).
If s ≡ 0  k, then the tight cycle C^k_s is k-partite.
For all t ≥ 1, let K^k(t) denote the complete (k,k)-graph whose vertex classes each have size t.
Note that C^k_s is a spanning subgraph of K^k(s/k).
Erdős <cit.> proved the following result, which implies an upper bound on the Turán number of C^k_s. 

 
	For all k ≥ 2 and s > 1, there exists n_0 = n_0(k,s) such that ( n, K^k(s) )  < n^k - 1/s^k-1 for all n ≥ n_0.


Our first result is a sublinear upper bound for c(n, C^k_s) when s ≡ 0  k.

 
	For all 2 ≤ k ≤ s with s ≡ 0  k, there exist n_0(k, s) and c = c(k, s) such that c(n, C_s^k) ≤ cn^1 - 1/s^k-1 for all n ≥ n_0.


There are some previously known results for tiling problems regarding ℓ-cycles.
Whenever C is a 3-uniform loose cycle, t(n, C) was determined exactly by Czygrinow <cit.>.
For general loose cycles C in k-graphs, t(n, C) was determined asymptotically by Mycroft <cit.> and exactly by Gao, Han and Zhao <cit.>.
For tight cycles C^k_s with s ≡ 0  k, Mycroft <cit.> proved that t(n, C^k_s) = (1/2 + o(1))n.
Notice that all mentioned cycle tiling results correspond to cases where the cycles are k-partite (since k-uniform loose cycles are k-partite for k ≥ 3).

We now focus on the covering and tiling problems for the tight cycle C^k_s, for all integers k,s which do not necessarily make C^k_s a (k,k)-graph.
We show that a minimum codegree of (1/2+o(1))n suffices to find a C^k_s-covering.

 
	Let k, s ∈ℕ with k ≥ 3 and s ≥ 2k^2.
	For all γ > 0, there exists n_0 = n_0(k, s, γ) such that for all n ≥ n_0, c(n, C^k_s) ≤ (1/2 + γ)n.


Moreover, this result is asymptotically tight if k and s satisfy the following divisibility conditions.
Let 2 ≤ k < s and let d = (k,s). We say that the pair (k,s) is admissible if d = 1 or k/d is even.
Note that an admissible pair (k,s) satisfies s ≢0  k.

 
	Let 3 ≤ k < s be such that (k,s) is admissible.
	Then c(n, C^k_s) ≥⌊ n / 2 ⌋ - k + 1.
	Moreover, if k is even, then _k-1(n, C^k_s) ≥⌊ n / 2 ⌋ - k + 1.


Notice that if (k,s) is admissible, k ≥ 3 is even and s ≥ 2k^2, then Theorem <ref> and Proposition <ref> imply that _k-1(n, C^k_s) = (1/2 + o(1))n.

We also study the tiling problem corresponding to C^k_s.
We give some lower bounds on t(n, C^k_s).
Notice that the bound is significantly higher if (k,s) is admissible.

 
	Let 2 ≤ k < s ≤ n with n divisible by s.
	Then t(n, C^k_s) ≥⌊ n/2 ⌋ - k.
	Moreover, if (k,s) is admissible, then
	
    t(n, C_s^k) ≥⌊(1/2 + 1/2s) n ⌋ - k    if k is even,
    ⌊( 1/2 + k/4s(k-1) + 2k)  n ⌋- k    if k is odd.
	


On the other hand, recall that the case s ≡ 0  k was solved asymptotically by Mycroft <cit.>, thus we study the complementary case.
We prove an upper bound on t(n, C^k_s) which is valid whenever s ≢0  k and s ≥ 5k^2.
Note that the bound is asymptotically sharp if k is even and (k,s) is admissible.

 
	Let 3 ≤ k < s be such that s ≥ 5k^2 and s ≢0  k.		
	Then, for all γ > 0, there exists n_0 = n_0(k, s, γ) such that for all n ≥ n_0 with n ≡ 0  s, 
    t(n, C_s^k) ≤( 1/2 + 1/2s + γ)n.





 §.§ Organisation of the paper


In Section <ref> we set up basic notation and give sketches of the proofs of our main results, Theorems <ref> and <ref>.

In Section <ref> we give constructions which imply lower bounds for the Turán numbers and covering and tiling thresholds of tight cycles, thus proving Propositions <ref> and <ref>.

In the next two sections we study the covering problem.
In Section <ref> we describe a family of gadgets which will be useful during the proofs of Proposition <ref> and Theorem <ref>.
Those proofs are done in Section <ref>.

Sections <ref>–<ref> are dedicated to investigating the tiling problem.
Our aim is the proof of Theorem <ref>, i.e. bounding t(n, C^k_s) from above.
In Section <ref>, we review the absorption technique for tilings, which we use in Section <ref> to prove Theorem <ref> under the assumption that we can find an almost perfect C^k_s-tiling (Lemma <ref>).
We prove Lemma <ref> in the next two sections: in Section <ref> we review tools of hypergraph regularity and in Section <ref> we introduce various auxiliary tilings that we use to finish the proof.

We conclude with some remarks and open problems in Section <ref>.



§ NOTATION AND SKETCHS OF PROOFS
 

For a hypergraph  and S ⊆ V, we denote [S] to be the subgraph of  induced on S, that is, V([S]) = S and E([S]) = { e ∈ E : e ⊆ S }.
Let ∖ S = H[V ∖ S].
For hypergraphs  and G, let - G be the subgraph of  obtained by removing all edges in E() ∩ E(G).

Given a, b, c reals with c > 0, by a = b ± c we mean that b - c ≤ a ≤ b + c.
We write x ≪ y to mean that for all y ∈ (0,1] there exists an x_0 ∈ (0,1) such that for all x ≤ x_0 the subsequent statement holds.
Hierarchies with more constants are defined in a similar way and are to be read from the right to the left.
We will always assume that the constants in our hierarchies are reals in (0,1].
Moreover, if 1/x appears in a hierarchy, this implicitly means that x is a natural number.

For all k-graphs  and all x ∈ V, define the link (k-1)-graph (x) of x in  to be the (k-1)-graph with V((x)) = V ∖{ x} and E((x)) = N_(x).
Given integers a_1, …, a_t ≥ 1, let K^k(a_1, …, a_t) denote the complete (k,t)-graph with vertex partition V_1, …, V_t such that |V_i| = a_i for all 1 ≤ i ≤ t.

For a family ℱ of k-graphs, an ℱ-tiling is a set of vertex-disjoint copies of (not necessarily identical) members of ℱ.

For a sequence of distinct vertices v_1, …, v_s in a k-graph H, we say P=v_1 … v_s is a tight path if all k consecutive vertices form an edge.
Note that all tight paths have an associated ordering of vertices.
Hence, v_1 … v_s and v_s … v_1 are assumed to be different tight paths, even if the corresponding subgraphs they define are the same.


Suppose that P_1 = v_1 … v_s and P_2 = w_1 … w_s' are two vertex-disjoint tight paths in a k-graph H.
If it happens that v_1 … v_s w_1 … w_s' is also a tight path in H, then we will denote it by P_1 P_2.
We sometimes refer to P_1 P_2 as the concatenation of P_1 and P_2.
Note that P_1P_2 has more edges than P_1 ∪ P_2. 
We naturally extend this definition (whenever it makes sense) to the concatenation of a sequence of paths P_1, …, P_r, and we denote the resulting path by P_1 … P_r.
For two tight paths P_1 and P_2, we say that P_2 extends P_1, if P_2 = P_1 P' for some tight path P' (where we may have |V(P')| < k, that is, P' contains no edge).
Also, we may define a tight cycle C by writing C = v_1 … v_s, whenever v_i… v_s v_1 … v_i-1 is a tight path for all 1 ≤ i ≤ s.

For all k ∈ℕ,  let [k] = {1, …, k }. Let S_k be the symmetric group of all permutations of the set [k], with the composition of functions as the group operation. Let id∈ S_k be the identity function that fixes all elements in [k]. Given distinct i_1, …, i_r ∈ [k], the cyclic permutation (i_1 i_2 … i_r) ∈ S_k is the permutation that maps i_j to i_j+1 for all 1 ≤ j < r and i_r to i_1, and fixes all the other elements; we say that such a cyclic permutation has length r. All permutations σ∈ S_k can be written as a composition of cyclic permutations σ_1 …σ_t such that these cyclic permutations are disjoint, meaning that there are no common elements between all pairs of these different cyclic permutations.

Let H be a k-graph, V_1, …, V_k be disjoint vertex sets of V and let σ∈ S_k.
We say that a tight path P = v_1 … v_ℓ in H has end-type σ with respect to V_1, …, V_k if for all 2 ≤ i ≤ k, v_ℓ - k + i∈ V_σ(i). Similarly, we say P has start-type σ with respect to V_1, …, V_k if v_i∈ V_σ(i) for all 1 ≤ i ≤ k-1. If H and V_1, …, V_k are clear from the context, we simply say that P has end-type σ and start-type σ, respectively.
Note that one could define start-type and end-type in terms of (k-1)-tuples in [k] instead. 
However, for our purposes, it is more convenient to define it in terms of permutations of [k].




 §.§ Sketches of proofs of Theorems <ref> and <ref>

We now sketch the proof of Theorem <ref>.
Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + γ)n.
Consider any vertex x ∈ V().
We can show that, for some appropriate value of t, x is contained in some copy K of K^k_k(t) with vertex classes V_1, …, V_k. 
Suppose that s ≡ r ≢0  k with 1 ≤ r < k.
Suppose P = v_1 … v_k is a tight path in K such that v_i ∈ V_i for all 1 ≤ i ≤ k and v_1 = x.
By wrapping around K, we may find a tight path P_2 = v_1 … v_ℓ which extends P_1, but if we only use vertices and edges of K, then we have v_j ∈ V_ℓ where j ≡ℓ k, for all j ∈ [ℓ].
To break this pattern, we will use some gadgets (see Section <ref> for a formal definition).
Roughly speaking, a gadget is a k-graph on V(K) and some extra vertices of H.
Using these gadgets we can extend P to a tight path P' with end-type σ, for an arbitrary σ∈ S_k (see Lemma <ref>).
Having done that (and choosing σ appropriately), then it is easy to extend P' into a copy of C_s^k by wrapping around V_1, …, V_k.


The proof of Theorem <ref> uses the absorbing method, introduced by Rödl, Ruciński and Szemerédi <cit.>.
We first find a small vertex set U ⊆ V(H) such that H[U ∪ W] has a perfect C_s^k-tiling for all small sets W with |U| + |W| ≡ 0  s. 
Thus the problem of finding a perfect C_s^k-tiling is reduced to finding a C_s^k-tiling in H ∖ U covering almost all of the remaining vertices.
However, we do not find such C_s^k-tiling directly.
First we show that there exists a k-graph F_s on s vertices containing a C_s^k which has a particularly useful structure: it is obtained from a complete (k,k)-graph by adding a few extra vertices.
So finding an almost perfect F_s-tiling suffices.
Instead, we show that there exists an { F_s, E_s }-tiling  for some suitable k-graph E_s, subject to the minimisation of some objective function ϕ().
We do so by considering its fractional relaxation, which we call a weighted fractional { F^∗_s, K^∗_s }-tiling (see Section <ref>).
Further, we use the hypergraph regularity lemma in the form of `regular slice lemma' of Allen, Böttcher, Cooley and Mycroft <cit.>.



§ LOWER BOUNDS
 

In this section, we construct k-graphs which give lower bounds for the codegree Turán numbers and covering and tiling thresholds for tight cycles.
These constructions will imply Proposition <ref> and Proposition <ref>.




We remark that the bounds obtained here can be improved by an additive constant via careful calculations and case distinctions, which we omit for the sake of giving a clear presentation.

Let A and B be disjoint vertex sets.
Define ^k_0 = ^k_0(A,B) to be the k-graph on A ∪ B such that the edges of ^k_0 are exactly the k-sets e of vertices that satisfy |e ∩ B| ≡ 1  2.
Note that δ_k-1(^k_0) ≥min{ |A|,|B| } - k + 1.







 
	Let 3 ≤ k ≤ s and d = (k,s).
	Let A and B be disjoint vertex sets.
	Suppose that H^k_0(A,B) contains a tight cycle C^k_s on s vertices with V(C^k_s) ∩ A ≠∅.
	Then |V(C^k_s) ∩ A| ≡ 0  s/d and (k,s) is not an admissible pair.



	Let C_s^k = v_1 … v_s.
	For all 1 ≤ i ≤ s, let ϕ_i ∈{ A, B } be such that v_i ∈ϕ_i and let ϕ_s + i = ϕ_i.
	If two edges e and e' in E(H^k_0(A,B)) satisfy |e ∩ e'| = k-1, then |e ∩ A| = |e' ∩ A| by construction.
	Thus ϕ_i + k = ϕ_i for all 1 ≤ i ≤ s.
	Therefore, ϕ_i+d = ϕ_i for all 1 ≤ i ≤ s.
	Hence, |V(C_s^k) ∩ A| ≡ 0  s/d.
	
	Let r = |{ v_1, …, v_k }∩ A| = |{ i: 1 ≤ i ≤ k, ϕ_i = A }|.
	Note that r > 0 and r ∈{ k/d, 2k/d, …, k }.
	Since { v_1, …, v_k } is an edge in H^k_0(A,B), it follows that k-r ≡ 1  2 and so, r ≢k  2.
	This implies d ≥ 2 and k/d is odd, i.e. (k,s) is not an admissible pair.


Now we use Proposition <ref> to prove Propositions <ref> and <ref>.


	Let A and B be disjoint vertex sets of sizes |A| = ⌊ n/2 ⌋ and |B| = ⌈ n/2 ⌉.
	Consider the k-graph _0 = ^k_0(A,B).
	By Proposition <ref>, no vertex of A can be covered with a copy of C^k_s.
	Then c(n, C^k_s) ≥δ_k-1(H_0) ≥⌊ n / 2 ⌋ - k + 1.
	
	Moreover, if k is even, then H^k_0(A,B) = H^k_0(B,A).
	So no vertex of B can be covered by a copy of C^k_s.
	Hence _0 is C^k_s-free.
	Therefore, _k-1(n, C^k_s) ≥δ_k-1(H_0) ≥⌊ n / 2 ⌋ - k + 1.



	To see the first part of the statement, let d := (k,s) and s' := s/d. 
	Note that d ≤ k < s, thus s' > 1.
	Let A and B be disjoint vertex sets chosen such that |A| + |B| = n, | |A| - |B| | ≤ 2 and |A| ≢0  s'.
	Consider the k-graph H_0 = H^k_0(A,B) and note that δ_k-1(H_0) ≥min{ |A|,|B| } - k + 1 ≥⌊ n/2 ⌋ - k.
	Proposition <ref> implies that all copies C of C^k_s in _0 satisfy |V(C) ∩ A| ≡ 0  s'.


	Since |A| ≢0  s', it is impossible to cover all vertices in A with vertex-disjoint copies of C_s^k.
	This proves that t(n, C^k_s) ≥δ_k-1(_0) ≥⌊ n/2 ⌋ - k as desired.
	
	Now suppose that (k,s) is an admissible pair.
	Let  be the k-graph on n vertices with a vertex partition {A, B, T} with |A| = ⌈ (n - |T|) / 2 ⌉ and |B| = ⌊ (n - |T|)/2 ⌋, where |T| will be specified later.
	The edge set of  consists of all k-sets e such that |e ∩ B| ≡ 1  2 or e ∩ T ≠∅.
	Note that δ_k-1() ≥min{|A|, |B| } + |T| - (k-1) ≥⌊ (n + |T|)/2 ⌋ - k + 1. We separate the analysis into two cases depending on the parity of k.
	Case 1: k even.
	Since [A ∪ B] = ^k_0(A, B) = ^k_0(B,A), by Proposition <ref>, [A ∪ B] is C^k_s-free.
	Thus, all copies of C^k_s in  must intersect T in at least one vertex.
	Hence, all C^k_s-tilings have at most |T| vertex-disjoint copies of C^k_s.
	Taking |T| = n/s - 1 assures that  does not contain a perfect C^k_s-tiling.
	This implies that t(n, C^k_s) ≥⌊(1/2 + 1/(2s) ) n ⌋ - k.
	Case 2: k odd.
	Since [A ∪ B] = ^k_0(A,B), by Proposition <ref> no vertex in A can be covered by a copy of C^k_s.
	Hence, all copies of C^k_s in  with non-empty intersection with A must also have non-empty intersection with T.
	Moreover, all edges in  intersect A in at most k-1 vertices, so all copies of C^k_s in H intersect A in at most s(k-1)/k vertices.
	Thus a perfect C^k_s-tiling would contain at most |T| and at least k|A|/(s(k-1)) cycles intersecting A.
	Let |T| = ⌈ nk / (2s(k-1) + k) ⌉ - 1.
	Since |T| < nk/(2s(k-1)+k) and |A| ≥ (n-|T|)/2, 
    k|A|/s(k-1)≥k(n-|T|)/2s(k-1) > nk/2s(k-1)( 1 - k/2s(k-1) + k) > |T|,

	
	and thus a perfect C^k_s-tiling in  cannot exist.
	This implies
	
    t(n, C^k_s) ≥δ_k-1() ≥⌊n+|T|/2⌋ - k + 1 ≥⌊( 1/2 + k/4s(k-1) + 2k)  n ⌋ - k,

	as desired.




§ G-GADGETS
 

Throughout this section, let τ (123 … k) ∈ S_k.
Let H be a k-graph, and let K be a complete (k,k)-graph in H with its natural vertex partition { V_1, …, V_k}. 
Knowing the end-types and start-types of paths with respect to V_1, …, V_k will help us to concatenate them and form longer paths which contains them both.
For instance, if P_1 and P_2 are vertex-disjoint tight paths, P_1 has end-type π and P_2 has start-type π, then we can concatenate the paths and obtain P_1 P_2.

Let P be a tight path in H with end-type π∈ S_k.
For x ∈ V_π(1)∖ V(P), Px is a tight path of  with end-type πτ.
We call such an extension a simple extension of P.
By repeatedly applying r simple extensions (which is possible as long as there are available vertices), we may obtain an extension P x_1 … x_r of P with end-type πτ^r, using r extra vertices and edges in K.

In the same spirit, observe that if P_1 has end-type π and P_2 has start-type πτ, then the sequence of ordered clusters corresponding to the last k-1 vertices of P_1 coincides with the corresponding sequence of the first k-1 vertices of P_2.
Thus, by using one extra vertex x ∈ V_π(1)∖ (V(P_1) ∪ V(P_2)) and setting P_1 x P_2, we can join these paths.

If P is a path with end-type π, we would like to find a path P' that extends P such that |V(P')| ≡ |V(P)|  k and P' has end-type σ, for arbitrary σ∈ S_k.
The goal of this section is to define and study `G-gadgets', a tool which will allow us to do precisely that.

Let G be a 2-graph on [k] and S ⊆ V().

We say W_G ⊆ V() is a G-gadget for K avoiding S if there exists a family of pairwise-disjoint sets { W_ij : ij ∈ E(G) } such that W_G = ⋃_ij ∈ E(G) W_ij, and for all ij ∈ E(G), 

	
  * |W_ij| = 2k - 1,
	
  * |W_ij∖ V(K)| = 1, W_ij∩ S = ∅ and, for all 1 ≤ i' ≤ k,
	
    |W_ij∩ V_i'| = 
    	
    	1	   if i' ∈{i,j},
    
    	2	   otherwise,


	
  *  for all σ∈ S_k with σ(1) ∈{i, j}, [W_ij] contains a spanning tight path with start-type στ and end-type (ij) σ.

If K is clear from the context, we will just say “a G-gadget avoiding S”.
For all edges ij ∈ E(G), we write w_ij for the unique vertex in W_ij∖ V(K).

We emphasize that <ref> is the key property that allows us to obtain an extension of a path at the same time we perform a change in the end-type.
In words, <ref> says that given any k-1 ordered clusters that miss V_i, there exists a tight path with vertex set W_ij, which start with the same ordered k-1 clusters and ends with the same ordered k-1 clusters but with V_j replaced by V_i. 
In other words, W_ij allows us to “switch” the type of a path by replacing i by j.
See Figure <ref> for an example.



Suppose P is a tight path with end-type π and σ is a cyclic permutation. In the next lemma, we show how to extend P into a tight path with end-type σπ using a G-gadget, where G is a path.

 
	Let k ≥ 3 and r ≥ 2.
	Let σ =  (i_1 i_2 … i_r) ∈ S_k be a cyclic permutation. 
	Let G be a 2-graph on [k]  containing the path Q = i_1 i_2 … i_r.
	Let  be a k-graph containing a complete (k,k)-graph K with vertex partition V_1, …, V_k.
	Suppose that P is a tight path in  with end-type π∈ S_k such that π(1) = i_r.
	Suppose W_G is a G-gadget avoiding V(P) and |V_i_j∖ V(P)| ≥ 2|E(G)| for all 1 ≤ j ≤ r.
	Then there exists an extension P' of P with end-type σπ such that
	
		
  * |V(P')| = |V(P)| + 2k(r-1), 
		
  * for all 1 ≤ i ≤ k, 
		
    | V_i ∩ ( V(P') ∖ V(P) )| = 
    		
    		2 (r-1) - 1    if i ∈{i_1, i_2, …, i_r-1},
    
    		2 (r-1)	   otherwise,

		
  * there exists a (G - Q)-gadget W_G - Q for K avoiding V(P') and
		
  * V(P') ∖ V(P ∪ K) = { w_i_j i_j+1 : 1 ≤ j < r }.
	



	We proceed by induction on r.
	First suppose that r = 2 and so σ = (i_1 i_2).
	Consider a G-gadget W_G avoiding V(P).
	Since i_1 i_2 ∈ E(G), there exists a set W_i_1 i_2⊆ W_G disjoint from V(P) such that |W_i_1 i_2| = 2k - 1 and [W_i_1 i_2] contains a spanning tight path P” with start-type πτ and end-type (i_1 i_2) π = σπ. 
	Note that |V_i_2∩ W_G| ≤ 2 |E(G)| - 1, as |V_i_2∩  W_i_1i_2| =1.
	Hence V_i_2∖( V(P) ∪ W_G ) ∅.
	Take an arbitrary vertex x_i_2∈ V_i_2∖( V(P) ∪ W_G ) and set P' = P x_i_2 P”.
	Since π( 1 ) = i_2, it follows that P' is a tight path with end-type σπ, and P' satisfies properties (i), (ii) and (iv).
	Set W_G - i_1 i_2 = W_G ∖ W_i_1 i_2. Then W_G - i_1 i_2 is a (G - i_1 i_2)-gadget for K avoiding V(P'), so P' satisfies property (iii), as desired.
	
	Next, suppose r > 2. Define σ' = (i_2 i_3 … i_r) and note that σ = (i_1 i_2) σ'. Then σ' is a cyclic permutation of length r-1,  with π(1) = i_r and the path Q' = i_2 … i_r-1 i_r is a subgraph of G. By the induction hypothesis, there exists an extension P” of P with end-type σ' π such that |V(P”)| = |V(P)| + 2k(r-2) and,
	for all 1 ≤ i ≤ k, 
	
    | V_i ∩ ( V(P”) ∖ V(P) )| = 
    	
    	2 (r-2) - 1    if i ∈{i_2, i_3, …,  i_r-1},
    
    	2 (r-2)	   otherwise.

	Moreover, there exists a (G - Q')-gadget W_G - Q' avoiding V(P”) and V(P”) ∖ V(P ∪ K) = { w_i_j i_j+1 : 2 ≤ j < r }.
	
	Note that σ' π (1) = σ'( i_r ) = i_2 and i_1 i_2 ∈ E(G - Q').
	For all 1 ≤ i ≤ r, | V_i ∖ V(P') | ≥ 2 |E(G - Q')|.
	Again by the induction hypothesis, there exists an extension P' of P” with end-type (i_1 i_2) σ' π = σπ such that |V(P')| = |V(P”)| + 2k = |V(P)| + 2k(r-1) and,
	for all 1 ≤ i ≤ k, 
	
    | V_i ∩ ( V(P') ∖ V(P”) )| = 
    	
    	1    if i = i_1,
    
    	2	   otherwise.
 and V(P') ∖ (V(P”∪ K)) = { w_i_1 i_2}, so P' satisfies properties (i), (ii) and (iv). Furthermore, set W_G - Q = W_G - ⋃_j = 1^r-1 W_i_j i_j+1. Then W_G - Q is a (G - Q)-gadget for K avoiding V(P'), so P' satisfies property (iii) as well.


In the next lemma, we show how to extend a path with end-type id to one with an arbitrary end-type.
We will need the following definitions.
Consider an arbitrary σ∈ S_k ∖{id}.
Write σ in its cyclic decomposition 

    σ =  (i_1,1 i_1,2… i_1, r_1 )  (i_2,1 i_2,2… i_2, r_2)
    …
    ( i_t,1 i_t,2… i_t, r_t )   ,

where σ is a product of t = t(σ) disjoint cyclic permutations of respective lengths r_1, …, r_t so that r_j ≥ 2 and i_j,r_j = min{ i_j, r' : 1 ≤ r' ≤ r_j } for all 1 ≤ j ≤ t; and i_1,r_1 < i_2,r_2 < … < i_t,r_t.
Define m(σ) = i_t,r_t. On the other hand, if σ = id, then define t(σ) = 0 and m(σ) = 1.
Define G_σ to be the 2-graph on [k] consisting precisely of the (vertex-disjoint) paths Q_j = i_j,1 i_j,2… i_j,r_j for all 1 ≤ j ≤ t(σ).
So G_id is an empty 2-graph.
Note that for all σ,

    2| E(G_σ)| + t(σ) = 2 ∑_j=1^t(σ) r_j - t(σ) ≤ 2k-1.

For 1 ≤ i ≤ k and σ∈ S_k ∖{id}, set X_i, σ = 1 if i ∈{ i_t', 1, …, i_t', r_t' - 1} for some 1 ≤ t' ≤ t, and X_i, σ = 0 otherwise.
Also, for 1 ≤ i ≤ k, set Y_i, σ = 1 if i ∈{σ(j) : 1 ≤ j < m(σ) } and Y_i, σ = 0 otherwise. If σ = id, then define X_i, σ = Y_i, σ = 0 for all 1 ≤ i ≤ k.

 
	Let k ≥ 3. Let  be a k-graph containing a complete (k,k)-graph K with vertex partition V_1, …, V_k and a tight path P with end-type id.
	Let σ∈ S_k and let G be a 2-graph on [k] containing G_σ.
	Suppose that K has a G-gadget W_G avoiding V(P), and |V_i ∖ V(P)| ≥ 2 | E(G) | + 2.
	Then there exists an extension P' of P with end-type στ^m(σ) - 1 such that
	
		
  * |V(P')| = |V(P)|+ 2 k |E(G_σ)| + m(σ) - 1,
		
  * for all 1 ≤ i ≤ k, |V_i ∩ ( V(P') ∖ V(P) )| = 2|E(G_σ)| - X_i, σ + Y_i, σ,
		
  * K has a (G - G_σ)-gadget avoiding V(P') and
		
  * V(P') ∖ V(P ∪ K) = { w_ij : ij ∈ E(G_σ) }.
	



	Let
	
    σ =  (i_1,1 i_1,2… i_1, r_1 )  (i_2,1 i_2,2… i_2, r_2)
    	…
    	( i_t,1 i_t,2… i_t, r_t )

	as defined above. We proceed by induction on t = t(σ). If t = 0, then σ = id and m(σ) = 1, so the lemma holds by setting P' = P. Now suppose that t ≥ 1 and the lemma is true for all σ' ∈ S_k with t(σ') <t. Let 
	
    σ_1 = (i_1,1 i_1,2… i_1, r_1 ) (i_2,1 i_2,2… i_2, r_2) … ( i_t-1,1 i_t-1,2… i_t-1, r_t-1 )

	and σ_2 = ( i_t,1 i_t,2… i_t, r_t ),  so σ_1 σ_2 = σ_2 σ_1 = σ. 
	For 1 ≤ i ≤ 2, let G_i = G_σ_i and m_i = m(σ_i).
	Note that G_σ = G_1 ∪ G_2.
	Let G' = G - G_1.
	Since t(σ_1)= t-1, by the induction hypothesis, there exists a path P_1 that extends P with end-type σ_1 τ^ m_1- 1 such that
	
		
  * |V(P_1)| = |V(P)| + 2 k |E(G_1)|   + m_1 - 1,
		
  *  for all 1 ≤ i ≤ k, |V_i ∩ ( V(P_1) ∖ V (P) )| = 2 |E(G_1)| - X_i, σ_1 + Y_i, σ_1,
		
  * K has a G'-gadget W_G' avoiding V(P_1) and
		
  * V(P_1) ∖ V(P ∪ K) = { w_ij : ij ∈ E(G_1) }.
	
	Note that for all 1 ≤ i ≤ k,
	
    | V_i ∖( V(P_1) ∪ W_G') | ≥ 2 |E(G)| + 2  - (2 |E(G_1)| + 1 ) - 2 |E(G')| =1.

	We extend P_1 using m_2 - m_1 >0 simple extensions, avoiding the set V(P_1) ∪ W_G' in each step, to obtain an extension P_2 of P_1 with end-type σ_1 τ^m_1- 1τ^m_2 - m_1 = σ_1 τ^m_2 - 1 such that  
	
    |V(P_2)|  = |V(P_1)| + m_2 - m_1 = |V(P)| + 2 k |E(G_1)| + m_2 - 1

	and W_G' is a G'-gadget for K that avoids V(P_2).
	As P_1 has end-type σ_1 τ^m_1 - 1, V(P_2) ∖ V(P_1) contains precisely one vertex in V_i for all i ∈{σ_1 τ^m_1 - 1(j) : 1 ≤ j ≤ m_2 - m_1 } = {σ_1 ( m_1 ), …, σ_1(m_2 - 1)  }.
	Since σ_1(i) = σ(i) for all m_1 ≤ i < m_2 and m_2 = i_t, r_t, together with <ref> we deduce that 
    |V_i ∩ ( V(P_2) ∖ V (P) )| = 2 |E(G_1)| - X_i, σ_1 + Y_i, σ.
		
	
	Note that σ_1 τ^m_2 - 1(1) = σ_1 ( m_2 ) = σ_1 ( i_t, r_t ) = i_t, r_t. 
	Since G' contains G_2, by Lemma <ref> there exists an extension P' of P_2 with |V(P')| = |V(P_2)| + 2k|E(G_2)| and P' has end-type σ_2 σ_1  τ^m_2 - 1 = στ^m(σ) - 1, as m_2 = m(σ).
	Moreover, as G' - G_2 = G - G_σ, K has a (G - G_σ)-gadget avoiding V(P'), implying (iii).
	Similarly, (iv) holds.
	Note that 
	
    |V(P')| = |V(P_2)| + 2k|E(G_2)| = |V(P)| + 2k |E(G_σ)| + m(σ) - 1

	implying (i). Finally, for  all 1 ≤ i ≤ k, we have 
    |V_i ∩ (V(P') ∖ V(P_2) )| = 
    	2 |E(G_2)| - 1    if i ∈{i_t,1, …, i_t, r_t - 1},
    
    	2 |E(G_2)|	   otherwise.

	So |V_i ∩ (V(P') ∖ V(P_2))| = 2|E(G_2)| - X_i, σ_2.
	Note that X_i, σ = X_i, σ_1 + X_i, σ_2 because σ_1 and σ_2 are disjoint.	
	Thus, together with (<ref>), (ii) holds.
 

Now we want to use the previous lemmas to find tight cycles of a given length.

Let P be a tight path with start-type σ and end-type π. If π = σ, then there exists a tight cycle C containing P with V(C) = V(P). Similarly if π = στ^-r, then (by using r simple extensions) there exists a tight cycle C on |V(P)| + r vertices containing P.
In general, in order to extend P into a tight cycle we use Lemma <ref> to first extend P to a path P' with end-type στ^- r for some suitable r, using the edges of K and a suitable G-gadget.
The next lemma formalises the aforementioned construction of the tight cycle C containing P and gives us precise bounds on the sizes of V_i ∩ (V(C) ∖ V(P)) in the case where σ = π, which will be useful during Section <ref>.

 
	Let k ≥ 3. Let σ, π∈ S_k and 0 ≤ r < k.
	Then there exists a 2-graph G:= G(σ, π,r) on [k] consisting of a vertex-disjoint union of paths such that the following holds for all s ≥ k(2k-1) with s ≡ r  k:
	let  be a k-graph containing a complete (k,k)-graph K with vertex partition V_1, …, V_k, and let P be a tight path with start-type σ and end-type π.
	Suppose W_G is a G-gadget for K avoiding V(P) and | V_i ∖ V(P) | ≥⌊ s /k ⌋ + 1.
	Then there exists a tight cycle C on |V(P)| + s vertices containing P, such that 
    V(C) ∖ (V(P ∪ K)) = { w_ij : ij ∈ E(G) }.

	Moreover, if σ = π, then for all 1 ≤ i,j ≤ k, 
    | | V_i ∩ ( V(C) ∖ V(P)) | - | V_j ∩ ( V(C) ∖ V(P)) | | ≤ 1.




	Without loss of generality, we may assume that π = id.
	Define σ' = στ^-r∈ S_k.
	Let G = G_σ'.
	Note that |E(G)| ≤ k-1, t(σ')≤ k/2 and 2|E(G)| + t(σ') ≤ 2k - 1 by (<ref>).
	Let ,K,P be as defined in the lemma.
	By Lemma <ref>, there exists an extension P' of P with end-type σ' τ^m(σ') - 1 such that 
	|V(P')| = |V(P)|+ 2 k |E(G)| + m(σ') - 1, for all 1 ≤ i ≤ k,
	
    |V_i ∩ ( V(P') ∖ V (P) )| = 2 |E(G)| - X_i, σ' + Y_i, σ'
 and V(P') ∖ (V(P ∪ K)) = { w_ij : ij ∈ E(G) }.
	We use k - m(σ') + 1 simple extensions to get an extension P” of P' of order
	
    |V(P”)| = |V(P')| + (k - m(σ') + 1)  = |V(P)| + 2 k |E(G)|+k.

	Note that V(P”) ∖ V(P') uses precisely one vertex in each of the clusters V_i for all i ∈{σ' τ^m(σ') - 1(j) : 1 ≤ j ≤ k - m(σ') + 1  } = {σ'(j) : m(σ') ≤ j ≤ k } = { j : Y_j, σ' = 0 }. It follows that for all 1 ≤ i ≤ k,
	
    |V_i ∩ ( V(P”) ∖ V (P) )| = 2 |E(G)| + 1 - X_i, σ'.
 Note that P” has end-type σ ' τ^m(σ') - 1τ^k - m(σ') + 1 = σ' = στ^-r.
	For all 1 ≤ i ≤ k and 0 ≤ r < k, set Z_i, σ, r = 1 if i ∈{σ(j) : k-r+1 ≤ j ≤ k }, and set Z_i, σ, r = 0 otherwise. We use r more simple extensions to get an extension P”' of P with end-type στ^-rτ^r = σ of order
	
    |V(P”')| = |V(P”)| + r  = |V(P)| + 2 k |E(G)|+k + r
 such that, for all 1 ≤ i ≤ k,
	
    |V_i ∩ ( V(P”') ∖ V (P) )| = 2 |E(G)| + 1 + Z_i, σ, r - X_i, σ'.

	
	Since |E(G)| ≤ k-1 and s ≡ r  k, it follows that |V(P”')| ≤  |V(P)| + s. Also, |V(P”') ∖ V(P)| ≡ s k.  For all 1 ≤ i ≤ k,
	
    |V_i ∖ V(P”') | 
    	   ≥ |V_i ∖ V(P) | - 2 |E(G)| - 1 + X_i, σ' - Z_i, σ, r
       ≥⌊ s / k ⌋ - 2 |E(G)| - 1 = 1/k( k ⌊ s / k ⌋ - 2 k |E(G)| - k ) 
        = 1/k( s - r - 2 k |E(G)| - k ) = 1/k(  s - (|V(P”')| - |V(P)|) ).

	Since P”' has start-type σ and end-type σ, then we can easily extend P”' (using simple extensions) into a tight cycle C on |V(P)| + s vertices.
	Note that V(C) ∖ (V(P ∪ K)) = { w_ij : ij ∈ E(G) }, as desired.
	
	Moreover, for all 1 ≤ i,j ≤ k,
	
    | | V_i ∩ ( V(C) ∖ V(P)) | - | V_j ∩ ( V(C) ∖ V(P)) | | 
        = | | V_i ∩ ( V(P”') ∖ V(P)) | - | V_j ∩ ( V(P”') ∖ V(P)) | | 
        = | ( Z_i, σ, r - X_i, σ' ) - ( Z_j, σ, r - X_j, σ' ) |.
	
	Suppose now that σ = π = id. We will show that -1 ≤ Z_i, σ, r - X_i, σ'≤ 0 for all 1 ≤ i ≤ k, implying that for all 1 ≤ i, j ≤ k, | | V_i ∩ ( V(C) ∖ V(P)) | - | V_j ∩ ( V(C) ∖ V(P)) | | ≤ 1.
	It suffices to show that if Z_i, σ, r = 1, then X_i, σ' = 1.
	If r = 0 then it is obvious, so suppose that 1 ≤ r < k.
	Let 1 ≤ i ≤ k such that Z_i, σ, r = 1.
	Since σ = π = id, then σ' = τ^-r.
	So if Z_i, σ, r = 1, then k - r + 1 ≤ i ≤ k.
	To show that X_i, τ^-r = 1, we need to show that i is not the minimal element in the cycle that it belongs in the cyclic decomposition of τ^-r, that is, there exists m < i such that i is in the orbit of m under τ^-r.
	Let d = (r, k).
	Choose 1 ≤ m ≤ d such that m ≡ i  d.
	The order of τ^-r is exactly k/d and the orbit of m has exactly k/d elements.
	There are exactly k/d elements i' satisfying 1 ≤ i' ≤ k and i' ≡ m  d, and all elements i' in the orbit of m also satisfy i' ≡ m  d, so it follows that i is in the orbit of m under τ^-r.
	Finally, m ≤ d ≤ k - r < i.
	This proves that X_i, τ^-r = 1, as desired.




 §.§ Finding G-gadgets in k-graphs with large codegree


We now turn our attention to the existence of G-gadgets.
We prove that all large complete (k,k)-graphs contained in a k-graph  with δ_k-1(H) large have a G-gadget, for an arbitrary 2-graph G on [k].

 
	Let 0 < 1/n, 1/t_0 ≪γ, 1/k.
	Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + γ)n containing a complete (k,k)-graph K with vertex partition V_1, …, V_k.
	Let S ⊆ V() be a set of vertices such that |V(K) ∪ S| ≤γ n /2 and |V_i ∖ S| ≥ t_0 for all 1 ≤ i ≤ k.
	Let G be a 2-graph on [k].
	Then there exists a G-gadget for K avoiding S.



	Choose 0 < 1/t ≪γ, 1/k and let t_0  t + k^2.
	Suppose that ij ∈ E(G) and |V_ℓ∖ S| ≥ t + 2 |E(G)| for all 1 ≤ℓ≤ k.
	Let U_ℓ⊆ V_ℓ∖ S with |U_ℓ| = t for all 1 ≤ℓ≤ k and let R = [k] ∖{i, j}.
	Let U = ⋃_1 ≤ℓ≤ k U_ℓ and 
    T = { A ∈Uk-1 : | A ∩ U_r| = 1  for all  r ∈ R  and  |A ∩ (U_i ∪ U_j)| = 1  }.

	Then T has size 2 t^k-1.
	By the codegree condition, all members in T have (1/2 + γ)n - |V(K) ∪ S| ≥ (1/2 + γ/2)n neighbours outside of V(K) ∪ S and by an averaging argument, there exists a vertex w ∉ V(K) ∪ S such that (w) satisfies | (w) ∩ T | ≥ (1 + γ) t^k-1.
	For all u ∈ U_i ∪ U_j, N_(w) ∩ T(u) is a family of (k-2)-sets of ⋃_r ∈ R U_r. We have that 
    ∑_(u_i, u_j) ∈ U_i × U_j |N_(w) ∩ T(u_i) ∩ N_(w) ∩ T(u_j)| 
                  ≥∑_(u_i, u_j) ∈ U_i × U_j( d_(w) ∩ T(u_i) + d_(w) ∩ T(u_j) - t^k-2) 
                   = t |(w) ∩ T| - t^k ≥ t^k(1 + γ) - t^k = γ t^k,
 and by an averaging argument, there exists a pair (x^∗_i, x^∗_j) ∈ U_i × U_j such that |N_(w) ∩ T(x^∗_i) ∩ N_(w) ∩ T(x^∗_j)| ≥γ t^k-2.
	
	By the choice of t and by Theorem <ref>, we have that N_(w) ∩ T(x^∗_i) ∩ N_(w) ∩ T(x^∗_j) contains a copy K' of K^k-2_k-2(2). Define W_ij = V(K') ∪{ w, x_i^∗, x_j^∗} and note that |W_ij| = 2(k-2) + 3 = 2k - 1.
	
	We now check that <ref> holds for W_ij.
	Recall that, informally, this means that given any k-1 ordered clusters that miss V_i, there exists a tight path with vertex set W_ij, which starts with the same ordered k-1 clusters and ends with the same ordered k-1 clusters but with V_j replaced by V_i. 
	For all r ∈ R, let U_r ∩ V(K') = { x_r, x'_r}.
	Consider an arbitrary σ∈ S_k with σ(1) = i and σ(j') = j.
	By construction, we have that 
    x_σ(2) x_σ(3)… x_σ(j' - 1) x^∗_j x_σ(j' + 1) x_σ(j' + 2)… x_σ(k) w x'_σ(2) x'_σ(3)… x'_σ(j' - 1) x^∗_i x'_σ(j'+1) x'_σ(j'+2)… x'_σ(k)
 is a spanning tight path in [W_ij], of start-type στ and end-type (ij)σ.
	Clearly W_ij is an ij-gadget avoiding S.
	
	Set S' = S ∪ W_ij and G' = G - ij.
	Repeating this construction for all edges in E(G - ij) and using that t_0 = t + k^2, it is possible to conclude that K has a G-gadget avoiding S.




 §.§ Auxiliary k-graphs F_s
 

Given a tight cycle C_s^k, we would like to find a k-graph F_s such that C_s^k ⊆ F_s and F_s is obtained from a complete (k,k)-graph by adding “few” extra vertices.
This will be useful in Section <ref>.

Let K be a (k,k)-graph with vertex partition V_1, …, V_k.
Consider a 2-graph G on [k] with E(G) = { j_i j'_i : 1 ≤ i ≤ℓ} and let y_1, …, y_ℓ be a set of ℓ vertices disjoint from V(K).
Let W_G := { y_1, …, y_ℓ}.
We define the G-augmentation of K to be the k-graph F = F(K,G) such that 
    V(F)     = V(K) ∪ W_G and 
    
    E(F)     = E(K) ∪⋃_1 ≤ i ≤ℓ ( E(H(y_i, j_i)) ∪ E(H(y_i, j'_i)) ),
 where H(v,j) is a complete (k,k)-graph with partition { v }, V_1, V_2, …, V_j-1, V_j+1, …, V_k.

The easy (but crucial) observation is that if |V_i| ≥ 2 ℓ for all 1 ≤ i ≤ k,
then the G-augmentation of K contains a G-gadget for K avoiding ∅.

Using that, we can prove the following.

 
	Let k ≥ 3, s ≥ 2k^2 and s ≢0  k.
	Then there exists a 2-graph G_s on [k] that is a disjoint union of paths, and a_s,1, …, a_s,k, ℓ∈ℕ	such that
	| a_s,i - a_s,j  | ≤ 1 for all i, j ∈ [k],
	ℓ = |E(G_s)| ≤ k - 1,
	and if K = K^k(a_s,1, …, a_s,k), then F_s, the G_s-augmentation of K, contains a spanning C_s^k and |V(F_s) ∖ V(K)| = ℓ.



	Let r ∈{1, …, k-1 } be such that s ≡ r  k.
	Let G_s be the 2-graph obtained from Lemma <ref> (with parameters σ = π = id and r).
	Note G_s is a disjoint union of paths and thus ℓ = E(G_s) ≤ k-1.
	
	Suppose that V_1, …, V_k are disjoint sets of size ⌊ s/k ⌋ + 1 and let K' be the complete (k,k)-graph with partition { V_1, …, V_k }.	
	For all i ∈ [k] let v_i ∈ V_i and consider the tight path P = v_1 … v_k.
	Note that P has both start-type and end-type id.
	Let F' be the G_s-augmentation of K'.
	It is easily checked that |V_i ∖ V(P)| ≥ 2(k-1) ≥ 2ℓ and therefore there is a G_s-gadget for K' in F' avoiding V(P).
	By the choice of G_s, F' contains a tight cycle C on s vertices containing P such that V(C) ∖ V(K) = V(F') ∖ V(K') = W_G_s and, over the range i ∈ [k], the values |V(C) ∩ V_i| differ at most by 1.
	It is easily checked that letting a_s,i := |V(C) ∩ V_i| we obtain the desired properties.







§ COVERING THRESHOLDS FOR TIGHT CYCLES
 

In this section, we prove the upper bounds for the covering codegree threshold for tight cycles, proving Proposition <ref> and Theorem <ref>.
We first prove Proposition <ref>, which immediately implies Proposition <ref> since K^k(s) contains a C^k_s'-covering for all s' ≡ 0  k with s' ≤ sk.
We will use the following classic result of Kővári, Sós and Turán <cit.>.

 
	Let z(m,n; s,t) denote the maximum possible number of edges in a bipartite 2-graph G with parts U and V for which |U| = m and |V| = n, which does not contain a K_s,t subgraph with s vertices in U and t vertices in V. Then 
    z(m,n; s,t) < (s-1)^1/t (n - t + 1) m^1 - 1/t + (t-1)m.



 
	For all k ≥ 3 and s ≥ 1, let n, c ≥ 2 such that 1/n, 1/c ≪ 1/k, 1/s.
	Then c(n, K^k(s)) ≤ c n^1 - 1/s^k-1.



	Let  be a k-graph on n vertices with δ_k-1() ≥  c n^1 - 1/s^k-1.
	Fix a vertex x ∈ V() and consider the link (k-1)-graph (x) of x.
	Let U_1 := E((x)).
	Note that
	
    | U_1 | ≥n-1k-2δ_k-1()/k - 1≥ c^1/2 n^k - 1 - 1/s^k-1.

	
	Let U_2 := V() ∖{ x}.
	Consider the bipartite 2-graph B with parts U_1 and U_2, where e ∈ U_1 is joined to u ∈ U_2 if and only if e ∪{u}∈ E().
	By the codegree condition of , all (k-1)-sets e ∈ U_1 have degree at least δ_k-1() - 1 in B.
	Hence 
    |E(B)| ≥ | U_1|(δ_k-1() - 1) ≥ | U_1| ( c n^1 - 1/s^k-1 - 1 ).

	
	We claim there is a K_n^k-1-1/s^k-2,s-1 as a subgraph in B, with n^k-1-1/s^k-2 vertices in U_1 and s-1 vertices in U_2.
	Suppose not.
	Then, by Theorem <ref>, 
    |E(B)|
    	   ≤ z(| U_1|, n-1; n^k - 1 - 1/s^k-2, s-1) 
    
    	    < (n^k - 1 - 1/s^k-2)^1/s-1 n | U_1|^1 - 1/s-1 + (s-1) | U_1| 
        = | U_1| ( n ( n^k - 1 - 1/s^k-2/| U_1|)^1/s-1 + s-1 ) 
       (<ref>)≤ | U_1| ( c^-1/2(s-1) n^1 - 1/s^k-1 + s-1 ) < | U_1|  n^1 - 1/s^k-1.

	This contradicts (<ref>).
	
	Let K be a copy of K_n^k-1-1/s^k-2,s-1 in B.
	Let W := V(K) ∩ U_1 and X := { x_1, …, x_s-1} = V(K) ∩ U_2.
	Since |W| = n^k - 1 - 1/s^k-2 and 1/n ≪ 1/k, 1/s, by Theorem <ref>, W contains a copy K' of K^k-1(s).
	By construction, for all y ∈{ x }∪ X and all e ∈ E(K'), { y }∪ e ∈ E().
	Hence, [ { x }∪ X ∪ V(K')] contains a K^k(s) covering x, as desired.


We are ready to prove Theorem <ref>.


	Let t ∈ℕ be such that 1/n_0≪ 1/t ≪γ, 1/s. Let  be a k-graph on n ≥ n_0 vertices with δ_k-1() ≥ (1/2 + γ) n. Fix a vertex x and a copy K of K^k_k(t) containing x, which exists by Proposition <ref>. Let V_1, …, V_k be the vertex partition of K with x ∈ V_1. By the choice of t, |V_i| ≥max{2 k^2 + 2, ⌊ s / k ⌋ + 2 } for all 1 ≤ i ≤ k.
	
	Let x_1 = x and select arbitrarily vertices x_i ∈ V_i for 2 ≤ i ≤ k.
	Now P = x_1 … x_k is a tight path on k vertices with both start-type and end-type id.
	Let G be a complete 2-graph on [k].
	By Lemma <ref>, there exists a G-gadget for K avoiding V(P).
	Thus, by Lemma <ref>, there exists a tight cycle in V() on s vertices containing P, and in turn, x.




§ ABSORPTION
 

We need the following “absorbing lemma”, which is a special case of a lemma of Lo and Markström <cit.>.


 
	Let s ≥ k ≥ 3 and 0 < 1/n ≪η, 1/s and 0 < α≪μ≪η, 1/s.
	Suppose that  is a k-graph on n vertices and for all distinct vertices x, y ∈ V() there exist η n^s-1 sets S of size s-1 such that H[S ∪{ x }] and H[ S ∪{ y } ] contain a spanning C_s^k.
	Then there exists U ⊆ V() of size |U| ≤μ n with |U| ≡ 0  s such that there exists a perfect C_s^k-tiling in H[U ∪ W] for all W ⊆ V() ∖ U of size |W| ≤α n with |W| ≡ 0  s.


Thus to find an absorbing set U, it is enough to find many (s-1)-sets S as above for each pair x, y ∈ V().
First we show that we can find one such S.

 
	Let s ≥ 5k^2 with s ≢0  k.
	Let 1/n ≪γ, 1/s.
	Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + γ)n.
	Then for all pair of distinct vertices x, y ∈ V(), there exists S ⊆ V() ∖{ x, y } such that |S| = s-1 and both [S ∪{ x }] and [S ∪{ y}] contain a spanning C_s^k.



	Let 1/n ≪ 1/t ≪γ, 1/s.
	Consider the k-graph _xy with vertex set V(_xy) = (V(H) ∖{ x, y }) ∪{ z } (for some z ∉ V()) and edge set 
    E(_xy) = E(∖{ x, y }) ∪{{ z }∪ S : S ∈ N_(x) ∩ N_(y)  }.

	Note that |V(_xy)| = n - 1 and δ_k-1(_xy) ≥γ |V(_xy)|.
	By Proposition <ref>, H_xy contains a copy K of K^k_k(t) containing z.
	Let V_1, …, V_k be the vertex partition of K with z ∈ V_1.
	
	Select arbitrarily vertices v_i ∈ V_i for 2 ≤ i ≤ k.
	Let ' = _xy∖{ z, v_2, …, v_k } and K' = K ∖{ z, v_2, …, v_k }.
	Note that δ_k-1(') ≥ (1/2 + γ/2) |V(')| and K' ⊆'.
	By Lemma <ref> with H' and K' playing the roles of H and K respectively, there exists a K_k-gadget for K' in H'.
	Hence, there exists a K_k-gadget for K in _xy avoiding { z, v_2, …, v_k }.
	
	Now we construct a copy of C_s^k in _xy containing z.
	Note that P = z v_2 … v_k is a tight path on k vertices with start-type and end-type id.
	Since there exists a K_k-gadget for K avoiding V(P), by Lemma <ref> H_xy contains a copy C of C_s^k containing z.
	
	Finally, let S = V(C) ∖{z}⊆ V().
	By construction, |S| = s-1 and both H[S ∪{x}] and H[S ∪{y}] contain a spanning C_s^k in , as desired.


We now apply the standard supersaturation trick to find many sets S.

 
	Let k ≥ 3 and 0 < 1/m ≪γ, 1/k.
	Let  be a k-graph on n ≥ m vertices with δ_k-1() ≥ (1/2 + γ)n.
	Let x, y ∈ V() be distinct.
	Then the number of m-sets R ⊆ V() ∖{ x, y } such that δ_k-1( [ R ∪{ x, y } ] ) ≥ (1/2 + γ/2) (m+2) is at least n-2m / 2.


To prove Lemma <ref>, first we recall the following fact about concentration for hypergeometric random variables around their mean (see, e.g., <cit.>).

 
	Let a, γ > 0 with a + γ < 1.
	Suppose that S ⊆ [n] and |S| ≥ (a + γ) n.
	Then 
    | { M ∈[n]m : |M ∩ S| ≤ am }| ≤nm e^- γ^2 m/3(a + γ)≤nm e^- γ^2 m / 3.




	Let T be a (k-1)-set in V().
	Note that, since 1/n ≤ 1/m ≪γ,
	
    |N_H(T) ∖{x,y}|
    	   ≥( 1/2 + γ)n - 2
    	≥( 1/2 + 2/3γ)(n-2).

	We call an m-set R ⊆ V(H) ∖{x,y} bad for T if |N_H(T) ∩ R| ≤ (1/2 + 3γ/5)m.
	
	An application of Lemma <ref> (with 1/2 + 3γ/5, γ/15, n-2, N_H(T) ∖{x,y} playing the roles of a, γ, n and S, respectively) implies that the number of m-sets which are bad for T is at most 
    | { R ∈V(H) ∖{x,y}m : |N_H(T) ∩ R| ≤ (1/2 + 3γ/5)m }| ≤n-2m e^- γ^2 m / 675.

	Say an m-set R ⊆ V() ∖{ x, y } is good if δ_k-1( R ∪{x,y} ) > (1/2 + 3 γ / 5)m (and bad, otherwise).
	Note that for any good m-set R, 
    δ_k-1(H[R ∪{x,y}]) > (1/2 + 3 γ / 5)m ≥ (1/2 + γ/2)(m+2),

	thus it is enough to prove that there are at most n-2m/2 bad m-sets.
	Note that R is bad if and only if there exists a (k-1)-set T ⊆ R ∪{x,y} such that R is bad for T.
	Therefore, the number of bad sets is at most 
    m+2k-1n-2m e^-γ^2 m / 675≤1/2n-2m,
 where the inequality follows from the choice of m.



	Let k ≥ 3 and s ≥ 5k^2.
	Let 1/n ≪α≪μ≪γ, 1/s.
	Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + γ) n.
	Then, there exists U ⊆ V() of size |U| ≤μ n with |U| ≡ 0  s such that there exists a perfect C_s^k-tiling in H[U ∪ W] for all W ⊆ V() ∖ U of size |W| ≤α n with |W| ≡ 0  s.


 
	Let μ≪η≪ 1/m ≪γ, 1/s.
	Let x, y be distinct vertices in V().
	By Lemma <ref>, at least n-2m/2 of the m-sets R ⊆ V() ∖{ x, y } are such that δ_k-1( [ R ∪{ x, y } ] ) ≥ (1/2 + γ / 2) (m+2).
	By Lemma <ref>, each one of these subgraphs contains a set S ⊆ R of size s-1 such that [S ∪{ x }] and [S ∪{ y }] have spanning copies of C_s^k.
	Then the number of these sets S in H is at least 
    1/2n-2m/n - 2 - (s-1)m - (s-1) = n-2s-1/2 ms-1≥η n^s-1.

	Then the result follows from Lemma <ref>.




§ TILING THRESHOLDS FOR TIGHT CYCLES
 

Now we prove Theorem <ref> under the assumption that the following `almost perfect C_s^k-tiling lemma' holds.

 
	Let 1/n ≪α, γ, 1/s, k ≥ 3 and s ≥ 5k^2 such that s ≢0  k.
	Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + 1/(2s) + γ)n.
	Then  has a C_s^k-tiling covering at least (1 - α) n vertices.


Assuming Lemma <ref> is true, we use it to prove Theorem <ref>.


Choose 1/n ≪α≪μ≪γ, 1/k, 1/s.
By Lemma <ref>, there exists U ⊆ V() of size |U| ≤μ n with |U| ≡ 0  s such that there exists a perfect C_s^k-tiling in [U ∪ W] for all W ⊆ V() ∖ U of size |W| ≤α n with |W| ≡ 0  s.

Define ' = ∖ U.
Then δ_k-1(') ≥δ_k-1() - |U| ≥ (1/2 + 1/(2s) + γ/2)|V(')|.
An application of Lemma <ref> (with γ/2, |V(H')| playing the roles of γ, n, respectively, and noting the hierarchy of constants in both lemmas are consistent) implies that there exists a C_s^k-tiling ' in ' covering at least (1 - α)|V(')| vertices.
Let W be the set of uncovered vertices by ' in '.
Then |W| ≤α n and |W| ≡ 0  s.
By the absorbing property of U, there exists a perfect C_s^k-tiling ” in [U ∪ W].
Then ' ∪” is a perfect C_s^k-tiling in .


The rest of the paper will be devoted to the proof of Lemma <ref>.



§ HYPERGRAPH REGULARITY AND REGULAR SLICE LEMMA
 

To prove Lemma <ref> we will use the hypergraph regularity lemma, which requires the following definitions. 



 §.§ Regular complexes

	Let  be a partition of V into vertex classes V_1, …, V_s. A subset S ⊆ V is -partite if |S ∩ V_i| ≤ 1 for all 1 ≤ i ≤ s.
	A hypergraph is -partite if all of its edges are -partite, and it is s-partite if it is -partite for some partition  with || = s.

	A hypergraph  is a complex if whenever e∈ E() and e' is a non-empty subset of e we have that e'∈ E().
	All the complexes considered in this paper have the property that all vertices are contained in an edge.
	For a positive integer k, a complex  is a k-complex if all the edges of  consist of at most k vertices.
	The edges of size i are called i-edges of .
	Given a k-complex , for all 1 ≤ i ≤ k we denote by _i the underlying i-graph of : the vertices of _i are those of  and the edges of _i are the i-edges of .
	Given s≥ k, a (k,s)-complex  is an s-partite k-complex.

	Let  be a -partite k-complex.
	For i ≤ k and X ∈i, we write _X for the subgraph of _i induced by ⋃ X. 
	Note that _X is an (i,i)-graph.
	In a similar manner we write _X^< for the hypergraph on the vertex set ⋃ X, whose edge set is ⋃_X' ⊊ X_X'.
	Note that if  is a k-complex and X is a k-set, then _X^< is a (k-1, k)-complex.

	Given i≥ 2, consider an (i,i)-graph _i and an (i-1,i)-graph _i-1 on the same vertex set, which are i-partite with respect to the same partition .
	We write _i(_i-1) for the family of all -partite i-sets that form a copy of the complete (i-1)-graph K_i^i - 1 in _i-1.
	We define the density of _i with respect to _i-1 to be
	
    d(_i|_i-1)=|_i(_i-1)∩ E(_i)|/|_i(_i-1)|  if   |_i(_i-1)|>0,

	and d(_i|_i-1)=0 otherwise.
	More generally, if Q=(Q_1, …, Q_r) is a collection of r subhypergraphs of _i-1, we define _i( Q):=⋃_j=1^r _i(Q_j) and
	
    d(_i| Q)=|_i( Q)∩ E(_i)|/|_i( Q)|  if   |_i( Q)|>0,

	and d(_i| Q)=0 otherwise.

	We say that _i is (d_i,,r)-regular with respect to _i-1 if for all r-tuples Q with |_i( Q)|> |_i(_i-1)| we have d(_i| Q) = d_i ±.
	Instead of (d_i, , 1)-regularity we simply refer to (d_i, )-regularity; we also say simply that _i is (, r)-regular with respect to _i-1 to mean that there exists some d_i for which _i is (d_i, , r)-regular with respect to _i-1.
	Given an i-graph G whose vertex set contains that of _i-1, we say that G is (d_i, , r)-regular with respect to _i-1 if the i-partite subgraph of G induced by the vertex classes of _i-1 is (d_i, , r)-regular with respect to _i-1.
	
	Given 3 ≤ k ≤ s and a (k,s)-complex  with vertex partition , we say that  is (d_k, d_k-1, …, d_2,_k,,r)-regular if the following conditions hold:
	
		
  * For all 2 ≤ i ≤ k-1 and A ∈i, _A is (d_i, )-regular with respect to (_A^<)_i-1, and 
		
  * for all A ∈k, the induced subgraph _A is (d_k, _k, r)-regular with respect to (_A^<)_i-1.
	 Sometimes we denote (d_k, …, d_2) by  and write (, _k, , r)-regular to mean (d_k, …, d_2, _k, , r)-regular.

We will need the following “regular restriction lemma” which states that the restriction of regular complexes to a sufficiently large set of vertices in each vertex class is still regular, with somewhat degraded regularity properties.

 
	Let k, m ∈ℕ and β, , _k, d_2, …, d_k be such that 
    1/m≪≪_k, d_2, …, d_k-1    and    _k ≪β, 1/k.

	Let r, s ∈ℕ and d_k > 0.
	Set = (d_k, …, d_2).
	Let G be a (, _k, , r)-regular (k,s)-complex with vertex classes V_1, …, V_s each of size m.
	Let V'_i ⊆ V_i with |V'_i| ≥β m for all 1 ≤ i ≤ s. Then the induced subcomplex G[V'_1 ∪…∪ V'_s] is (, √(_k), √(), r)-regular.




 §.§ Statement of the regular slice lemma


In this section we state the version of the regularity lemma (Theorem <ref>) due to Allen, Böttcher, Cooley and Mycroft <cit.>, which they call the regular slice lemma.
A similar lemma was previously applied by Haxell, Łuczak, Peng, Rödl, Ruciński and Skokan in the case of 3-graphs <cit.>.
This lemma says that all k-graphs G admit a regular slice , which is a regular multipartite (k-1)-complex whose vertex classes have equal size such that G is regular with respect to .

Let t_0, t_1 ∈ℕ and > 0. We say that a (k-1)-complex  is (t_0, t_1, )-equitable if it has the following two properties: 
	
  * There exists a partition  of V() into t parts of equal size, for some t_0 ≤ t ≤ t_1, such that  is -partite.
	We refer to  as the ground partition of , and to the parts of  as the clusters of .
	
  * There exists a density vector = (d_k-1, …, d_2) such that, for all 2 ≤ i ≤ k-1, we have d_i ≥ 1/t_1 and 1/d_i ∈ℕ, and the (k-1)-complex  is (, , , 1)-regular.

Let X ∈k.
We write _X for the (k-1, k)-graph (_X^<)_k-1.
A k-graph G on V() is (_k, r)-regular with respect to _X if there exists some d such that G is (d, _k, r)-regular with respect to _X.
We also write d^∗_, G(X) for the density of G with respect to _X, or simply d^∗(X) if  and G are clear from the context.


	Given , _k > 0, r, t_0, t_1 ∈ℕ, a k-graph G and a (k-1)-complex  on V(G), we call  a (t_0, t_1, , _k, r)-regular slice for G if  is (t_0, t_1, )-equitable and G is (_k, r)-regular with respect to all but at most _k tk of the k-sets of clusters of , where t is the number of clusters of .


Given a regular slice  for a k-graph G, we keep track of the relative densities d^∗(X) for k-sets X of clusters of , which is done via a weighted k-graph.


	Given a k-graph G and a (t_0, t_1, )-equitable (k-1)-complex  on V(G), we let R_(G) be the complete weighted k-graph whose vertices are the clusters of , and where each edge X is given weight d^∗(X). When  is clear from the context we write R(G) instead of R_(G).


The regular slice lemma (Theorem <ref>) guarantees the existence of a regular slice  with respect to which R(G) resembles G in various senses.
In particular, R(G) inherits the codegree condition of G in the following sense.

Let G be a k-graph on n vertices.
Given a set S ∈V(G)k - 1, recall that _G(S) is the number of edges of G which contain S.
The relative degree (S; G) of S with respect to G is defined to be 
    (S; G) = _G(S)/n - k +1.

Thus, (S; G) is the proportion of k-sets of vertices in G extending S which are in fact edges of G.
To extend this definition to weighted k-graphs G with weight function d^∗, we define 
    (S; G) = ∑_e ∈ E(G): S ⊆ e d^∗(e)/n - k +1.

Finally, for a collection 𝒮 of (k-1)-sets in V(G), the mean relative degree (𝒮; G) of 𝒮 in G is defined to be the mean of (S; G) over all sets S ∈𝒮.

We will need an additional property of regular slices.
Suppose G is a k-graph, 𝒮 is a (k-1)-graph on the same vertex set, and  is a regular slice for G on t clusters.
We say  is (η, 𝒮)-avoiding if for all but at most ηtk-1 of the (k-1)-sets Y of clusters of , it holds that |_Y ∩𝒮| ≤η | _Y|.

We can now state the version of the regular slice lemma that we will use.

 
Let k ∈ℕ with k ≥ 3.
For all t_0 ∈ℕ, _k > 0 and all functions r: ℕ→ℕ and : ℕ→ (0, 1], there exist t_1, n_1 ∈ℕ such that the following holds for all n ≥ n_1 which are divisible by t_1!.
Let G be a k-graph on n vertices,
and let 𝒮 be a (k-1)-graph on the same vertex set with |E(𝒮)| ≤θnk-1.
Then there exists a (t_0, t_1, (t_1), _k, r(t_1))-regular slice  for G such that, for all (k-1)-sets Y of clusters of , we have (Y; R(G)) = (_Y; G) ±_k,
and furthermore  is (3 √(θ), 𝒮)-avoiding.


We remark that the original statement of <cit.> 

did not include the “avoiding” property with respect to a fixed (k-1)-graph 𝒮.
This, however, can be obtained easily from their proof.
We sketch this in Appendix <ref>.



 §.§ The d-reduced k-graph and strong density
 

Once we have a regular slice  for a k-graph G, we would like to work within k-tuples of clusters with respect to which G is both regular and dense. To keep track of those tuples, we introduce the following definition.


	Let G be a k-graph and  be a (t_0, t_1, , _k, r)-regular slice for G.
	Then for d > 0 we define the d-reduced k-graph R_d(G) of G to be the k-graph whose vertices are the clusters of  and whose edges are all k-sets of clusters X of  such that G is (_k, r)-regular with respect to X and d^∗(X) ≥ d.
	Note that R_d(G) depends on the choice of  but this will always be clear from the context.


The next lemma states that for regular slices  as in Theorem <ref>, the codegree conditions are also preserved by R_d(G).

 
	Let k, r, t_0, t ∈ℕ and , _k > 0.
	Let G be a k-graph and let  be a (t_0, t_1, , _k, r)-regular slice for G.
	Then for all (k-1)-sets Y of clusters of , we have 
    (Y; R_d(G)) ≥(Y; R(G)) - d - ζ(Y),
 where ζ(Y) is defined to be the proportion of k-sets Z of clusters with Y ⊆ Z that are not (_k, r)-regular with respect to G.


For 0 ≤μ, θ≤ 1, we say that a k-graph  on n vertices is (μ, θ)-dense if there exists 𝒮⊆V()k - 1 of size at most θnk-1 such that, for all S ∈V()k - 1∖𝒮, we have _(S) ≥μ(n - k + 1). In particular, if  has δ_k-1() ≥μ n, then it is (μ, 0)-dense.

By using Lemma <ref>, we show that  R_d(G) `inherits' the property of being  (μ, θ)-dense.

 
	Let 1/n ≪ 1/t_1 ≤ 1/t_0 ≪ 1/k and μ, θ, d, , _k > 0.
	Suppose that G is a k-graph on n vertices, that G is (μ, θ)-dense and let 𝒮 be the (k-1)-graph on V(G) whose edges are precisely { S ∈V(G)k-1 : _G(S) < μ (n-k+1) }.
	Let  be a (t_0, t_1, , _k, r)-regular slice for G such that for all (k-1)-sets Y of clusters of , we have (Y; R(G)) = (_Y; G) ±_k, and furthermore  is (3 √(θ), 𝒮)-avoiding.
	Then R_d(G) is ((1 - √(θ))μ - d - _k - √(_k), 3√(θ) + 3√(_k) )-dense.



	Let  be the ground partition of  and t = |  |.
	Let m = n/t.
	Clearly |V| = m for all V ∈.


	Let _1 be the set of all Y ∈k - 1 such that |_Y ∩𝒮| ≥ 3 √(θ) |_Y|.
	Since  is (3 √(θ), 𝒮)-avoiding, |_1| ≤ 3 √(θ)tk-1.

	
	For all Y ∈k - 1, let ζ(Y) be defined as in Lemma <ref>. 
	Let _2 be the set of all Y ∈k - 1 with ζ(Y) > √(_k).
	Since G is (_k, r)-regular with respect to all but at most _k tk of the k-sets of clusters of , it follows that |_2| √(_k) (t - k + 1) / k ≤_k tk, namely, |_2| ≤√(_k)tk-1.
	
	Then it follows that |_1 ∪_2| ≤ 3 (√(θ) + √(_k)) tk-1.
	We will show that all Y ∈k - 1∖ (_1 ∪_2) will have large codegree in R_d(G), thus proving the lemma.
	
	Consider any Y ∈k - 1∖ (_1 ∪_2).
	Since Y ∉_2, ζ(Y) ≤√(_k).
	By Lemma <ref>, we have 
    (Y; R_d(G))
    	   ≥(Y; R(G)) - d - ζ(Y) 
       ≥(Y; R(G)) - d - √(_k)
       ≥(_Y; G) - _k - d - √(_k).

	So it suffices to show that (_Y; G) ≥ (1 - 3 √(θ)) μ.	
	Recall that (_Y; G) is the mean of (S; G) over all S ∈_Y.
	Since Y ∉_1, |_Y ∩𝒮| ≤√(θ) |_Y|.
	By definition, for all S ∈_Y ∖𝒮, _G(S) ≥μ(n - k + 1).
	Thus (_Y; G) ≥ (1 - √(θ)) μ, as required.


For 0 ≤μ, θ≤ 1, a k-graph  on n vertices is strongly (μ, θ)-dense if it is (μ, θ)-dense and, for all edges e ∈ E() and all (k-1)-sets X ⊆ e, _(X) ≥μ (n - k + 1).
We prove that all (μ, θ)-dense k-graphs contain a strongly (μ', θ')-dense subgraph, for some degraded constants μ', θ'.

 
	Let n ≥ 2k and 0 < μ, θ < 1.
	Suppose that  is a k-graph on n vertices that is (μ, θ)-dense.
	Then there exists a sub-k-graph ' on V() that is strongly (μ - 2^k θ^1/(2k - 2), θ + θ^1/(2k - 2))-dense.



	Let 𝒮_1 be the set of all S ∈V()k-1 such that _(S) < μ(n - k + 1).
	Thus, |𝒮_1| ≤θnk - 1.
	Let β = θ^1/(k-1).
	Now, for all j ∈{ k - 1, k - 2, …, 1} in turn we construct _j ⊆V()j in the following way.
	Initially, let _k - 1 = 𝒮_1.
	Given j > 1 and _j, we define _j-1⊆V()j - 1 to be the set of all X ∈V()j - 1 such that there exist at least β (n - j + 1) vertices w ∈ V() with X ∪{ w }∈_j.
	
	
		For all 1 ≤ j ≤ k-1, |_j| ≤β^jnj.
	
	
	
		We prove it by induction on k - j. When j = k-1 it is immediate.
		Now suppose 2 ≤ j ≤ k - 1 and that |_j| ≤β^jnj.
		By double counting the number of tuples (X, w) where X is a (j-1)-set in _j-1 and X ∪{ w }∈_j we have |_j-1| β (n - j + 1) ≤ j |_j|.
		By the induction hypothesis it follows that 
    |_j-1| ≤j/β(n - j + 1) |_j| ≤β^j-1nj - 1.

	
	
	For all 1 ≤ j ≤ k - 1, let F_j be the set of edges e ∈ E() such that there exists S ∈_j with S ⊆ e, and let F = ⋃_j = 1^k - 1 F_j.  Define ' =  - F. We will show that it satisfies the desired properties.
	
	For each j-set, there are at most n - jk - j k-edges containing it.
	Thus, for all 1 ≤ j ≤ k - 1, the claim above implies that
	
    |F_j| ≤ |_j| n - jk - j≤β^j njn - jk - j = β^j kjnk.

	Therefore
	
    | F | ≤∑_j=1^k - 1 |F_j| ≤nk∑_j=1^k - 1kjβ^j≤ 2^k βnk.

	Let 𝒮_2 be the set of all S ∈V()k - 1 contained in more than 2^k √(β) (n - k + 1) edges of F.
	It follows that |𝒮_2| ≤√(β)nk - 1.
	This implies that |𝒮_1 ∪𝒮_2| ≤ (θ + √(β)) nk - 1 = (θ + θ^1/(2k - 2)) nk - 1.
	Now consider an arbitrary S ∈V()k - 1∖ (𝒮_1 ∪𝒮_2). As S ∉𝒮_1, it follows that _(S) ≥μ(n - k + 1). As S ∉𝒮_2, it follows that 
    _'(S)
    	   ≥_(S) - 2^k √(β) (n - k + 1) ≥ (μ - 2^k θ^1/(2k - 2)) (n - k + 1).
 Therefore, ' is (μ - 2^k θ^1/(2k - 2), θ + θ^1/(2k - 2))-dense.
	
	Let e ∈ E(') and let X ∈ek-1.
	It is enough to prove that X ∉𝒮_1 ∪𝒮_2.
	As e ∉ F_k-1, it follows that X ∉_k-1 = 𝒮_1.
	So it is enough to prove that X ∉𝒮_2.
	Suppose the contrary, that X ∈𝒮_2.
	Then X is contained in more than 2^k √(β) (n - k + 1) edges e' ∈ E(F).
	Let W = N_F(X).
	For all w ∈ W, fix a set A_w ∈⋃_j=1^k-1_j such that A_w ⊆ X ∪{ w } and let T_w = X ∩ A_w.
	If A_w ⊆ X then A_w ⊆ e ∈ E('), a contradiction.
	Hence w ∈ A_w for all w ∈ W, and therefore |T_w| = |A_w| - 1 ≤ k-2 < |X| for all w ∈ W.
	We deduce T_w ≠ X for all w ∈ W.	
	By the pigeonhole principle, there exists T ⊊ X and W_T ⊆ W such that for all w ∈ W_T, T_w = T and |W_T| ≥ |W|/(2^k-1) ≥ 2 √(β) (n - k + 1) > √(β) n.
	
	Suppose |T| = t ≥ 1. Then for all w ∈ W_T, T ∪{ w } = A_w ∈_t + 1, so there are at least √(β) n ≥β (n - t) vertices w ∈ V() such that T ∪{ w }∈_t+1.
	Therefore, T ∈_t and T ⊆ X ⊆ e, which is a contradiction because e ∉ F_t.
	Hence, we may assume that T = ∅.
	Then for all w ∈ W_T, { w }∈_1.
	And so |_1| ≥ |W_T| > √(β) n, contradicting the claim.




 §.§ The embedding lemma


We will need a version of “embedding lemma” which gives sufficient conditions to find a copy of a (k,s)-graph  in a regular (k, s)-complex G.

Suppose that G is a (k,s)-graph with vertex classes V_1, …, V_s, which all have size m.
Suppose also that  is a (k,s)-graph with vertex classes X_1, …, X_s of size at most m.
We say that a copy of  in G is partition-respecting if for all 1 ≤ i ≤ s, the vertices corresponding to those in X_i lie within V_i.

Given a k-graph G and a (k-1)-graph J on the same vertex set, we say that G is supported on J if for all e ∈ E(G) and all f ∈ek - 1, f ∈ E(J).

We state the following lemma which can be easily deduced from a lemma stated by Cooley, Fountoulakis, Kühn and Osthus <cit.>.

 
	Let k, s, r, t, m_0 ∈ℕ and let d_2, …, d_k-1, d, , _k > 0 be such that 1/d_i ∈ℕ for all 2 ≤ i ≤ k-1, and 
    1/m_0≪1/r, ≪_k, d_2, …, d_k-1    and    _k ≪ d, 1/t, 1/s.

	Then the following holds for all m ≥ m_0.
	Let  be a (k,s)-graph on t vertices with vertex classes X_1, …, X_s.
	Let  be a (d_k-1, …, d_2, , , 1)-regular (k-1, s)-complex with vertex classes V_1, …, V_s all of size m.
	Let G be a k-graph on ⋃_1 ≤ i ≤ s V_i which is supported on _k-1 such that for all e ∈ E() intersecting the vertex classes { X_i_j : 1 ≤ j ≤ k }, the k-graph G is (d_e, _k, r)-regular with respect to the k-set of clusters { V_i_j : 1 ≤ j ≤ k }, for some d_e ≥ d depending on e.
	Then there exists a partition-respecting copy of  in G.


The differences between Lemma <ref> and <cit.> are discussed in Appendix <ref>.



§ ALMOST PERFECT C_S^K-TILINGS
 

The aim of this section is to prove Lemma <ref>, that is, finding an almost perfect C_s^k-tiling.
Throughout this section, we fix k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
Let G_s, W_G_s, a_s,1, …, a_s,k, ℓ, F_s be given by Proposition <ref>.
Recall that F_s contains a spanning C_s^k.
Therefore, an F_s-tiling in  implies the existence of a C_s^k-tiling in H of the same size.

Here we summarise some useful inequalities that will be used throughout the section.
Let M_s = max_i a_s,i and m_s = min_i a_s,i.
We have 
    ℓ + ∑_i=1^k a_s,i = s,    M_s ≤ m_s+1,   and   1 ≤ℓ≤ k - 1.

From this, we can easily deduce 
    m_s + 1 ≥ M_s ≥s - ℓ/k≥s - k + 1/k.









Define E_s = K^k(M_s), the complete (k,k)-graph with each part of size M_s.
Given an { F_s, E_s }-tiling  in , let _ and _ be the set of copies of F_s and E_s in , respectively.
Define 
    ϕ() = 1/n( n - s ( |_| + 3/5 |_| ) ).

Note that if _ = ∅, then  is an F_s-tiling covering all but ϕ()n vertices.
Let ϕ() be the minimum of ϕ() over all { F_s, E_s}-tilings  in .
Given n ≥ k and 0 ≤μ, θ < 1, let Φ(n, μ, θ) be the maximum of ϕ() over all (μ, θ)-dense k-graphs  on n vertices.
Note that ϕ(H) and Φ(n, μ, θ) depend on k and s but they will be clear from the context.

 
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let 1/n, θ≪α, γ, 1/k, 1/s.
	Then Φ(n, 1/2 + 1/(2s) + γ, θ) ≤α.


We now show that Lemma <ref> implies Lemma <ref>.


	Fix α, γ > 0. Note that |V(F_s)| = s and |V(E_s)| = k M_s.
	Let δ = 7/10.
	Using s ≥ 5k^2, (<ref>) and k ≥ 3, we deduce kM_s/s ≥ 1 - (k-1)/(5k^2) ≥ 43/45.
	Hence 
	
    3 s / 5 ≤  43 s δ/45 ≤δ k M_s.

	
	Define α_1 = α (1 - δ) and choose some θ≪α, γ, 1/k, 1/s.
	Since 1/n ≪α, γ, 1/k, 1/s as well, Lemma <ref> (with α_1 in place of α) implies that Φ(n, 1/2 + 1/(2s) + γ, θ) ≤α_1.
	
	Let  be a k-graph on n vertices with δ_k-1() ≥ (1/2 + 1/(2s) + γ)n.
	Then ϕ() ≤Φ(n, 1/2 + 1/(2s) + γ, 0) ≤Φ(n, 1/2 + 1/(2s) + γ, θ) ≤α_1.
	Let  be an { F_s, E_s }-tiling in  with ϕ() ≤α_1.
	Hence, 
	
    1 - α_1 ≤ 1 - ϕ() 
    	≤s/n( | _| + 3 /5  |_| ) 
    	(<ref>)≤1/n( s |_| + δ k M_s |_|  ).

	As  is a tiling, we have that s |_| + k M_s |_| ≤ n.
	Hence, 1 - α_1 ≤ (1 - δ) s | _ |/n + δ and so 
    s |_| ≥( 1 - α_1/1 - δ) n = (1 - α) n.

	Therefore H contains an _s-tiling _ covering all but at most α n vertices, implying the existence of a C_s^k-tiling of the same size.




 §.§ Weighted fractional tilings
 

Our strategy for proving Lemma <ref> is to apply the regular slice lemma (Theorem <ref>).  
In the reduced k-graph, we find a fractional {F^∗_s, E^∗_s }-tiling for some simpler k-graphs F^∗_s and E^∗_s.
By using the regularity methods, this fractional tiling can then be lifted to an actual tiling with copies of F_s, E_s in the original k-graph, which covers a similar proportion of vertices.


To define the k-graphs F^∗_s and E^∗_s, we use the notion of G-augmentation introduced in Subsection <ref>.
Let K be a k-edge with vertices { x_1, …, x_k }.
Let G_s be the 2-graph on [k] given by Corollary <ref>.
Let F^∗_s be the G_s-augmentation of K (with respect to the vertex partition V_i := {x_i} for all i ∈ [k]). 
Let V(F^∗_s) = { x_1, …, x_k }∪{ y_1, …, y_ℓ}, where ℓ = |E(G_s)|.
We refer to c(F^∗_s) = { x_1, …, x_k } as the set of core vertices of F^∗_s and p(F^∗_s) = { y_1, …, y_ℓ} as the set of pendant vertices of F^∗_s.
Define the function α: V(F^∗_s) →ℕ to be such that for u ∈ V(F^∗_s), 
    α(u) = 
    a_s,i   if  u = x_i, 
     1    if  u ∈ p(F^∗_s).
 Note that there is a natural k-graph homomorphism θ from F_s to F^∗_s such that for all u ∈ V(F^∗_s), |θ^-1(u)| = α(u).
Observe that (<ref>), s ≥ 5k^2 and k ≥ 3 imply that α(u) = 1 if and only if u is a pendant vertex.

Let ^∗_s() be the set of copies of F^∗_s in .
Given v ∈ V(H) and F^∗_s ∈^∗_s(), define 
    α_F^∗_s(v) = α(u)    if v corresponds to vertex u ∈ V(F^∗_s),
     0    otherwise.

Given v ∈ V() and e ∈ E(), define 
    α_e(v) = 
    M_s    if v ∈ e,
     0    otherwise.

We now define a weighted fractional { F^∗_s, E_s^∗}-tiling of  to be a function ω^∗ : ^∗_s() ∪ E() → [0,1] such that, for all vertices v ∈ V(),

    ω^∗(v) ∑_F^∗_s ∈^∗_s()ω^∗(F^∗_s) α_F^∗_s(v) + ∑_e ∈ E()ω^∗(e) α_e(v) ≤ 1.

Note that if (contrary to our assumptions) a_s,1 = … = a_s,k = 1,
then we have α_F^∗_s(v) = 1{ v ∈ V(F^∗_s) } and α_e(v) = 1{ v ∈ e } implying that ω^∗ is the standard fractional { F_s, E_s }-tiling.
Note that the definition depends on k and the functions α_F^∗_s and α_e, but those will always be clear from the context.

Define the minimum weight of ω^∗ to be 
    ω^∗_min = min_J ∈^∗_s() ∪ E() 
     v ∈ V() 
    ω^∗(J) α_J(v) ≠ 0 ω^∗(J) α_J(v).

Analogously to ϕ(), define 
    ϕ( ω^∗ ) = 1/n( n - s ( ∑_F^∗_s ∈^∗_s()ω^∗(F^∗_s) + 3/5∑_e ∈ E()ω^∗(e) ) ).

Given c > 0 and a k-graph , let ϕ^∗(, c) be the minimum of ϕ(ω^∗) over all weighted fractional { F^∗_s, E^∗_s }-tilings ω^∗ of  with ω^∗_min≥ c.
Note that ϕ^∗(H, c) also depends on k, s, α_F^∗_s and α_e, which will always be clear from the context.

Let  be an { F_s, E_s }-tiling. We say that a vertex v is saturated under  if it is covered by a copy of F_s and v corresponds to a vertex in W_G_s under that copy.
Let S() denote the set of all saturated vertices under .
Define U() as the set of all uncovered vertices under .

Analogously, given a weighted fractional { F^∗_s, E^∗_s }-tiling ω^∗, we say that a vertex v is saturated under ω^∗ if

    ∑_F^∗_s ∈_s^∗() 
    α_F^∗_s(v) = 1 ω^∗(F^∗_s) α_F^∗_s (v) = 1,

that is, ω^∗(v) = 1 and all its weight comes from copies of F^∗_s such that v corresponds to a pendant vertex.

Let S(ω^∗) be the set of all saturated vertices under ω^∗.
Also, define U(ω^∗) as the set of all vertices v ∈ V() such that ω^∗(v) = 0.

  
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let H be a k-graph on n vertices.
	Let ω^∗ be a weighted fractional { F^∗_s, E^∗_s }-tiling in H.
	Then the following holds: 
		
  *  s ∑_F^∗∈^∗_sω^∗ (F^∗) + k M_s  ∑_e ∈ E()ω^∗ (e) ≤ n. In particular, ∑_F^∗∈^∗_sω^∗ (F^∗) ≤ n/s and  ∑_e ∈ E()ω^∗ (e) ≤ n/ (k M_s),
		
  *  |S(ω^∗)| ≤ℓ n / s,
		
  *  if S' ⊆ S(ω^∗) with |S'| > n/s, then there exists F^∗∈^∗_s() with ω^∗(F^∗) > 0 such that |p(F^∗) ∩ S'| ≥ 2.
	



	For <ref>, note that
	
    n
    	   ≥∑_v ∈ V()∑_F^∗∈^∗_s(H)ω^∗(F^∗) α_F^∗(v) + ∑_v ∈ V()∑_e ∈ E(H)ω^∗(e) α_e(v) 
        = ∑_F^∗∈^∗_s(H)ω^∗(F^∗) ∑_v ∈ V()α_F^∗(v) + ∑_e ∈ E(H)ω^∗(e) ∑_v ∈ V()α_e(v)  
        = s ∑_F^∗∈^∗_s(H)ω^∗(F^∗) + k M_s ∑_e ∈ E(H)ω^∗(e).

	
	To prove <ref>, recall that all of the vertices v ∈ S(ω^∗) only receive weight from pendant vertices, and all copies of F ∈^∗_s() have precisely ℓ pendant vertices, and therefore 
    |S(ω^∗)| = ∑_v ∈ S(ω^∗)∑_F^∗∈^∗_s()ω^∗(F^∗) α_F^∗(v) ≤ℓ∑_F^∗∈^∗_s()ω^∗(F^∗) <ref>≤ℓ n / s.

	
	Finally, for <ref>, suppose the contrary, that, for all F^∗∈^∗_s() with ω^∗(F^∗) > 0, we have ∑_v ∈ S'α_F^∗(v) = |p(F^∗) ∩ S'| ≤ 1. Then 
    |S'|
    	    = ∑_v ∈ S'∑_F^∗∈^∗_s()ω^∗(F^∗) α_F^∗(v) = ∑_F^∗∈^∗_s()ω^∗(F^∗) ∑_v ∈ S'α_F^∗(v) 
       ≤∑_F^∗∈^∗_s()ω^∗(F^∗) ≤ n/s,
 a contradiction.


Note that F_s admits a natural perfect weighted fractional F^∗_s-tiling, defined as follows.
Let a = ∏_1 ≤ i ≤ k a_s,i.
Let F be a copy of F_s and suppose that V(F) = V_1 ∪…∪ V_k ∪ W, where V_1, …, V_k forms a complete (k,k)-graph with |V_i| = a_s,i for all 1 ≤ i ≤ k and |W| = ℓ.
Note that a ≤ M^k_s.
For all (v_1, …, v_k) ∈ V_1 ×…× V_k, the vertices { v_1, …, v_k }∪ W span a copy of F^∗_s, where we identify { v_1, …, v_k } with the core vertices of F^∗_s and W with the pendant vertices of F^∗_s.
Define ω^∗ by assigning to all such copies the weight 1 / a.
A similar method shows that E_s admits a perfect weighted fractional E^∗_s-tiling, by setting ω^∗(e) = M^-k_s for all e ∈ E_s.

We can naturally extend these constructions to find a weighted fractional { F^∗_s, E^∗_s }-tiling given an {F_s, E_s}-tiling, by repeating the above procedure over all copies of F_s and E_s.
The following proposition collects useful properties of the obtained fractional tiling, for future reference.
All of them straightforward to check by using the construction outlined above, so we omit its proof.

 
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let  be a k-graph and let  be an { F_s, E_s }-tiling in .
	Then there exists a weighted fractional { F^∗_s, E^∗_s }-tiling ω^∗ such that
	
		
  * ϕ() = ϕ(ω^∗), 
		
  * |_| = ∑_F^∗∈^∗_s()ω^∗(F^∗),
		
  * |_| = ∑_e ∈ E()ω^∗(e),
		
  * S(ω^∗) = S() and U(ω^∗) = U(), 
		
  * for all F^∗∈_s^∗(), ω^∗(F^∗) ∈{ 0, a^-1}, where a = ∏_1 ≤ i ≤ k a_s,i, 
		
  * for all e ∈ E(), ω^∗(e) ∈{ 0, M^-k_s }, moreover if e ∈ E(E_s) for some E_s ∈_, then ω^∗(e) = M^-k_s, 
		
  * ω^∗_min≥ M_s^-k, and 
		
  * ω^∗(v) ∈{0,1} for all v ∈ V().  

















The next lemma assures that if R is a reduced k-graph of , then ϕ(H) is roughly bounded above by ϕ^∗(R, c).

 
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let c ≥β > 0 and 
    1/n≪, 1/r ≪_k ≪ 1/t_1 ≤ 1/t_0 ≪β, c, 1/s, 1/k
 and 
    _k ≪ d, 1/k, 1/s.
 
	Let  be a k-graph on n vertices and  be a (t_0, t_1, , _k, r)-regular slice for , and R = R_d() be its d-reduced k-graph obtained from .
	Then ϕ() ≤ϕ^∗(R, c) + s β / c.



	Let ω^∗ be a weighted fractional { F^∗_s, E^∗_s }-tiling on R such that ϕ(ω^∗) = ϕ^∗(R, c) and ω^∗_min≥ c.
	Let t = |V(R)| and let m = n/t, so that each cluster in  has size m.
	Let n^∗_F be the number of F^∗_s ∈^∗_s(R) with ω^∗(F^∗_s) > 0 and n^∗_E be the number of E ∈ E(R) with ω^∗(E) > 0.
	Note that 
    n^∗_F + n^∗_E ≤ t/c.

	For all clusters U ∈ V(R), we subdivide U into disjoint sets { U_J }_J ∈^∗_s(R) ∪ E(R) of size |U_J| = ⌊ω^∗(J) α_J(U) m ⌋.
	
	In the next claim, we show that if ω^∗(J) > 0 for some J ∈^∗_s(R) ∪ E(R) then we can find a large F_s-tiling or a large E_s-tiling on ⋃_U ∈ V(J) U_J.
	
	
		For all J ∈_s^∗(R) ∪ E(R) with ω^∗(J) > 0, [ ⋃_U ∈ V(J) U_J ] contains
		
			
  * an F_s-tiling _J with |_J| ≥ m (ω^∗(J) - β ) if J ∈^∗_s(R); or
			
  * an E_s-tiling _J with |_J| ≥ m (ω^∗(J) - β ) if J ∈ E(R).
		
	
	
	
		We will only consider the case when J ∈^∗_s(R), as the case J ∈ E(R) is proved similarly.
		
		Suppose c(J) = { X_1, …, X_k } and p(J) = {Y_1, …, Y_ℓ}, so V(J) = c(J) ∪ p(J).
		We will first show that if X'_i ⊆ X_i for all 1 ≤ i ≤ k and Y'_j ⊆ Y_j for all 1 ≤ j ≤ℓ are such that |X'_i| = |Y'_j| ≥β m, then [ ⋃_1 ≤ i ≤ k X'_i ∪⋃_1 ≤ j ≤ℓ Y'_j ] contains a copy F of F_s such that |V(F) ∩ X'_i| = a_s,i for all 1 ≤ i ≤ k and |V(F) ∩ Y'_j| = 1 for all 1 ≤ j ≤ℓ.
		
		Indeed, take X'_i, Y'_j as above and construct the subcomplex ' obtained by restricting  along with  to the subsets X'_i, Y'_j and then deleting the edges in  not supported in k-tuples of clusters corresponding to edges in E(J).
		Then ' is a (k, k + ℓ)-complex.
		Since  is (t_0, t_1, )-equitable, there exists a density vector = (d_k-1, …, d_2) such that, for all 2 ≤ i ≤ k-1, we have d_i ≥ 1/t_1, 1/d_i ∈ℕ and  is (d_k-1, …, d_2, , , 1)-regular.
		As J ⊆ R, all edges e in E(J) ∩ E(R) induce k-tuples X_e of clusters in  with d^∗(X_e) = d_e ≥ d and  is (d_e, _k, r)-regular with respect to X_e.
		By Lemma <ref>, the restriction of X_e to the subsets { X'_1, …, X'_k, Y'_1, …, Y'_ℓ} is (d_e, √(_k),  √(), r)-regular.
		Hence, by Lemma <ref>, there exists a partition-respecting copy F of F_s in ', that is, F satisfies |V(F) ∩ X'_i| = a_s,i for all 1 ≤ i ≤ s and |V(F) ∩ Y'_j| = 1 for all 1 ≤ j ≤ℓ, as desired.
		
		Now consider the largest F_s-tiling _J in [ ⋃_U ∈ V(J) U_J ] such that all F ∈_J satisfy |V(F) ∩ X_i| = a_s,i for all 1 ≤ i ≤ k and |V(F) ∩ Y_j| = 1 for all 1 ≤ j ≤ℓ.
		Let V(_J) = ⋃_F ∈_J V(F).
		By the discussion above, we may assume that |U_J ∖ V(_J) | < β m for some U ∈ V(J).
		

		A simple calculation shows that |(Y_j)_J ∖ V(_J) | < β m for all 1 ≤ j ≤ℓ and |(X_i)_J ∖ V(_J) | < a_s,iβ m for all 1 ≤ i ≤ k.
		Therefore, _J covers at least sm(ω^∗(J) - β) vertices and it follows that |_J| ≥ m (ω^∗(J) - β).
	
	
	Now consider the { F_s, E_s }-tiling = _∪_ in , where _ = ⋃_J ∈^∗_s(R)_J and _ = ⋃_E ∈ E(R)_J as given by the claim (and we take _J = _J = ∅ whenever ω^∗(J) = 0).
	Therefore 
    |_| + 3/5 |_|
    	   ≥∑_ F^∗_s ∈^∗_s(R) 
    ω^∗(F^∗_s) > 0 m(ω^∗(F^∗_s) - β) + 3/5∑_ E ∈ E(R) 
    ω^∗(E) > 0 m(ω^∗(E) - β ) 
       ≥ m ( ∑_F^∗_s ∈^∗_s(R)ω^∗(F^∗_s) + 3/5∑_ E ∈ E(R)ω^∗(E) - β (n^∗_F + n^∗_E) ) 
       ≥ m ( ∑_F^∗_s ∈^∗_s(R)ω^∗(F^∗_s) + 3/5∑_ E ∈ E(R)ω^∗(E) - β t/c) 
        = m t ( 1 - ϕ(ω^∗)/s - β/c) = n/s(  1 - ϕ(ω^∗) - β s/c).

	Thus we have ϕ() ≤ϕ() ≤ϕ(ω^∗) + s β / c = ϕ^∗(R, c) + s β / c.




 §.§ Proof of Lemma <ref>
 

We begin with some lemmas before formally proving Lemma <ref>.

 
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let μ + γ/3 ≤ 2/3.
	Then Φ(n, μ, θ) ≤Φ((1 + γ)n, μ + γ/3, θ) + s γ.



	Let  be a k-graph on n vertices that is (μ, θ)-dense. Consider the k-graph ' on the vertices V() ∪ A obtained from  by adding a set of |A| = γ n vertices and adding all of the k-edges that have non-empty intersection with A. Since 
    μ + γ/1 + γ≥μ + γ / 3
 as μ + γ/3 ≤ 2/3, ' is (μ + γ/3, θ)-dense.
	
	Let ' be an { F_s, E_s }-tiling on ' satisfying ϕ(') = ϕ(').
	Consider the { F_s, E_s }-tiling  in  obtained from ' by removing all copies of F_s or E_s intersecting with A. It follows that
	
    1 - ϕ()
    	    = s/n( |_| + 3/5 |_|  )
    	≥s/n( |_'| + 3/5 |_'|  ) - s γ
       ≥s/(1 + γ) n( |_'| + 3/5 |_'|  ) - s γ = 1 - ϕ(') - s γ.

	Hence, ϕ() ≤ϕ() ≤ϕ(') + s γ≤Φ((1 + γ)n, μ + γ/3, θ) + s γ.


The next lemma shows that given an { F_s, E_s }-tiling  of a strongly (μ, θ)-dense k-graph  with ϕ(T) “large”, we can always find a better weighted fractional { F^∗_s, E^∗_s }-tiling in terms of ϕ^∗.

 
	Let k ≥ 3, s ≥ 5k^2 with s ≢0  k, and c = s^-2k. 

	For all γ > 0 and 0 ≤α≤ 1 there exists n_0 = n_0(k, s, γ, α) ∈ℕ and ν = ν(k, s, γ) > 0 and θ = θ(α, k) such that following holds for all n ≥ n_0.
	Let  be a k-graph on n vertices that is strongly (1/2 + 1/(2s) + γ, θ)-dense and ϕ() ≥α. Then ϕ^∗(, c) ≤ (1 - ν) ϕ().


We defer the proof of Lemma <ref> to the next subsection and now we use it to prove Lemma <ref>.


	Consider a fixed γ > 0.
	Suppose the result is false, that is, there exists α > 0 such that for all n ∈ℕ and θ^∗ > 0 there exists n' > n satisfying Φ(n', 1/2 + 1/(2s) + γ, θ^∗) > α.
	Let α_0 be the supremum of all such α.
	Apply Lemma <ref> (with parameters γ/2, α_0/2 playing the roles of γ, α) to obtain n_0 = n_0(k, s, γ/2, α_0/2), ν = ν(k, s, γ/2) and θ = θ(α_0/2, k).

	Let 
    0 < η≪ν, γ, α_0, 1/s.

	By the definition of α_0, there exists θ_1 > 0 and n_1 ∈ℕ such that for all n ≥ n_1, 
    Φ(n, 1/2 + 1/(2s) + γ, θ_1) ≤α_0 + η/2.

	Now we prepare the setup to use the regular slice lemma (Theorem <ref>).
	Let β, _k, , d, θ^∗, θ' > 0 and t_0, t_1, r, n_2 ∈ℕ be such that 
    1/n_2 ≪, 1/r ≪    _k, 1/t_1 ≪ 1/t_0 ≪β≪γ' ≪η, c=s^-k, 1/s, 1/k, 1/n_0, 1/n_1; 
       _k ≪ d ≪γ'; 
       _k ≪θ' ≪θ^∗≪γ', θ, θ_1
 and n_2 ≡ 0  t_1!.
	
	Let  be a (1/2 + 1/(2s) + γ, θ')-dense k-graph on n ≥ n_2 vertices with 
    ϕ() > α_0 - η,
 such  exists by the definition of α_0. By removing at most t_1! - 1 vertices we get a k-graph ' on at least n_2 vertices such that |V(')| is divisible by t_1! and ' is (1/2 + 1/(2s) + γ - γ', 2 θ')-dense.
	
	Let 𝒮 be the set of (k-1)-tuples T of vertices of V(H') such that _H'(T) < (1/2 + 1/(2s) + γ - γ')(|V(H')| - k + 1).
	Thus |𝒮| ≤ 2 θ' |V(H')|k-1.	
	By Theorem <ref>, there exists a (t_0, t_1, , _k, r)-regular slice  for ' such that for all (k-1)-sets Y of clusters of , we have (Y; R(')) = (_Y; ') ±_k, and furthermore,  is (3 √(2 θ'), 𝒮)-avoiding.
	
	Let R = R_d(') be the d-reduced k-graph obtained from ' and .
	Since θ', d, _k ≪γ', _k ≪θ' and  is (3 √(2 θ'), 𝒮)-avoiding, Lemma <ref> implies that R is (1/2 + 1/(2s) + γ - 2 γ', 5 √(θ'))-dense.
	By Lemma <ref>, there exists a subgraph R' ⊆ R on the same vertex set that is strongly (1/2 + 1/(2s) + γ - 3 γ', θ^∗)-dense as θ' ≪γ', 1/k, θ^∗.
	Since the vertices of R' are the clusters of , we have |V(R')| ≥ t_0 ≥ n_1.
	By the fact that θ^∗≤θ_1, Lemma <ref> (with 9 γ ' playing the role of γ) and (<ref>), we deduce that
	
    ϕ(R')
    	   ≤Φ( |V(R')|, 1/2 + 1/(2s) + γ - 3 γ', θ^∗ ) 
       ≤Φ( (1 + 9 γ') |V(R')|, 1/2 + 1/(2s) + γ, θ^∗ ) + 9 γ' s 
       ≤α_0 + η/2 + 9 γ' s ≤α_0 + η.

	
	We further claim that ϕ^∗(R', c) ≤α_0 - 2 η.
	Note that c = s^-k and α_0 ≥ 4 η.
	Therefore, if ϕ(R') < α_0 / 2, then the claim holds by Proposition <ref>.
	Thus we may assume that ϕ(R') ≥α_0/2.
	Note that |V(R')| ≥ t_0 ≥ n_0, γ - 3 γ' ≥γ / 2, and θ^∗≤θ.
	By the choice of n_0, ν, and θ (given by Lemma <ref>lemma:fractionalisbetter), 
	we have 
    ϕ^∗(R', c) ≤ (1 - ν) ϕ(R') ≤ (1 - ν) (α_0 + η) ≤α_0 - 2 η,
 where the last inequality holds since η≪ν, α_0.
	
	Finally, recall that β≪η, c, so an application of Lemma <ref> implies that 
    ϕ() ≤ϕ^∗(R, c) + s β / c ≤ϕ^∗(R', c) + s β / c ≤α_0 - η,
 contradicting (<ref>).




 §.§ Proof of Lemma <ref>


Before proceeding with the full details of the proof of Lemma <ref>, we first give a rough outline of the proof.
Let  be an { F_s, E_s }-tiling of  satisfying ϕ() = ϕ(H).
By Proposition <ref>, we obtain a weighted fractional { F^∗_s, E^∗_s }-tiling ω^∗_0 with ϕ(ω^∗_0) = ϕ(), U(ω^∗_0) = U() and (ω^∗_0)_min≥ M_s^-k.
Our aim is to sequentially define weighted fractional { F^∗_s, E^∗_s }-tilings ω^∗_1, ω^∗_2, …, ω^∗_t such that ϕ(ω^∗_j-1) - ϕ(ω^∗_j) ≥ν_1 / n for all j ∈ [t], where ν_1 is a fixed positive constant.
We will follow this procedure for t = Ω(n) steps, and we will show that ω^∗_t satisfies the required properties.

Moreover, we will construct ω^∗_j+1 based on ω^∗_j by changing the weights of _s() and E() on a small number of vertices, such that no vertex has its weight changed more than once during the whole procedure.
Recall that U() is the set of uncovered vertices.
If |U()| is large then we construct ω^∗_j+1 from ω^∗_j via assigning weights to edges that contain at least k-1 vertices in U().
Suppose that |U()| is small.
Since ϕ() ≥α, not all of the weight of ω^∗_0 can contributed by  copies of F^∗_s.
Thus there must exist edges e ∈ E(H) with positive weight under ω^∗_0.
We use this to find e ∈ E(H) with ω^∗_j(e) > 0.
The crucial property is that a copy of F^∗_s might be obtained from an edge by adding a few extra vertices to it.
We use this to obtain ω^∗_j+1 from ω^∗_j by reducing the weight on e before assigning weight to some copy of F^∗_s which originates from e.
More care is needed to ensure that ω^∗_j+1 is indeed a weighted fractional { F^∗_s, E^∗_s }-tiling.
Ideally we would like that the extra vertices which are added to e to form a copy of F^∗_s are not saturated, if possible.

We summarise and recall the relevant properties of F^∗_s, which was originally as defined at the beginning of Subsection <ref>.
There exists a 2-graph G_s on [k] with ℓ≤ k-1 edges which consists of a disjoint union of paths.
Suppose e_1, …, e_ℓ is an enumeration of the edges of G_s and e_i = j_i j'_i for all 1 ≤ i ≤ s.
If X = { x_1, …, x_k }, then we may describe F^∗_s as having vertices V(F^∗_s) = X ∪{ y_1, …, y_ℓ}, and the edges of F^∗_s are X together with (X ∖{ x_j_i}) ∪{ y_i} and (X ∖{ x_j'_i}) ∪{ y_i} for all 1 ≤ i ≤ℓ.
We call c(F^∗_s) = X and p(F^∗_s) = { y_1, …, y_ℓ} the core and pendant vertices of F^∗_s, respectively.


The following two lemmas are needed for the case when U() is small.
The idea is the following: suppose H is a k-graph on n vertices with δ_k-1(H) ≥ (1/2 + 1/(2s) + γ)n.
If X is a k-edge in H, we would like to extend it into a copy F of F^∗_s such that c(F) = X.
Lemma <ref> will indicate where should we look for the vertices of p(F).

 
	Let k ≥ 3, s ≥ 2k^2 and ℓ≤ k - 1.


	Suppose that N_i ⊆ [n] are such that |N_i| ≥ (1/2 + 1/(2s) + γ)n for all 1 ≤ i ≤ k.
	Let G be a 2-graph on { N_1, …, N_k } such that N_i N_j ∈ E(G) if and only if |N_i ∩ N_j| ≤ (ℓ/s + γ)n.
	Then G is bipartite.



	We will show that G does not have any cycle of odd length.
	It suffices to show that N_i_1 N_i_2j+1∉ E(G) for all paths N_i_1… N_i_2j+1 in G on an odd number of vertices.
	
	For any S ⊆ [n], write S := [n] ∖ S.	
	First, note that if N_i is adjacent to N_j in G, then |N_i ∖N_j| = |N_i ∩ N_j| ≤( ℓ/s + γ) n and |N_j∖ N_i| ≤ (n - |N_j|) - (|N_i| - |N_i ∩ N_j|) ≤( ℓ/s - γ) n.
	Hence if N_i N_j N_k is a path on three vertices in G, then 
	
    |N_i ∖ N_k|  ≤ |N_i ∖N_j| + |N_j∖ N_k| ≤ 2 ℓ n / s.

		
	Now consider a path in G on an odd number of vertices.
	Without loss of generality (after a suitable relabelling), we assume the path is given by N_1 N_2 … N_2j+1 for some j which necessarily satisfies 2j+1 ≤ k.
	By using the previous bounds repeatedly, we obtain
	
    |N_1∖ N_2j+1|
    		   ≤ |N_1 ∖ N_3| + |N_3 ∖ N_5| + … + |N_2j-1∖ N_2j+1|
    		≤2 ℓ j n/s≤ℓ (k-1) n/s.

	Since ℓ≤ k-1 and s > 2k^2, we obtain 
	
    |N_1∩ N_2j+1|
    	   ≥ |N_1| - ℓ(k-1)n/s≥( 1/2 + 1/2s + γ) n - (k-1)^2 n /s
    	> ( ℓ/s + γ) n.

	Hence, N_1 N_2j+1∉ E(G) as desired.


































 
	Let k ≥ 3 and s ≥ 5k^2 with s ≢0  k.
	Let 1/n ≪γ, 1/k and θ > 0.
	Let H be a strongly (1/2 + 1/(2s) + γ, θ)-dense k-graph on n vertices.
	
	Let X = { x_1, …, x_k } be an edge of H and let N_i = N_H(X ∖{ x_i }) for all 1 ≤ i ≤ k.
	Let S ⊆ V(H) with |S| ≤ (ℓ/s + γ/3)n and y_0 ∈ N_1 ∩ N_2.
	Suppose either |N_1 ∩ N_2| < (ℓ/s + 2 γ / 3)n or |N_i ∩ N_j| ≥ (ℓ/s + 2 γ/3)n for all 1 ≤ i, j ≤ k.
	Then there exists a copy F^∗ of F^∗_s such that c(F^∗) = X and p(F^∗) ∩ (S ∖{ y_0 }) = ∅.



	Note that |N_i| ≥ (1/2 + 1/(2s) + γ)(n-k+1) ≥ (1/2 + 1/(2s) + 2γ/3)n for all 1 ≤ i ≤ k.
	Let G be the 2-graph on [k] such that ij ∈ E(G) if and only if |N_i ∩ N_j| < (ℓ/s + 2γ/3)n.
	Note that if ij ∉ E(G), then |N_i ∩ N_j| ≥ (ℓ/s + 2 γ/3)n ≥ |S|+ℓ. 
	
	Recall that G_s, the 2-graph which defines F^∗_s, is a disjoint union of paths.
	By our assumption, either 12 ∈ E(G) or G is empty.
	By Lemma <ref>, G is bipartite.
	Thus, in either case, there exists a bijection ϕ: V(G_s) → [k] such that {ϕ(j_i) ϕ(j'_i) : j_i j'_i ∈ E(G_s) }∩ E(G) ⊆{ 12 }.
	
	Let e_1, …, e_ℓ be an enumeration of the edges of E(G_s).
	Consider e_i = j_i j'_i ∈ E(G_s).
	If {ϕ(j_i), ϕ(j'_i) } = { 1, 2 }, then let y_i = y_0.
	Otherwise, ϕ(j_i) ϕ(j'_i) ∉ E(G) and therefore |N_ϕ(j_i)∩ N_ϕ(j'_i)| ≥ |S| + ℓ.
	Thus we can greedily pick y_i ∈ (N_ϕ(j_i)∩ N_ϕ(j'_i)) ∖ S such that y_1, …, y_ℓ are pairwise distinct.
	Then there exists a copy F^∗ of F^∗_s with c(F^∗) = X and p(F^∗) = { y_1, …, y_ℓ}, which satisfies the required properties.


Now we are ready to prove Lemma <ref>.


	We may assume that γ≪α, 1/k, 1/s.
	Recall that our aim is to define a sequence of fractional { F^∗_s, E^∗_s }-tilings ω^∗_0, …, ω^∗_t, for some t ≥ 0.
	Let 
    ν_1 = s/25 k M_s^k,  ν_2 = γ/40 k^3 s^k,   and  ν = ν_1 ν_2/2.

	Choose θ≪α, 1/k and 1/n_0 ≪α, γ, 1/k, 1/s.
	Let  be a strongly (1/2 + 1/(2s) + γ, θ)-dense k-graph on n ≥ n_0 vertices with ϕ() ≥α.
	Choose t = ⌊ν_2 ϕ(H) n ⌋.
	
	Recall that G_s, ℓ, F_s, m_s, M_s are given by Proposition <ref> and they satisfy (<ref>) and (<ref>). 







	Let  be an { F_s, E_s }-tiling on  with ϕ() = ϕ().
	Apply Proposition <ref> and obtain a weighted fractional { F^∗_s, E^∗_s }-tiling w^∗_0 satisfying all the properties of the proposition.
	
	Given that ω^∗_j has been defined for some 0 ≤ j ≤ t, define 
    A_j = { v ∈ V() : ∀ J ∈^∗_s() ∪ E(),  ω^∗_j(J) α_J(v) = ω^∗_0(J) α_J(v) }.

	So A_j is the set of vertices such that ω^∗_j is “identical to w^∗_0”.
	Note that by Proposition <ref><ref>, for all v ∈ A_j,
	
    ω^∗_j(v) = ω^∗_0(v) ∈{0,1}.

	Clearly we have A_0 = V().
	Let 𝒯^+_0 = { J ∈^∗_s() ∪ E() : ω^∗_0(J) > 0 }.
	The set A_j will indicate where we should look for graphs J ∈𝒯^+_0 whose weight on ω^∗_j is known (by knowing the weight on J ∈ω^∗_0), and we will modify those to define the subsequent weighting ω^∗_j+1.
	




	By Proposition <ref> and (<ref>), we have that for all J ∈𝒯^+_0, if V(J) ∩ A_j ≠∅, then ω^∗_j(J) = ω^∗_0(J) and therefore
	
    ω^∗_j(J) - 1/M_s^-k
    		= 0    if J ∈ E(H) or m_s = M_s,
    ≥ c    otherwise.

	
	Now we turn to the task of making the construction of ω^∗_1, …, ω^∗_t explicit.
	
	 
		There is a sequence of weighted fractional { F^∗_s, E^∗_s }-tilings ω^∗_1, …, ω^∗_t such that for all 1 ≤ j ≤ t, 
			
  *  A_j ⊆ A_j-1 and |A_j| ≥ |A_j-1| - 5k^2;
			
  *  (ω^∗_j)_min≥ c and
			
  *  ϕ(ω^∗_j) ≤ϕ(ω^∗_j-1) - ν_1/n.
		
	

	Note that Lemma <ref> follows immediately from Claim <ref> as ϕ(ω^∗_t) ≤ϕ() - ν_1 t / n ≤ (1 - ν) ϕ().
	
	Proof of Claim <ref>.
	Suppose that, for some 0 ≤ j < t, we have already defined ω^∗_0, ω^∗_1, …, ω^∗_j satisfying <ref>–<ref>.
	We write U_i = U(ω^∗_i), for each 0 ≤ i ≤ j.
	Observe that U_0 = U() by the choice of ω^∗_0 and Proposition <ref><ref>.
	Note that <ref> implies that |A_j| ≥ |A_0| - 5 k^2 j ≥ n - 5k^2 ν_2 ϕ(H)n ≥ (1 - αγ / 40)n, and therefore 
	
    |V ∖ A_j| = n - |A_j| ≤αγ/40 n.
	





	
	Now our task is to construct ω^∗_j+1.
	We will use the following shorthand notation.		
	For all J ∈^∗_s() ∪ E(), if we have already specified the values of ω^∗_j+1, then let 
    ∂(J) = ω^∗_j+1(J) - ω^∗_j(J).
	
	The proof splits on two cases depending on the size of U_0.
	
	Case 1: |U_0| ≥ 3 α  n / 4.
	
	Note that (U_0∖ U_j)∩ A_j=∅, which implies that A_j ∩ U_0⊆ A_j ∩ U_j.

	By (<ref>), |A_j ∩ U_j| ≥ |A_j ∩ U_0| ≥ |U_0| - αγ n / 40 ≥ 3 α n / 4 - αγ n / 40 ≥α n / 2.
	Together with 1/n ≪α, we get 
    |U_j ∩ A_j |k - 1≥α n / 2 k - 1≥α^k-1/2^knk - 1≥θnk - 1 + k^2 nk - 2
 as θ, 1/n ≪α, 1/k.
	Since  is strongly (1/2 + 1/(2s) + γ, θ)-dense, we can (greedily) find k disjoint (k-1)-sets W_1, …, W_k of U_j ∩ A_j such that (W_i) ≥ (1/2 + 1/(2s) + γ)(n - k + 1) for all 1 ≤ i ≤ k.
	Define N_i = N(W_i) ∩ A_j.
	Then 
    |N_i|
    	   ≥( 1/2 + 1/2s + γ)(n-k+1) - (n - |A_j|) (<ref>)≥( 1/2 + 1/2s + γ/2) n.

	
	Suppose that for some 1 ≤ i ≤ k, there exists x ∈ N_i ∩ U_j.
	Then e = { x }∪ W_i ∈ E(), so we can define ω^∗_j+1(e ) = 1 and ω^∗_j+1(J) = ω^∗_j(J) for all J ∈ (^∗_s() ∪ E()) ∖{ e }.
	In this case, |A_j+1| = |A_j| - k ≥ |A_j| - 5k^2, (ω^∗_j+1)_min = (ω^∗_j)_min≥ c and ϕ(ω^∗_j+1) = ϕ(ω^∗_j) - 3s/(5n) ≤ϕ(ω^∗_j) - ν_1 / n so we are done.
	Thus, we may assume that 
    ⋃_1 ≤ i ≤ k N_i ⊆ A_j ∖ U_j.
	

	
	For all F^∗∈^∗_s() and e ∈ E(), define 
	
    d_F^∗ = ∑_i=1^k| N_i ∩ c(F^∗) |
    	 and 
    	d_e = ∑_i=1^k |N_i ∩ e|.


	
	Case 1.1: there exists F^∗∈^∗_s(H) with ω^∗_j(F^∗) > 0 and d_F^∗≥ k+1.
	There exist distinct i, i' ∈{1, …, k} and distinct x∈ N_i∩ c(F^∗), x' ∈ N_i'∩ c(F^∗) such that both e_1 = W_i ∪{ x } and e_2 = W_i'∪{ x' } are edges in .
	Note that since x ∈ A_j, by (<ref>) we have ω^∗_j(F^∗) = ω^∗_0(F^∗) ≥ M_s^-k.
	Also, since x, x' ∈ c(F^∗), α_F^∗(x), α_F^∗(x') ≥ m_s.
	Define ω^∗_j+1 to be such that
	
    ∂(J) 
    	= 
    	m_s M_s^-(k+1)   if J ∈{ e_1, e_2},
    
    	-M_s^-k   if J = F^∗,
    
    	0    otherwise.

	Then ω^∗_j+1 is a weighted fractional { F^∗_s, E^∗_s }-tiling.
	First, note that |A_j+1| = |A_j| - (3k + ℓ - 2) ≥ |A_j| - 5k^2.
	Secondly, using (<ref>) we have that ω^∗_j(F^∗) is either 0 or at least c.
	Thus we obtain
	
    (ω^∗_j+1)_min   ≥min{ (ω^∗_j)_min, M_s ω^∗_j+1(e_1), c }≥min{ c, m_s M_s^-k, c }≥ c.

	Finally,
	
    ϕ(ω^∗_j) - ϕ(ω^∗_j+1)
    	    = s/n( ∂(F^∗) + 3/5 (∂(e_1) + ∂(e_2) )  ) = s/n M_s^k( 6 m_s/5 M_s - 1 ).

	Using (<ref>), s ≥ 5k^2, ℓ≤ k-1 and k ≥ 3, we can lower bound m_s/M_s by 
    m_s/M_s≥M_s - 1/M_s≥s - ℓ - k/s - ℓ = 1 - k/s -  ℓ≥ 1 - k/5k^2 - k+1≥40/43.

	We deduce ϕ(ω^∗_j) - ϕ(ω^∗_j+1) ≥ 5 s / (43 M_s^k n) ≥ν_1 / n, so we are done in this subcase.
	
	Case 1.2: there exists e ∈ E(H) with ω^∗_j(e) > 0 and d_e≥ k+1.
	We prove this case using a similar argument used in Case 1.1.
	There exist distinct i, i' ∈{1, …, k} and distinct x, x' ∈ e such that both e_1 = W_i ∪{ x } and e_2 = W_i'∪{ x' } are edges in .
	Since x ∈ A_j, Proposition <ref><ref> and (<ref>) implies that ω^∗_j(e) = M_s^-k.
	Define ω^∗_j+1 to be such that 
    ∂(J) = 
    	-M_s^-k   if J = e,
    
    	M_s^-k   if J ∈{  e_1, e_2 },
    
    	0    otherwise.

	Then ω^∗_j+1 is a weighted fractional { F^∗_s, E^∗_s }-tiling with |A_j+1| = |A_j| - (3k - 2) ≥ |A_j| - 5k^2.
	Note ω^∗_j+1(e) = 0 and ω_j+1^∗(e_i) > ω_j^∗(e_i) for i ∈ [2], so we have (ω^∗_j+1)_min≥ (ω^∗_j)_min≥ c.
	Note that
    ϕ(ω^∗_j) - ϕ(ω^∗_j+1)
    	    = 3 s/5 n(∂(e_1) + ∂(e_2) + ∂(e) ) =  3s/ 5 M_s^k n≥ν_1/n,
	
	so this finishes the proof of this subcase.
	
	Case 1.3: Both Cases 1.1 and 1.2 do not hold.
	Thus d_J≤ k for all J ∈^∗_s() ∪ E() with ω^∗_j(J) > 0.
	Recall that α_F^∗(v) ≤ M_s if v ∈ c(F^∗) and α_F^∗(v) = 1 if v ∈ p(F^∗).
	Thus, for all F^∗∈^∗_s() with ω^∗_j(F^∗) > 0, we have
	
    ∑_i=1^k∑_x ∈ N_iα_F^∗(x)
    	   ≤∑_i=1^k( M_s |N_i ∩ c(F^∗)| + |N_i ∩ p(F^∗)| ) 
        =  M_s d_F^∗ + ∑_i=1^k |N_i ∩ p(F^∗)| ≤ k(M_s + ℓ) ≤ s + k^2.
 Therefore,
	
    ∑_F^∗∈^∗_s∑_i=1^k∑_x ∈ N_iω^∗_0(F^∗) α_F^∗(x)
    	
    	   ≤ (s + k^2) ∑_F^∗∈^∗_s() w^∗_0(F^∗).
	
	Similarly, for e ∈ E() with ω^∗_j(e) > 0, we obtain
	
    ∑_i=1^k ∑_x ∈ N_iα_e(x)
    	    = ∑_i=1^k M_s |e ∩ N_i| = M_s d_e ≤ k M_s.

	Hence, 
    ∑_e ∈ E()∑_i=1^k ∑_x ∈ N_iω^∗_0(e) α_e(x) ≤ k M_s ∑_e ∈ E() w^∗_0(e).
	
	Combining everything, we deduce 
    ∑_i=1^k |N_i|
    	    = ∑_i=1^k ∑_x ∈ N_i 1
    	(<ref>), (<ref>)=∑_i=1^k ∑_x ∈ N_iω^∗_0(x) 
        = ∑_i=1^k ∑_x ∈ N_i∑_J ∈^∗_s() ∪ E()ω^∗_0(J) α_J(x)
    	= ∑_J ∈^∗_s() ∪ E()∑_i=1^k ∑_x ∈ N_iω^∗_0(J) α_J(x) 
       (<ref>), (<ref>)≤   (s + k^2) ∑_F^∗∈_s^∗() w^∗_0(F^∗) + k M_s ∑_e ∈ E() w^∗_0(e) 
       Prop. <ref><ref>≤   n + k^2 ∑_F^∗∈_s^∗() w^∗_0(F^∗) ≤ n + k^2/sn ≤6n/5,
 where the last inequality uses s ≥ 5k^2.
	This contradicts (<ref>) and finishes the proof of Case 1.
	
	Case 2: |U_0| < 3 α  n / 4.
	Write ,  for _, _, respectively.
	Note that n = s || + k M_s | | + |U_0|.
	Hence, 
    α≤ϕ() ≤ 1 - s/n |  | ≤1/n( k M_s | | + |U_0| ) ≤k M_s |  |/n + 3 α/4.

	Using that s ≥ 5k^2, that k ≥ 3, that 1/n ≪α, γ≤ 1 and (<ref>), we have 
    |  | ≥α n/4 k M_s≥αγ n/40 + 1 ≥  n - |A_j| + 1.

	Hence there exists E_s ∈ with V(E_s) ⊆ A_j.
	By Proposition <ref><ref>, there exists an edge X = { x_1, …, x_k }∈ E() such that X ⊆ A_j and 
    w^∗_j(X) = w^∗_0(X) = M_s^-k.

	











	We would like to use Lemma <ref> to find copies F of F^∗_s with c(F) = X, and decrease the weight of X to be able to increase the weight of an appropriate copy of F^∗_s.	
	Recall that S(ω^∗_j) is the set of saturated vertices with respect to ω^∗_j.
	We write S_j = S(ω^∗_j) and let  S' = S_j ∪ (V(H) ∖ A_j).
	Proposition <ref><ref> and (<ref>) together imply that |S'| ≤ (ℓ/s + γ/40)n.
	
	For all 1 ≤ i ≤ k, let N_i = N_H(X ∖{ x_i }).
	We may assume (by relabelling) that either |N_1 ∩ N_2| < (ℓ/s + 2γ/3)n or |N_i ∩ N_j| ≥ (ℓ/s + 2γ/3) for all 1 ≤ i, j ≤ k.
	
	Case 2.1: (N_1 ∩ N_2) ∖ S' ≠∅.
	In this case, select y ∈ (N_1 ∩ N_2) ∖ S' and apply Lemma <ref> with S', y playing the roles of S, y_0.
	We obtain a copy F_1 of F^∗_s such that c(F_1) = X and p(F_1) ∩ S' = ∅.
	Then p(F_1) ⊆ A_j ∖ S_j.
	Let P_0 = p(F_1) ∖ U_j.
	For p ∈ p(F_1) ∩ U_j, by (<ref>), ω^∗_j(p) = 0.
	For every p ∈ P_0, by the definitions of A_j and U_j, there exists J_p ∈^+_0 such that p ∈ V(J_p), and since p ∉ S_j we also can choose J_p such that α_J_p(p) ≥ m_s.
	(The J_p might coincide for different p ∈ P_0.)
	Define ω^∗_j+1 to be such that 
    ∂(J) = 
    	M_s^-k   if J = F_1,
    
    	- M_s^-k   if J = X,
    
    	- M_s^-k/m_s    if J = J_p for some p ∈ P_0,
    
    	0    otherwise.

	Then ω^∗_j+1 is a weighted fractional { F^∗_s, E^∗_s }-tiling.
	First, note that |A_j+1| ≥ |A_j| - (|V(F_1)| + ∑_p ∈ P_0 |V(J_p)| ) ≥ |A_j| - (2k+2k^2) ≥ |A_j| - 5k^2.
	Secondly, (<ref>) implies that ω^∗_j+1(X) = 0 and ω^∗_j+1(F_1) ≥ c, and moreover, for all p ∈ P_0, ω^∗_j+1(J_p) ≥ M_s^-k(1 - 1/m_s) ≥ M_s^-k-1≥ c.	Thus
	(ω^∗_j+1)_min≥ c.
	
	Finally, since |P_0| ≤ |p(F_1)| = ℓ, we have
	
    ϕ(ω^∗_j) - ϕ(ω^∗_j+1)
    	   ≥s/n(  ∂(F_1) + 3/5∂(X) + ∑_p ∈ P_0∂(J_p) )
    	≥s/n M_s^k( 2/5  - |P_0|/m_s) 
       ≥s/n M_s^k( 2/5  - ℓ/m_s).

	By (<ref>), ℓ≤ k-1 and s ≥ 5 k^2,  we get 
    ℓ/m_s≤k-1/M_s - 1≤k/M_s≤k^2/s - ℓ≤k^2/5k^2 - k + 1≤1/4,
 where the last inequality holds for every k ≥ 3.
	Thus ϕ(ω^∗_j) - ϕ(ω^∗_j+1) ≥ 3s / (20 n M^k_s) ≥ν_1 / n and we are done.
	
	Case 2.2: N_1 ∩ N_2 ⊆ S'.	
	Since H is strongly (1/2 + 1/(2s) + γ, θ)-dense and 1/n ≪γ, 1/k, we deduce |N_1 ∩ N_2| ≥ (1/s + γ)n.
	Using N_1 ∩ N_2 ⊆ S' and (<ref>), we have |N_1 ∩ N_2 ∩ S_j ∩ A_j| ≥ (1/s + γ/2)n.
	By Proposition <ref><ref>, there exists F_2 ∈^∗_s() ∩^+_0 and |p(F_2) ∩ N_1 ∩ N_2 ∩ S_j ∩ A_j| ≥ 2.
	Let y'_1, y”_1 be two distinct vertices in p(F_2) ∩ N_1 ∩ N_2 ∩ S_j ∩ A_j.



	We claim that
	
    0.85there exists F'_2 ∈^∗_s() such that p(F'_2) ∖ p(F_2) ⊆ A_j ∖ (S_j ∪ X),
    	their core vertices satisfy c(F'_2) = c(F_2),
    	and { y'_1, y”_1 }∖ p(F'_2) ≠∅.
 
	To see where we are heading, if we have found such F'_2, then our aim will be to define ω^∗_j+1 by decreasing the weight of F_2 and X, which will allow us then to increase the weight of F'_2 and a copy F'_1 of F^∗_s such that c(F'_1) = X and { y'_1, y”_1 }∩ p(F'_1) ≠∅.
	
	Let us check (<ref>) holds.
	Let Z = c(F_2) = { z_1, …, z_k } and for every 1 ≤ i ≤ k let Z_i = N_H(Z ∖{ z_i }).
	Since y'_1 ∈ p(F_2), without loss of generality (by relabelling) we may assume that y'_1 ∈ Z_1 ∩ Z_2.
	Suppose first that (Z_1 ∩ Z_2) ∖ (S' ∪ X ∪ V(F_2)) is non-empty.
	Select any y”'_1 ∈ (Z_1 ∩ Z_2) ∖ (S' ∪ X ∪ V(F_2)).
	Thus there exists F'_2 ∈^∗_s() such that c(F'_2) = Z, p(F'_2) = (p(F_2) ∖{ y'_1 }) ∪{ y”'_1 }, p(F'_2) ∖ p(F_2) = {y”'_1 }⊆ A_j ∖ (S_j ∪ X) and y'_1 ∈{ y'_1, y”_1 }∖ p(F'_2), as desired.
	Hence, we may assume Z_1 ∩ Z_2 ⊆ S' ∪ X ∪ V(F_2).
	This implies that |Z_1 ∩ Z_2| ≤ |S' ∪ X ∪ V(F_2)| ≤ (ℓ/s + γ/40)n + |X|+|V(F_2)| < (ℓ/s + 2 γ/3)n.
	Apply Lemma <ref> (with Z, Z_i, S' ∪ X ∪ V(F_2), y'_1 playing the roles of X, N_i, S and y_0, respectively) to obtain F'_2 ∈^∗_s such that c(F'_2) = Z and p(F'_2) ∩ ( S' ∪ X ∪ V(F_2) ∖{ y'_1 } ) = ∅.
	It is easily checked that F'_2 satisfies (<ref>).
	
	Now take such an F'_2 and assume (after relabelling, if necessary) that y'_1 ∉ p(F'_2).
	Apply Lemma <ref> (with X, N_i, S' ∪ V(F'_2), y'_1 playing the roles of X, N_i, S and y_0, respectively) to obtain F'_1 such that c(F'_1) = X and p(F'_1) ∩ (S' ∖{ y'_1 }) = ∅.
	
	Let P' = (p(F'_1) ∖{ y'_1 }) ∪ (p(F'_2) ∖ p(F_2)) and observe that P' ⊆ A_j ∖ S_j.
	Let P'_0 = P' ∖ U_j.
	Arguing as in the previous case we see that for every p ∈ P' ∩ U_j, ω^∗_j(p) = 0, and for every p ∈ P'_0 there exists J_p ∈^+_0 such that p ∈ V(J_p) and α_J_p(p) ≥ m_s.
	
	Let ω^∗_j+1 be such that 
    ∂(J) = 
    		M_s^-k   if J = F'_1, 
    
    		M_s^-(k+1) m_s    if J =  F'_2, 
    
    		- M_s^-k   if J ∈{ X, F_2 }, 
    
    		- M_s^-k / m_s    if J = J_p for some p ∈ P'_0,
    
    		0    otherwise.

	Since p(F'_1) ∪ p(F'_2) ⊆ P' ∪ p(F_2), the decrease of weight in F_2 and the J_p implies that the vertices in p(F'_1) ∪ p(F'_2) get weight at most 1 under ω^∗_j+1.
	Using that, it is not difficult to check that ω^∗_j+1 is indeed a weighted fractional { F^∗_s, E^∗_s }-tiling.
	
	Note that A_j∖ A_j+1⊆ V(F'_1) ∪ V(F_2) ∪ V(F'_2) ∪⋃_p ∈ P'_0 V(J_p) and |P'_0| ≤ |p(F'_1)| + |p(F'_2)| = 2 ℓ.
	Using that ℓ≤ k-1, we deduce |A_j+1| ≥ |A_j| - 3(k+ℓ) - |P'_0|(k+ℓ) ≥ |A_j| - (3 + 2 ℓ)(k+ℓ) ≥ |A_j| - 5k^2.

	Similarly as in the previous case, we deduce from (<ref>) that 

	(ω^∗_j+1)_min≥ c.
	 
	Using that |P'_0| ≤ 2 ℓ, we deduce 
    ϕ(ω^∗_j) - ϕ(ω^∗_j+1)
    		   ≥s/n( ∂(F'_1) + ∂(F'_2) + ∂(F_2) + 3/5∂(X) + ∑_p ∈ P'_0∂(J_p) ) 
        = s/n M_s^k( 1 + m_s/M_s - 1 - 3/5 - |P'_0|/m_s)
    		≥s/n M_s^k( m_s/M_s - 3/5 - 2 ℓ/m_s).

	From (<ref>), s ≥ 5k^2 and ℓ≤ k-1, we deduce 
    m_s/M_s - 3/5 - 2 ℓ/m_s   ≥2/5 - 1/M_s - 2 ℓ/m_s≥2/5 - 1 + 2 ℓ/m_s≥2/5 - k(1 + 2 ℓ)/s - ℓ - k
       ≥2/5 - 2k^2 - k/5k^2 - 2k + 1
    	= k+2/25k^2 - 10 k + 5≥k+2/25k^2≥1/25 k.

	Thus we get ϕ(ω^∗_j) - ϕ(ω^∗_j+1) ≥ s/(25 M_s^kkn) ≥ν_1/n and we are done.
	This finishes the proof of Case 2.2 and of Claim <ref>.
	□
	
	This concludes the proof of Lemma <ref>.




§ REMARKS AND FURTHER DIRECTIONS
 

The following family of examples gives lower bounds for the Turán problems of tight cycles on a number of vertices not divisible by k (and hence for the tiling and covering problem, as well).
We acknowledge and thank a referee for suggesting this construction.
We are not aware of its appearance in the literature before, although it bears some resemblance to examples considered by Mycroft to give lower bounds for tiling problems <cit.>.

 
	Let k ≥ 2 and p > 1 be a divisor of k.
	For n > 0, we define the k-graph H^k_n,p as follows.
	Given a vertex set V of size n, partition it into p disjoint vertex sets V_1, …, V_p of size as equal as possible.
	Assume that every x ∈ V_i is labelled with i, for all 1 ≤ i ≤ p.
	Let H^k_n,p be the k-graph on V where the edges are the k-sets such that the sum of the labels of its vertices is congruent to 1 modulo p.


Using this construction, we deduce the following lower bounds for _k-1(n, C^k_s) when s is not divisible by k (and therefore, also for c(n, C^k_s)).

 
	Let s > k ≥ 2 with s not divisible by k.
	Let p be a divisor of k which does not divide s.
	Then _k-1(n, C^k_s) ≥⌊ n/p ⌋ - k + 2.
	In particular, _k-1(n, C^k_s) ≥⌊ n/k ⌋ - k + 2.



	Given k, p, n, let H = H^k_n,p be the k-graph given by Construction <ref>.
	Since the sets V_i are chosen to have size as equal as possible, we deduce |V_i| ≥⌊ n/p ⌋ holds for all 1 ≤ i ≤ p.
	It is easy to check that no edge of  is entirely contained in any set V_i,
	and that, for every (k-1)-set S in V, N(S) = V_j ∖ S for some j.
	Thus δ_k-1(H) ≥⌊ n/p ⌋ - k + 2.
	
	We show that  is C^k_s-free.
	Let C be a tight cycle on t vertices in .
	It is enough to show that p divides t (since p does not divide s, it will follow that t ≠ s).
	Recall from Construction <ref> that every x ∈ V_i is labelled with i.
	We double count the sum T of the labels of vertices, over all the edges of C.
	On one hand, T ≡ 0  k since each vertex appears in exactly k edges of C and thus is counted k times.
	Since p divides k, T ≡ 0  p.
	On the other hand, the sum of the labels of a single edge is congruent to 1 modulo p and there are t of them, thus T ≡ t  p.
	This implies that p divides t.


Now we discuss covering thresholds.
Let s > k ≥ 3.
Theorem <ref> and Proposition <ref> imply that c(n, C_s^k) = (1/2 + o(1))n for all admissible pairs (k,s) with s ≥ 2k^2.
A natural open question is to determine c(n, C_s^k) for the non admissible pairs (k,s).
The smallest case not covered by our constructions is when (k,s) = (6,8), and Proposition <ref> implies that c(n, C^6_8) ≥⌊ n/3 ⌋ - 4.


	Is the lower bound for c(n, C_s^k) given by Proposition <ref> asymptotically tight, for non admissible pairs (k,s)? 
	In particular, is c(n, C^6_8) = (1/3 + o(1))n?


Now, we consider the Turán thresholds.
Theorem <ref> and Proposition <ref> also show that _k-1(n, C_s^k) = (1/2 + o(1))n for k even, s ≥ 2k^2 and (k, s) is an admissible pair.
We would like to know the asymptotic value of _k-1(n, C_s^k) in the cases not covered by our constructions.
Proposition <ref> implies that _k-1(n, C_s^k) ≥⌊ n/k ⌋ - k+ 2 for s not divisible by k; but on the other hand, if s ≡ 0  k then _k-1(n, C_s^k) = o(n), which follows easily from Theorem <ref>.

The simplest open case is when k = 3 and s is not divisible by 3.
Note that C^3_4 = K^3_4, and the lower bound _2(n, C^3_4) ≥ (1/2 + o(1))n holds in this case <cit.>.
We conjecture that in the case k=3, for s > 4 and not divisible by three, the lower bound given by Proposition <ref> describes the correct asymptotic behaviour of _k-1(n, C^k_s).


	_2(n, C^3_s) = (1/3 + o(1))n for every s > 4 with s ≢0  3.






Finally, we discuss tiling thresholds.
Let (k,s) be an admissible pair such that s ≥ 5k^2.
If k is even, then Theorem <ref> and Proposition <ref> imply that t(n, C_s^k) = (1/2 + 1/(2s) + o(1))n.
We conjecture that for k odd, the bound given by Proposition <ref> is asymptotically tight.


	Let (k,s) be an admissible pair such that k ≥ 3 is odd and s ≥ 5k^2.
	Then t(n, C_s^k) = (1/2 + k/(4 s(k-1) + 2k  ) + o(1))n.


Note that, for k odd, the extremal example given by Proposition <ref> is an example of the so-called space barrier construction.
However, it is different from the common construction which is obtained by attaching a new vertex set W to an F-free k-graph and adding all possible edges incident with W.
On the other hand, for k even, it is indeed the common construction of a space barrier.

It also would be interesting to find bounds on the Turán, covering and tiling thresholds that hold whenever k < s ≤ 5k^2. The known thresholds for these kind of k-graphs do not necessarily follow the pattern of the bounds we have found for longer cycles. For example, note that C^k_k+1 is a complete k-graph on k+1 vertices, which suggests that for lower values of s the problem behaves in a different way. Concretely, when (k, s) = (3, 4), it is known that t(n, C^3_4) = (3/4 + o(1))n KeevashMycroft2014, LoMarkstroem2015.


	Given k ≥ 3, what is the minimum s such that t(n, C_s^k) ≤ (1/2 + 1/(2s) + o(1))n holds?




§ ACKNOWLEDGEMENTS


We thank Richard Mycroft and Guillem Perarnau for their valuable comments and insightful discussions.
We also thank an anonymous referee for their comments and suggestions that simplified some parts and vastly improved the presentation of the paper.
In particular, we are grateful for their suggestions of a simpler proof of Lemma <ref> and Construction <ref>.






§ HYPERGRAPH REGULARITY


In Section <ref> we stated modified versions of some regularity statements which follow from easy modifications of the original statements or proofs.
In this appendix we sketch how to guarantee those properties hold.



 §.§ Avoiding fixed (k-1)-graphs
 

Our version of the Regular Slice Lemma (Theorem <ref>) includes an additional property (that of “avoiding” a fixed (k-1)-graph 𝒮 on the same vertex set as G) which is not present in the original statement <cit.>.
We claim that extra property follows already from their proof by doing one simple extra step.

Their proof of the Regular Slice Lemma can be summarised as follows (we refer the reader to <cit.> for the precise definitions).
First, they obtain an “equitable family of partitions” 𝒫^∗ from (a strengthened version of) the Hypergraph Regularity Lemma.
This can be used to find suitable complexes in the following way: first, for each pair of clusters of 𝒫^∗, select a 2-cell uniformly at random. Then, for each triple of clusters of 𝒫^∗ select a 3-cell uniformly at random which is supported on the corresponding previously selected 2-cells; and so on, until we select (k-1)-cells.
This will always output a (t_0, t_1, )-equitable (k-1)-complex , and the task is to check that, with positive probability,  is actually a (t_0, t_1, , _k, r)-regular slice satisfying the “desired properties” with respect to the reduced k-graph.

Having selected  at random as before, the most technical part of the proof is to show that the “desired properties” of the reduced k-graph (labelled (a), (b) and (c) in <cit.>) hold with probability tending to 1 whenever n goes to infinity.
Thankfully, that part of the proof does not require any modification for our purposes.
Moreover, the selected  will be a (t_0, t_1, , _k, r)-regular slice with probability at least 1/2.
This is shown by upper bounding the expected number of k-sets of clusters of 𝒥 for which G is not (_k, r)-regular, and an application of Markov's inequality (cf. <cit.>).
It is a natural adaptation of this method that will show that  is also (3 θ^1/2, 𝒮)-avoiding with probability at least 2/3.

Let 𝒮 be a (k-1)-graph on V(G) of size at most θnk-1.
We only need to consider the edges of 𝒮 which are 𝒫-partite.
Every 𝒫-partite edge of 𝒮 is supported in exactly one (k-1)-cell of the family of partitions 𝒫^∗, which by <cit.> is present in  with probability p = ∏_i=2^k-1 d_i^k-1j.
Thus the expected size of |E(𝒮) ∩ E(_k-1)| is at most |E(𝒮)|p ≤θ p nk-1.
By Markov's inequality, with probability at least 2/3 we have |E(H) ∩ E(_k-1)| ≤ 3 θ p nk-1.
By the previous discussion, with positive probability  satisfies all of the properties of <cit.> and also that |E(𝒮) ∩ E(_k-1)| ≤ 3 θ p nk-1.
Thus we may assume  satisfies all of the previous properties simultaneously, and it is only necessary to check that  is (3 θ^1/2, 𝒮)-avoiding.

Let t be the number of clusters of  and m the size of a cluster in .
For each (k-1)-set of clusters Y, _Y has (1 ±_k/10) p m^k-1 edges (see <cit.>).
We say a (k-1)-set of clusters Y is bad if |_Y ∩ E(𝒮)| > √(6 θ) |_Y| and let  be the set of bad (k-1)-sets.
Then 
    3 θ p nk-1   ≥∑_Y |_Y ∩ E(𝒮)| ≥ || √(6 θ) (1 - _k/10) p m^k-1,
 which implies || ≤ 3 θ^1/2tk-1.
It follows that  is (3 θ^1/2, 𝒮)-avoiding, as desired.



 §.§ Embedding lemma
 

Note that <cit.> is stronger than Lemma <ref> in the sense that it allows embeddings of k-graphs with bounded maximum degree whose number of vertices is linear in m, but we don't require that property here.

The main technical difference between Lemma <ref> and Theorem 2 in <cit.> is that their lemma asks for the stronger condition that for all e ∈ E() intersecting the vertex classes { X_i_j : 1 ≤ j ≤ k }, the k-graph G should be (d, _k, r)-regular with respect to the k-set of clusters { V_i_j : 1 ≤ j ≤ k }, such that the value d does not depend on e, and 1/d ∈ℕ; where as we allow G to be (d_e, _k, r)-regular for some d_e ≥ d depending on e and not necessarily satisfying 1/d_e ∈ℕ.
By the discussion after Lemma 4.6 in <cit.>, we can reduce to that case by working with a sub-k-complex of ∪ G which is (d, d_k-1, d_k-2, …, d_2, _k, , r)-regular, whose existence is guaranteed by an application of the “slicing lemma” <cit.>.

 
