Embedding loose trees in k k -uniform hypergraphs Yaobin Chen, Allan Lo Abstract A classical result of Komlós, Sárközy and Szemerédi shows that every large n n -vertex graph with minimum degree at least ( 1 / 2 + γ ) ​ n (1/2+\gamma)n contains all spanning trees of bounded degree. We generalised this result to loose spanning hypertrees in k k -uniform hypergraphs, that is, linear hypergraphs obtained by subsequently adding edges sharing a single vertex with a previous edge. We give a general sufficient condition for embedding loose trees with bounded degree. In particular, we show that for all k ≥ 4 k\geq 4 , every n n -vertex k k -uniform hypergraph with n ≥ n 0 ​ ( k , γ , Δ ) n\geq n_{0}(k,\gamma,\Delta) and minimum ( k − 2 ) (k-2) -degree at least ( 1 / 2 + γ ) ​ ( n k − 2 ) (1/2+\gamma)\binom{n}{k-2} contains every spanning loose tree with maximum vertex degree at most Δ \Delta . This bound is asymptotically tight. This generalises a result of Pehova and Petrova, who proved the case when k = 3 k=3 and of Pavez-Signé, Sanhueza-Matamala and Stein, who considered the codegree threshold for bounded degree tight trees. 1 Introduction The study of spanning trees of bounded degree in graphs and random graphs has been an active area of research for many years. A classical result of Komlós, Sárközy and Szemerédi [ 17 ] proved that every large n -vertex graph G with minimum degree at least (1/2+\gamma)n contains all spanning trees of bounded degree. The result is clearly the best possible, as exemplified by two disconnect complete graphs on n/2 vertices. Csaba, Levitt, Nagy-György and Szemerédi [ 4 ] showed that \gamma n can be replaced by C\Delta\log n improving a previous result of [ 18 ] . This result has also been generalized to random graphs, pseudorandom graphs and directed graphs, see [ 19 , 20 , 10 , 15 , 22 , 11 ] . In this paper, we consider an analogue of this problem for k -uniform hypergraphs. Since there is no single way to define a hypertree. We introduce the definition about hypertrees due to Kalai [ 13 ] . A k -uniform s -hypertree is defined iteratively as follows: a single k -uniform edge is a k -uniform s -hypertree; any k -graph can be obtained from a k -uniform s -hypertree T by adding a new edge e such that there exists e^{\prime}\in E(T) with |e\cap e^{\prime}|=s=|e\cap V(T)| . Note that a n -vertex k -uniform s -hypertree satisfies n\equiv s\mod k-s , which we will always assume. Throughout this paper, we refer to the k -uniform 1 -tree as k -loose tree (also known in the literature as a linear tree ). Observe that 2 -loose tree is the usual tree in graphs, since a tree can be defined as adding leaves iteratively. Also, a loose path in k -uniform graph is a k -loose tree. The minimum \ell -degree \delta_{\ell}(H) of a k -uniform hypergraph H is the minimum number of edges containing any given set of \ell vertices. Moreover, the minimum relative \ell -degree \overline{\delta}_{\ell}(G) is \delta_{\ell}(G)/\binom{n}{k-\ell} . The maximum ( relative ) \ell -degree , denoted by \Delta_{\ell}(G) (and \overline{\Delta}_{\ell}(G) , respectively) is defined analogously. Extremal problem about hypertrees has a long history. In 1995 Kalai [ 6 , Conjecture 3.6] , conjectured that every k -graph with more than \frac{t-1}{k}\binom{n}{k-1} edges contains every k -loose tree with t edges. In general, Kalai’s conjecture is still open but there are many partial results. Regarding spanning k -loose trees, Georgakopoulos, Haslegrave, Montgomery and Narayanan [ 8 ] proved that every large n -vertex 3 -graph with minimum 2 -degree at least n/3+o(n) have a spanning triangulation of a 2 -sphere, which in particular contains some spanning 3 -loose tree. Pavez-Signé, Sanhueza-Matamala and Stein [ 23 ] proved that the minimum (k-1) -degree threshold for the existence of any bounded vertex degree spanning (k-1) -hypertree. Theorem 1.1 (Pavez-Signé, Sanhueza-Matamala and Stein [ 23 ] ) . For all k\geq 2,\gamma>0 and \Delta\in\mathbb{N} , there exists an n_{0} such that any k -graph G on n\geq n_{0} vertices with \overline{\delta}_{k-1}(G)\geq 1/2+\gamma contains every n -vertex (k-1) -hypertree T with \Delta_{1}(T)\leq\Delta and the bound is asymptotic tight. In particular, G contains all n -vertex k -loose trees T with \Delta_{1}(T)\leq\Delta . For general \ell and k , what is the minimum (relative) \ell -degree threshold which forces the existence of any bounded vertex degree spanning k -loose trees? We say a k -graph G on n vertices is \Delta -loose-tree-universal , if G contains every spanning k -loose tree T with \Delta_{1}(T)\leq\Delta . Moreover, we define the loose tree embeddable (k,\ell) -threshold , denoted by \delta_{k,\ell}^{T} , to be the infimum \delta such that for any \gamma>0 and \Delta\in\mathbb{N} , there exists an integer n_{0} such that any k -graph G on n\geq n_{0} vertices with n\equiv 1\mod k-1 and \overline{\delta}_{\ell}(G)>\delta+\gamma is \Delta -loose-tree-universal. Thus Theorem 1.1 implies that \delta_{k,k-1}^{T}=1/2 . The following example shows that \delta_{k,\ell}^{T} should also guarantee a perfect matching in k -graphs. We define the binary k -loose tree T_{k,r} with depth r as follows. Let T_{k,0} be a loose tree with one edge and root it at an arbitrary vertex. We say a vertex is a leaf vertex if it is not the root vertex and in only one edge. So T_{k,0} has k-1 leaf vertices. Then for any r\geq 1 , let T_{k,r} be the loose tree by adding one edge on each leaf vertex of T_{k,r-1} . If r is even, then T_{k,r} contains a perfect matching and the maximum vertex degree of T_{k,r} is 2 , see Figure 1 . Figure 1: The binary 3 -loose tree T_{3,2} . We denote the perfect matching (k,\ell) -threshold \delta_{k,\ell}^{PM} to be the infimum \delta such that for any \gamma>0 , there exists an integer n_{0} such that any k -graph G on n\geq n_{0} vertices with k|n and \overline{\delta}_{\ell}(G)>\delta+\gamma contains a perfect matching. Ruciński and Szemerédi [ 29 ] showed that \delta_{k,k-1}^{PM}=1/2 and Hán, Person and Schacht [ 9 ] showed that \delta_{3,1}^{PM}=5/9 . See [ 31 ] for a survey. Recently, Pehova and Petrova [ 24 ] showed that every 3 -graph G with \overline{\delta}_{1}(G)>5/9 contains all bounded degree 3 -loose trees. Theorem 1.2 (Pehova and Petrova [ 24 ] ) . We have \delta_{3,1}^{T}=5/9 . In particular, for all \gamma>0 and \Delta\in\mathbb{N} , there exists an n_{0} such that any 3 -graph G on n\geq n_{0} vertices with n odd and \overline{\delta}_{1}(G)\geq 5/9+\gamma contains every spanning 3 -loose tree T with \Delta_{1}(T)\leq\Delta . Pehova and Petrova [ 24 ] further conjectured that \delta_{k,\ell}^{T}=\delta_{k,\ell}^{PM} in general. Conjecture 1.3 (Pehova and Petrova [ 24 ] ) . For all 1\leq\ell0 and \Delta\in\mathbb{N} , there exists an n_{0} such that any k -graph G on n\geq n_{0} vertices with \overline{\delta}_{k-2}(G)\geq 1/2+\gamma and n\equiv 1\mod k-1 contains every spanning k -loose tree T with \Delta_{1}(T)\leq\Delta . Note that in the proof of Theorems 1.1 and 1.2 , one ingredient is to find a tight Hamilton cycle. Tight Hamilton cycles exists by the minimum degree condition by [ 27 ] and [ 28 ] . Lang and Sanhueza-Matamala [ 21 ] and independently, Polcyn, Reiher, Rödl and Schülke [ 26 ] showed that the corresponding tight Hamilton cycle (k,k-2) -threshold is 5/9>\delta_{k,k-2}^{PM} . One of our main contributions is to provide a necessary condition, which we called the robust framework , for \Delta -loose-tree-universality, see Section 4 . Paper organization: In Section 2 , we introduce some notations and terminology that we will use throughout the paper. In Section 3 , we give a sketch proof for Theorem 1.4 . In Section 4 we give a robust framework for embedding loose trees. A robust framework will consist of three key properties, robust fractional matching, reachable and rotatable. In Section 5 , we introduce the hypergraph regularity lemma and related embedding method in the reduced graph. In Section 6 , we prove that the robust framework is sufficient for embedding loose trees. In Section 7 , we construct a subgraph G^{*} which will turn out to be a robust framework. We will verify that G^{*} satisfies the three key properties in Sections 8 , 9 and 10 . We conclude the paper with a discussion and open problems in Section 11 . 2 Preliminaries 2.1 Notation We write v_{1}\dots v_{k} for \{v_{1},\dots,v_{k}\} . We omit floors and ceilings whenever they are not crucial. We say that a statement holds for \alpha\ll\beta if there exists a non-decreasing function f such that the statement holds for \alpha0 . We say that a k -graph G has \alpha -perturbed minimum relative \ell - degree , denoted by \overline{\delta}^{\alpha}_{\ell}(G) , at least \delta , if the following hold for every j\in[\ell] (P1) every edge of E(\partial_{j}(G)) has relative degree at least \delta in G ; (P2) \overline{\partial_{j}(G)} has edge density at most \alpha ; (P3) each (j-1) -edge of \partial_{j-1}(G) has relative degree less than \alpha in \overline{\partial_{j}(G)} . We obtain the following proposition. Proposition 2.4 . Let \alpha\ll\delta\ll 1/k . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq\delta . (L1) Let S\in E(\partial_{j}(G)) with j\leq k-2 . Then the link graph L_{G}(S) of S satisfies \overline{\delta}^{\alpha}_{k-j-2}(L_{G}(S))\geq\delta . (L2) Let A_{1},\dots,A_{\ell} be subsets of V(G) with each of size m\leq k-4 . Let B\subseteq V(G) with size larger than \alpha mn . Then there exists an edge uv with u,v\in B and uv\in\bigcap_{i=1}^{\ell}E(\partial_{2}(A_{i})) . Proof. Note that (L1) follows from Definition 2.3 . For (L2) , by Definition 2.3 , there are at most \alpha n isolated vertices in \partial_{2}(A_{i}) for i\in[\ell] . This implies that there is a vertex v\in V(G) which is not isolated in all \partial_{2}(A_{i}) . By Definition 2.3 (P3) , the relative degree of v in V(\overline{\partial_{2}(A_{i})}) is at most \alpha . Note that \displaystyle|B|-m\cdot\alpha n>\alpha mn-\alpha mn=0. Hence, there exists an edge uv\in\bigcap_{i=1}^{\ell}E(\partial_{2}(A_{i})) with u,v\in B . ∎ We remark that the transition from perturbed edges to perturbed minimum degree comes at negligible costs. We get the following lemma. Lemma 2.5 ( [ 21 , Lemma 2.3] ) . Let 1/n\ll\varepsilon\ll\alpha\ll\delta,1/k . Let G be a k -graph on n vertices with \overline{\delta_{\ell}}(G)\geq\delta . Let I be a subgraph of G of edge density at most \varepsilon . Then there exists a spanning subgraph G^{\prime} of G-I with \overline{\delta}^{\alpha}_{\ell}(G^{\prime})\geq\delta-\alpha . 3 Proof sketch of Theorem 1.4 In this section, we sketch the proof of Theorem 1.4 and discuss some new ideas we used. Let T be a k -loose tree on n vertices. Suppose that we are given a large k -graph G with n vertices with \overline{\delta}_{k-2}(G)\geq 1/2+2\gamma . We now find an embedding of T in G using the absorption technique, which splits the proof into the following three steps. Step 1: find an absorber. Fix a root vertex r in T such that T is union of two k -loose trees T_{1} and T_{2} both rooted at r , where T_{1} is small. Find an embedding \psi_{1} from T_{1} to G such that any almost embedding of T can be extended to a full embedding (see Lemma 6.3 ). Step 2: embed an almost spanning tree. Remove the vertices in G that is used to embed T_{1}\setminus r and call the resulting graph G_{2} . Since T_{1} is small, \overline{\delta_{\ell}}(G_{2})\geq 1/2+\gamma . Find an almost embedding \psi_{2} from T_{2} into G_{2} such that \psi_{1}(r)=\psi_{2}(r) , that is, the root vertices of T_{1} and T_{2} are mapped to the same vertex in G . Together with \psi_{1} , we obtain an almost embedding from T to G . Step 3: complete the embedding. Extend the embedding of Step 2 to be a spanning tree by our absorber. Clearly, Step 3 follows immediately from Steps 1 and 2. Our proof of Step 1 follows a similar approach to [ 24 ] , which was inspired by [ 1 , 2 , 30 ] . We describe the key ingredient for the absorber. Suppose we have already had an almost embedding \psi of T and we would like to extend the embedding by attaching an edge to \psi(x) . Pick vertices w_{2},\dots,w_{k} in G that are not covered. The embedding \psi_{1} of T_{1} contains some (unused) absorbing tuple, which consists of k-1 vertex disjoint loose stars. More importantly, the centres of these star together with \psi(x) is an edge in G and (in \psi ) we can replace centres of these stars with w_{2},\dots,w_{k} . Thus we have ‘enlarged’ the embedding \psi . See Section 6.1 for further details. Note that \overline{\delta_{1}}(G)\geq 1/2+\gamma is already sufficient for Step 1. Therefore, we now focus on Step 2. In particular, we aim to find an almost spanning k -loose tree T_{2} in the k -graph G_{2} . We first apply the weak hypergraph regularity lemma and obtain a reduce graph R_{2} . To embed T_{2} into G_{2} , we find a homomorphism \phi from T_{2} to R_{2} and then turn it into an embedding of T_{2} in G_{2} . Note that we need to ensure that \phi does not map too many vertices of T_{2} into one particular cluster of R_{2} . We now give a sketch on how to construct \phi and highlight the necessary properties of R_{2} that we need (see Section 4 for their formal definitions). First we find a perfect matching M=\{e_{1},\dots,e_{\ell}\} in R_{2} . This exists by our assumption as \overline{\delta}_{k-2}(R_{2})\geq\overline{\delta}_{k-2}(G_{2})-\gamma/2\geq(1+\gamma)/2\geq\delta_{k,k-2}^{PM} . We break T_{2} into smaller trees T_{2,1},\dots,T_{2,s} with a large constant s\gg\ell , where T_{2,i} is a subtree of \bigcup_{i^{\prime}\in[i]}T_{2,i^{\prime}} . We construct our homomorphism \phi by first mapping (most of) T_{2,1},\dots T_{2,s_{1}} into e_{1} , T_{2,s_{1}+1},\dots T_{2,s_{2}} into e_{2} and so on. Since T_{2} is connected, we require e_{1} to be connected to e_{2} or else we cannot find a homomorphism. However just being in the same loose component is not sufficient as illustrated by the following example. Suppose that R is a 4 -graph with vertex set V_{1}\cup V_{2} with V_{1}\cap V_{2}=\emptyset and that all edges in R contains even number of vertices in V_{1} . Observe that there is no homomorphism of a 4 -loose path that maps edges to an edge in V_{1} and an edge in V_{2} . Thus, we require a stronger notation, which we call ‘reachable’. Roughly speaking, an edge e is reachable from an edge f if we can find a homomorphism of T_{2} that maps its root to a given vertex in f and maps almost all vertices of T_{2} to e . Note that reachable may not be symmetric but induces a partial ordering. We require that reachable induced a linear ordering on M , namely, e_{j} is reachable from e_{i} for i\leq j . Recall that \phi will map most of T_{2,1},\dots T_{2,s_{1}} into e_{1} . Suppose for each such T_{2,i} , majority of its vertices lie in the same colour class that contains in its root. Thus a naive homomorphism from \bigcup_{i\in[s_{1}]}T_{2,i} into e_{1} will map most of the vertices onto one vertex of e_{1} . In order to ensure that each vertex of e_{1} has similar number of preimages, we require each edge to be ‘rotatable’. We say that R_{2} is ‘robust’ if it satisfies the three mentioned properties of having a perfect (fractional) matching, reachable and rotatable. In fact, one of our contribution is to show that being robust is already suffices to Step 2, that is, finding a almost spanning tree, see Section 6.2 . Recall in the outline of Step 2 that we require both roots of T_{1} and T_{2} to be mapped onto the same vertex x^{*} in G . Hence, we actually find a robust subgraph in the reduce graph before Step 1 . In particular, we pick x^{*} to be in the ‘first edge’ of M (in the ordering induced by reachability). After embedding T_{1} , the clusters of the reduce graph may have different sizes. Since T_{1} is small, our robust condition still ensures the existence of a perfect fractional matching. 3.1 Verifying robustness Marjory of our paper is dedicated to verifying the reduce graph contains a spanning robust subgraph. We first review the known cases when (k,\ell)=(k,k-1) [ 23 ] and (k,\ell)=(3,1) [ 24 ] . In both cases, we have \delta_{k,\ell}^{T}=\delta^{THC}_{k,\ell} . This ensures that there is a tight Hamilton cycle C in the reduce graph. Note that C contains a perfect fractional matching. By winding around C , one can show that C is reachable. When (k,\ell)=(3,1) , C is also rotatable (c.f. [ 24 , Lemma 3.1] ). Therefore C is robust. In this paper, we consider the case (k,\ell)=(k,k-2) with k\geq 4 . Most importantly, \delta^{PM}_{k,k-2}<\delta^{THC}_{k,k-2} as discussed in Section 1 . Thus, one cannot guarantee a tight Hamiltonian cycle in the reduce graph and so various new ideas are needed to find a spanning robust subgraph. For simplicity, we focus on the case when (k,\ell)=(4,2) . We first describe the structure of the robust subgraph. Consider A\in\binom{V(R)}{2} . Note that its link graph is a 2 -graph and let C_{A} be the largest component. Let E_{A} be the set of 4 -edges of the form e\cup A for e\in E(C_{A}) . Note that edges in E_{A} are tight connected (and being tight connected is ideal for being reachable). Let R^{*} be the subgraph induced by union of E_{A} for all A\in\binom{V(R)}{2} . See Section 7 for formal definition. In Section 8 , we show that R^{*} satisfies the perfect matching property. Recall that E_{A} is tight connected for A\in\binom{V(R)}{2} . Thus edges in E_{A} are reachable within themselves. We can define an equivalent relationship on \binom{V(R)}{2} such that A\sim A^{\prime} if and only if E_{A}\cup E_{A^{\prime}} are reachable within themselves. This can be represented by a colouring of \binom{V(R)}{2} , i.e. an edge-colouring of the complete graph on V(R) . Furthermore, we prove that the colouring is Gallai (i.e., no rainbow triangle) and locally 2 -edge colouring, see Lemma 9.11 . By analysing monochromatic components, we obtain the desired enumeration of E_{R^{*}} . See Section 9 for further discussions and its proof. Roughly speaking, for a permutation \sigma\in S_{4} , we say that an edge e=x_{1}x_{2}x_{3}x_{4} is \sigma -rotatable if for any 4 -loose tree T with root r and i\in[4] , there is a homomorphism \psi such that r maps to x_{i} and most of C_{i}(T) is mapped to x_{\sigma(i)} . Thus e is rotatable if it is \sigma -rotatable for all \sigma\in S_{4} . We will show that e is \sigma -rotatable for \sigma\in\{(12),(13),(14)\} . Since \{(12),(13),(14)\} is a generator set of S_{4} , we can then deduce that e is rotatable. It should be noted that the general case when k\geq 4 can be deduced to the case when k=4 . See Section 10 for further discussions and its proof. 4 A sufficient condition for almost spanning trees embedding In this section, we discuss some natural conditions and give a sufficient condition for embedding almost spanning loose trees. We now consider a k -graph G with its reduced graph R obtained by hypergraph regularity lemma (see Section 5 ). Let T be an almost spanning k -loose tree. To embed T , we will construct a homomorphism \phi from T to R and then turn it into an embedding in G . Next, we discuss three natural conditions that R needs to satisfy in order to construct \phi . Recall that there exists a bounded vertex degree loose tree with a perfect matching. Thus, we seek a (fractional) perfect matching structure in R . Secondly, any two edges in a loose tree are connected by a loose path. This requires us to connect edges in the matching of R . It is called reachable . Meanwhile, to construct homomorphism in reduced graph R , we need to guarantee that there is no cluster overused. This is called rotatable . Formally, we have the following definitions. Definition 4.1 . ( \omega -fractional matching) Let G be a k -graph and a vertex weighting \omega:V(G)\rightarrow[0,1] . We say \omega^{*}:E(G)\rightarrow[0,1] is an \omega -fractional matching if \sum_{e\ni v}\omega^{*}(e)\leq\omega(v) for all v\in V(G) . The size of \omega^{*} is \sum_{e\in E(G)}\omega^{*}(e) . We say \omega^{*} is perfect if the size of \omega^{*} is \sum_{v\in V(G)}\omega(v)/k . The next definition will enable us to find a tree homomorphism on the reduced graph from one edge to another edge. Definition 4.2 . (Reachable) Let G be a k -graph and C\in\mathbb{N} . We say that an edge e\in E(G) is C -reachable from a vertex u\in V(G) if for any rooted k -loose tree T at r , there exists a homomorphism \phi from T to G such that \phi(r)=u and \phi(v)\in e for all v with \text{dist}(r,v)>C . Moreover, we say e is C -reachable from e^{\prime}\in E(G) if e is C -reachable from all u\in e^{\prime} . Meanwhile, we define a rotation property to embed vertices on each cluster in the reduced graph balanced. Recall that S_{k} is the set of permutation of [k] . Definition 4.3 . (Rotatable) Let C\in\mathbb{N} , G be a k -graph and e=u_{1}\dots u_{k}\in E(G) . We say e is C -rotatable if for any u\in e , any \sigma\in S_{k} and any rooted k -loose tree T at r , there exists a homomorphism \phi from T to G such that \phi(r)=u and \phi(v)=u_{\sigma(s)} for all v\in C_{s}(T) with \text{dist}(r,v)\geq C . The next property shows that reachable and rotatable imply that we can map most edges in a tree to some specific edge while the root vertex is mapped to another edge. Proposition 4.4 . Let G be a k -graph, v\in V(G) and e=x_{1}\dots x_{k}\in E(G) . Suppose that e is C -reachable from v and C^{\prime} -rotatable. Let T be a rooted k -loose tree at r with \Delta_{1}(T)\leq\Delta . Then there exists a homomorphism \phi from T to G such that \phi(r)=v and for all j\in[k] , |C_{j}(T)\backslash\phi^{-1}(x_{j})|\leq(k\Delta)^{C+C^{\prime}}. Proof. By Definition 4.2 , there is a homomorphism \phi^{\prime} from T to G such that for w\in V(T) with \text{dist}(r,w)\geq C , \phi^{\prime}(w)\in e . Let \tau=(12\dots k)\in S_{k} . Then for vertex w\in V(T) with \text{dist}(r,w)=C and w\in C_{i}(T) , consider the subtree T(w) with colour classes C_{j}(T(w))=C_{\tau^{i-1}(j)}(T)\cap V(T(w)). Hence, w\in C_{i}(T)\cap V(T(w))=C_{1}(T(w)) . By Definition 4.3 , there is a homomorphism \phi_{w} from T(w) to G such that \phi_{w}(w)=\phi^{\prime}(w)\in e and, for each vertex x\in C_{\tau^{-(i-1)}(j)}(T(w))=C_{j}(T)\cap V(T(w)) with \text{dist}(w,x)\geq C^{\prime} , we have \phi_{w}(x)=x_{j} . Define \phi to be such that \phi(u)=\begin{cases}\phi^{\prime}(u)&\quad\text{ if }\text{dist}(r,u)\leq C,\\ \phi_{w}(u)&\quad\text{ if }u\in T(w).\end{cases} If u\in C_{j}(T) with \text{dist}(r,u)\geq C+C^{\prime} , then we have \phi(u)=x_{j} . So |C_{j}(T)\backslash\phi^{-1}(x_{j})|\leq(k\Delta)^{C+C^{\prime}} . ∎ Next, we define the key properties for embedding almost spanning loose trees. Definition 4.5 . Let G be a k -graph on n vertices and \eta>0 . We say G is \eta - robust if (R1) for any vertex weighting \omega:V(G)\rightarrow[0,1] with \sum_{v\in V(G)}\omega(v)\geq(1-\eta)|V(G)| and \omega(v)=0 if v is an isolated vertex of G , there exists a perfect \omega -fractional matching \omega^{\ast} of G ; (R2) there exists an integer C_{1}=C_{1}(n) and an enumeration of E(G) , e_{1},e_{2},\dots,e_{|E(G)|} such that e_{i} is C_{1} -reachable from e_{j} for all i\geq j ; (R3) there exists an integer C_{2}=C_{2}(n) such that all edges in E(G) are C_{2} -rotatable. For 1\leq\ell\leq k-1 , the robust \ell -degree threshold for k -graph , denoted by \delta_{k,\ell}^{R} , is the infimum \delta>0 such that for 1/n\ll\alpha\ll\eta\ll\gamma , every k -graph G on n vertices with \overline{\delta}^{\alpha}_{\ell}(G)\geq\delta+\gamma contains an \eta -robust spanning subgraph. We remark that our proof shows that C_{1},C_{2}\leq n^{4k} . Since we will seek an \eta -robust subgraph in the reduced graph, C_{1} and C_{2} will be treated as large constants independent of the order of host graph. Note that (R1) implies that G contains a perfect matching, so we have \displaystyle\delta_{k,\ell}^{R}\geq\delta_{k,\ell}^{PM}\geq 1/2. (4.1) Now, we state our general theorem. Theorem 4.6 . For k\geq 2 and \ell\in[k-1] , we have that \delta_{k,\ell}^{T}\leq\delta_{k,\ell}^{R} . By this theorem, to prove Theorem 1.4 , it suffices to show that \delta_{k,k-2}^{R}=1/2 (see Lemma 7.3 ). We prove Theorem 4.6 in Section 6 after we introduce the hypergraph regularity lemma. 5 Weak hypergraph regularity lemma A main tool we use to prove Theorem 4.6 is the weak hypergraph regularity lemma . Given \varepsilon>0 , we say that a k -partite k -graph G on sets V_{1},\dots,V_{k} is \varepsilon -regular if for every X_{i}\subseteq V_{i} of size at least \varepsilon|V_{i}| , we have that \displaystyle|d_{G}(X_{1},\dots,X_{k})-d_{G}(V_{1},\dots,V_{k})|\leq\varepsilon. A partition \{V_{0},V_{1},\dots,V_{t}\} of the vertex set of a k -graph G on n vertices is \varepsilon -regular if |V_{0}|\leq\varepsilon n , all other sets V_{i} with i\in[t] have equal size, and the graph induced by all but at most \varepsilon\binom{t}{k} k -tuple of V_{i} for i\in[t] is \varepsilon -regular. Theorem 5.1 ( [ 3 , 7 ] ) . For every \varepsilon>0 and t_{0}\in\mathbb{N} , there exist T_{0},n_{0}\in\mathbb{N} such that every k -graph G with at least n_{0} vertices admits an \varepsilon -regular partition \{V_{0},V_{1},\dots,V_{t}\} , where t_{0}\leq t\leq T_{0} . Given an \varepsilon -regular partition \mathcal{Q}=\{V_{0},\dots,V_{t}\} of the vertex set of a k -graph G , we define the (\mathcal{Q},\varepsilon,d) -reduced graph R on vertex set \{1,\dots,t\} corresponding to the sets \{V_{0},\dots,V_{t}\} . The edges of R are all \varepsilon -regular k -tuples of density at least d . By Lemma 2.5 , we can imply the following degree version of hypergraph regularity lemma. Lemma 5.2 . For 0\ll\varepsilon\ll\alpha\ll d\ll\delta , k>j\geq 1 and t_{0},\in\mathbb{N} , there exist T_{0},n_{0}\in\mathbb{N} such that the following holds. Suppose that G is a k -graph on n\geq n_{0} vertices with minimum degree \delta_{j}(G)\geq\delta\binom{n}{k-j} . Then G admits an \varepsilon -regular partition \mathcal{Q}=\{V_{0},\dots,V_{t}\} such that t_{0}\leq tj(i-1) ; (iv) for all e_{j}=x_{1}\dots x_{k}\in E(R) and distinct p,p^{\prime}\in[k] , ||\phi_{i-1}^{-1}(x_{p})\cap V(\mathcal{T}^{j}_{\leq i-1})|-|\phi_{i-1}^{-1}(x_{p^{\prime}})\cap V(\mathcal{T}^{j}_{\leq i-1})||\leq 2k\Delta\xi tm+(i-1)k(k\Delta)^{C_{1}+C_{2}}. We now give a rough interpretation of (i) to (iv) . Property (i) means most of T_{i^{\prime}} is mapped to some edge e_{j(i^{\prime})} in R . Note that \mathcal{T}_{\leq i-1}^{j} is all trees T_{i^{\prime}} mapped to e_{j} with i^{\prime}km\sum_{j\in[|E(R)|]}\omega^{\prime}(e_{j})-2\Delta\xi tkm|E(R)| \displaystyle\overset{\mathclap{\text{\eqref{edge total weight}}}}{\geq}(1-\eta-\alpha/2)tm-2\Delta\xi t^{k+1}km\geq(1-\eta-\alpha)tm\geq|V(T)|, a contradiction. Let e_{j(i)}=y_{1}\dots y_{k} and \pi\in S_{k} be such that |\phi^{-1}_{i-1}(y_{\pi(1)})\cap V(\mathcal{T}^{j}_{\leq i-1})|\leq\dots\leq|\phi^{-1}_{i-1}(y_{\pi(k)})\cap V(\mathcal{T}^{j}_{\leq i-1})|. Recall that (R2) and (R3) say that e_{j} is C_{1} -reachable from v and C_{2} -rotatable. By Proposition 4.4 , there exists a homomorphism \phi^{\prime} from T_{i} to R such that \phi^{\prime}(r_{i})=\phi(r_{i}) and, for all j\in[k] , \displaystyle|C_{j}(T_{i})\backslash\phi^{\prime-1}(y_{j})|\leq(k\Delta)^{C_{1}+C_{2}}. (6.3) Define a homomorphism T_{\leq i} to R such that \phi_{i}(u)=\begin{cases}\phi_{i-1}(u)&\text{ if }u\in V(T_{\leq i-1}),\\ \phi^{\prime}(u)&\text{ if }u\in V(T_{i}).\\ \end{cases} Note that from the choice of j(i) , \phi_{i} satisfies (ii) and (iii) . For distinct p,p^{\prime}\in[k] , we have \displaystyle||\phi_{i}^{-1}(x_{p})\cap V(\mathcal{T}^{j(i)}_{\leq i})|-|\phi_{i}^{-1}(x_{p^{\prime}})\cap V(\mathcal{T}^{j(i)}_{\leq i})|| \displaystyle\leq \displaystyle\max\left\{\left||\phi_{i-1}^{-1}(x_{p})\cap V(\mathcal{T}^{j(i)}_{\leq i-1})|-|\phi_{i-1}^{-1}(x_{p^{\prime}})\cap V(\mathcal{T}^{j(i)}_{\leq i-1})|\right|+\sum_{j\in[k]}|C_{j}(T_{i})\backslash\phi^{\prime-1}(y_{j})|,|V(T_{i})|\right\} \displaystyle\overset{\mathclap{\text{\ref{map4}, \eqref{eqn:C_j(T_i)}}}}{\leq} \displaystyle\max\{2k\Delta\xi tm+(i-1)k(k\Delta)^{C_{1}+C_{2}}+k(k\Delta)^{C_{1}+C_{2}},2k\Delta\xi tm\}\leq 2k\Delta\xi tm+ik(k\Delta)^{C_{1}+C_{2}}. Hence, (iv) holds. Thus we obtain a homomorphism \phi_{s} from T to R . Consider j\in[|E(R)|] with \omega^{\prime}(e_{j^{\prime}})>0 , so \omega^{\prime}(e_{j^{\prime}})\geq 1/t^{k+1} . Let i^{\prime} be maximum such that j(i^{\prime})=i , which exists as \omega^{\prime}(e_{j^{\prime}})\geq 1/t^{k+1}\geq 2\Delta\xi t . Note that \displaystyle\omega^{\prime}(e_{j})-\frac{|V(\mathcal{T}^{j}_{\leq s})|}{km} \displaystyle=\omega^{\prime}(e_{j})-\frac{|V(\mathcal{T}^{j}_{\leq i^{\prime}})|}{km}\geq\omega^{\prime}(e_{j})-\frac{|V(\mathcal{T}^{j}_{\leq i^{\prime}-1})|}{km}-\frac{|V(T_{i^{\prime}})|}{km} \displaystyle\overset{\mathclap{\text{\ref{map3}}}}{\geq}2k\Delta\xi t-2\Delta\xi t=2(k-1)\Delta\xi t. for x\in e_{j} , we have \displaystyle|\phi_{s}^{-1}(x)\cap V(\mathcal{T}^{j}_{\leq s})| \displaystyle\overset{\mathclap{\text{\ref{map4}}}}{\leq}\frac{|V(\mathcal{T}^{j}_{\leq s})|}{k}+2k\Delta\xi tm+sk(k\Delta)^{C_{1}+C_{2}} \displaystyle\leq\omega^{\prime}(e_{j})m+2\Delta\xi tm+sk(k\Delta)^{C_{1}+C_{2}}\leq\omega^{\prime}(e_{j})m+\theta^{2}m. (6.4) Therefore for each non-isolated vertex v\in V(R) , \displaystyle|\phi_{s}^{-1}(v)| \displaystyle\leq\sum_{e_{j}\in E(R)}|\phi^{-1}(v)\cap V(\mathcal{T}^{j}_{\leq s})| \displaystyle\leq\sum_{v\in e_{j}\in E(R)}|\phi^{-1}(v)\cap V(\mathcal{T}^{j}_{\leq s})|+\sum_{i\in[s]}|V(T_{i})\setminus\phi^{-1}(e_{j(i)})| \displaystyle\overset{\mathclap{\text{\eqref{eqn:phis(x)},~\ref{map1}}}}{\leq}\sum_{v\in e_{j}\in E(R)}(\omega^{\prime}(e_{j})m+\theta m)+sk(k\Delta)^{C_{1}+C_{2}} \displaystyle\leq m\sum_{v\in e_{j}\in E(R)}\omega^{\prime}(e_{j})+\zeta\theta m\overset{\mathclap{\text{\eqref{eqn:omega'(e)}}}}{\leq}(1-\zeta)\omega(v)m. We are done by setting \phi=\phi_{s} . ∎ Now, we are ready to turn this homomorphism on reduced graph to an embedding for almost spanning tree by Lemma 5.3 . Recall that if d(v,V_{2};\dots;V_{k})\geq d , v is d -dense into \{V_{2},\dots,V_{k}\} . Lemma 6.8 . Let 1/n\ll 1/t\ll 1/r\ll\varepsilon\ll\theta\ll\zeta\ll\alpha\ll\eta\ll d\ll 1/\Delta\ll 1/k . Let G be a k -graph on n vertices. Let \mathcal{Q} be a \varepsilon -regular partition of G and R be the corresponding (\mathcal{Q},\varepsilon,d) -reduced graph. Let the cluster of reduced graph R be V_{1},\dots,V_{t} and vertex set of R be [t] . Let an edge e_{1}\in E(R) be 1\dots k . Let T be a rooted k -loose tree at r with \Delta_{1}(T)\leq\Delta and |V(T)|\leq(1-\alpha-\eta)n . Then there is a vertex v^{\ast}\in V_{1} such that the following statement holds: Let A\subseteq V(G) be such that |A|\leq\eta n , |V_{i}\backslash A|\geq\theta|V_{i}| for i\in[t] and A\cap V_{i}=\emptyset for i\in[k] . Suppose that \phi is a (T,R,1,e_{1}) -homomorphism with |V_{i}\backslash A|-|\phi^{-1}(i)|\geq\zeta|V_{i}\backslash A| for i\in[t] . Then there exists an embedding \psi from T to G such that \psi(r)=v^{\ast} and for any v\in V(T) , \psi(v)\in V_{\phi(v)}\backslash A . Proof. By the definition of reduced graph R , we have that \{V_{1},\dots V_{k}\} is an \varepsilon -regular tuple with density at least d . Since d(V_{1};\dots;V_{k})\geq d , there exists a vertex z in V_{1} such that z is d/2 -dense into \{V_{2},\dots,V_{k-1}\} . Let v^{*}=z . Next we show that v^{*} is the vertex as required. Suppose that \phi is a (T,R,1,e_{1}) -homomorphism with |V_{i}\backslash A|-|\phi^{-1}(i)|\geq\zeta|V_{i}\backslash A| for i\in[t] . We now construct the embedding \psi from T to G as following. At first, embed the root vertex r such that \psi(r)=v^{*} . Next we embed all edges in one time according to the breadth-first manner order. In this process, once we embed a vertex, then we remove this vertex from its cluster and update all V_{i} . Recall that in homomorphism \phi we use at most (1-\zeta)|V_{i}\backslash A| vertices for each cluster V_{i} with i\in[s] . So |V_{i}| for i\in[t] always larger than \zeta\cdot\theta\cdot|V_{i}|>\varepsilon|V_{i}| . Throughout, we will keep the dense property: for every vertex v\in V(T) , every edge e with v\in e and \phi(e)=\phi(v){i_{1}}{i_{2}}\dots i_{k-1} , \psi(v) is d/4 -dense into \{V_{i_{1}},V_{i_{2}},\dots,V_{i_{k-1}}\} . Since \phi is (T,R,1,e_{1}) -homomorphism and for all edges e with r\in e , \phi(e)=e_{1} . In particular, for the root vertex r , \psi(r)=v^{*}\in V_{1} and v^{*} is d/2 -dense into \{V_{2},\dots,V_{k}\} . Hence \psi(v^{*})=r satisfies the dense property. For other vertices except r , there are at most \Delta (k-1) -tuples \{V_{i_{1}},V_{i_{2}},\dots,V_{i_{k-1}}\} such that there exists an edge e with v\in e and \phi(e)=\phi(v){i_{1}}{i_{2}}\dots i_{k-1} . Assume that we aim to embed an edge a_{1}\dots a_{k} , where a_{1} has been embedded. Suppose that V_{\phi(a_{i})}=W_{i} for i\in[k] . Let m=|V_{i}| for i\in[k] . Since a_{1} is d/4 -dense into \{W_{2},\dots,W_{k-1}\} and |W_{2}|,|W_{3}|,\dots,|W_{k}|\geq\zeta m\geq\sqrt{\varepsilon}m , apply Lemma 5.3 to obtain y^{2},y^{3},\dots,y^{k} satisfying the dense property. Thus, we can embed all other vertices in T . ∎ 6.3 Complete embedding We are ready to prove Theorem 4.6 . Proof of Theorem 4.6 . Let 1/n\ll 1/t\ll 1/r\ll\varepsilon\ll\theta\ll\zeta\ll\alpha\ll\beta\ll\eta\ll d\ll\gamma\ll 1/\Delta. Let G be a k -graph on n vertices with \overline{\delta_{\ell}}(G)\geq\delta_{k,\ell}^{R}+\gamma . Let \mathcal{Q} be a \varepsilon -regular partition of G and R be the (\mathcal{Q},\varepsilon,d) -regular reduced graph. Let T be a rooted k -loose tree on n vertices. Step 0: setting up. Let x be a vertex in T such that \eta n/\Delta\leq|V(T(x))|\leq\eta n , which exists by a breadth-first search. Let T_{x}=T(x) and T^{\prime}=T\backslash(T_{x}\backslash x) be subtrees rooted at x . By adjusting \eta slightly, we may assume that \displaystyle|V(T_{x})|=\eta n. Let T^{\prime\prime} be a k -loose tree rooted at x such that T^{\prime\prime}\subset T and \displaystyle|V(T^{\prime})|-|V(T^{\prime\prime})|=(k-1)\alpha n. (We can obtain T^{\prime\prime} from T^{\prime} by deleting leaf edge \alpha n times.) By Lemma 5.2 , there exists a spanning subgraph R^{\prime} of the reduced graph R with \overline{\delta}_{\ell}^{\alpha}(R^{\prime})\geq\delta_{k,\ell}^{R}+\gamma/2. Let R^{*} be a spanning \eta -robust subgraph of R^{\prime}\subseteq R . Let e_{1},\dots,e_{|E(R^{*})|} be an enumeration of edges in R^{*} satisfying (R2) . Without loss of generality, assume the first edge be e_{1}=1\dots k . By Lemma 6.8 with (\alpha,T)=((k-1)\alpha,T^{\prime\prime}) , we obtain a vertex v^{*}\in V_{1} such that the following holds. ( \ast ) Let A\subseteq V(G) with |A|\leq\eta n , |V_{i}\backslash A|\geq\theta|V_{i}| for i\in[t] and A\cap V_{i}=\emptyset for i\in[k] . Suppose that \phi is a (T^{\prime\prime},R,1,e_{1}) -homomorphism \phi with |V_{i}\backslash A|-|\phi^{-1}(i)|\geq\zeta|V_{i}\backslash A| for i\in[t] . Then there exists an embedding \psi from T^{\prime\prime} to G\setminus A such that \psi(r)=v^{\ast} and, for any v\in V(T) , \psi(v)\in V_{\phi(v)} . Step 1: find absorbers immersed by T_{x} . Let F\subseteq V(G) be such that V_{1},\dots,V_{k}\subseteq F and, for i\in[k+1,t] , |F\cap V_{i}|=\theta|V_{i}| . Note that |F|\leq\sum_{1\leq i\leq k}|V_{i}|+t\theta(n/t)\leq\zeta n . By Proposition 2.1 and ( 4.1 ), we have \displaystyle\overline{\delta}_{1}(G),\overline{\delta}_{1}(G\setminus(F\setminus x))\geq 1/2+\gamma/2. By Lemma 6.4 , there is a set \mathcal{A}\subseteq A_{\Delta}(F) of at most \beta n pairwise vertex-disjoint \Delta -absorbing tuples such that for every ordered tuple (w_{1},\dots,w_{k}) in V(G) , we have \displaystyle|A_{\Delta}(w_{1},\dots,w_{k},F)\cap\mathcal{A}|\geq\alpha n. Note that |V(\mathcal{A})|\leq k^{2}\Delta|\mathcal{A}|\leq k^{2}\Delta\beta n . By Lemma 6.5 with (G,T)=(G\setminus(F\setminus x),T_{x}) , we obtain an embedding \psi_{1} from T_{x} into G such that \mathcal{A} is immersed by \psi_{1} , \psi_{1}(x)=v^{*}\in V_{1} and, by setting A=\psi_{1}^{-1}(T_{x}\setminus x) , we have \displaystyle|V_{i}\backslash A|\geq|(F\setminus x)\cap V_{i}|=\begin{cases}|V_{i}|&\text{if $i\in[k]$,}\\ \theta|V_{i}|&\text{if $i\in[k+1,t]$.}\\ \end{cases} Step 2: extend \psi_{1} to embedding of T^{\prime} . Define a vertex weighted function \omega:[t]\rightarrow[\theta,1] such that, for i\in[t] , if i is non-isolated in R^{*} , then set \displaystyle\omega(i)=\frac{|V_{i}\backslash A|}{|V_{i}|}\geq\theta and set \omega(i)=0 otherwise. Recall that R^{*} is \eta -robust. By Lemma 6.6 with (v_{1},T,\alpha)=(1,T^{\prime\prime},\alpha) , there exists a (T^{\prime\prime},R^{*},1,e_{1}) -homomorphism \phi such that, for all i\in[t] , |\phi^{-1}(i)|\leq(1-\zeta)\omega(i)|V_{i}| . Together with ( ∗ ) ‣ 6.3 , we obtain an embedding \psi_{2} of T^{\prime\prime} to G\setminus A such that \psi_{2}(x)=v^{\ast} . Step 3: extend to an embedding of T . Note that \psi_{1}\cup\psi_{2} is an embedding of T_{x}\cup T^{\prime\prime} to G , which immerses \mathcal{A} . Note that |V(T)\setminus V(T_{x}\cup T^{\prime\prime})|=|V(T^{\prime})|-|V(T^{\prime\prime})|=(k-1)\alpha n . Then by Lemma 6.3 with (p,T,T^{*})=(\alpha n,T_{x}\cup T^{\prime\prime},T) , we obtain an embedding of T to G . ∎ 7 Robust spanning subgraph construction In this section, we give the construction of the \eta -robust spanning subgraph in the \alpha -perturbed k -graph. Recall the definition of shadow graph \partial_{j}(G) and \partial_{j}(A) in Section 2.1 . Definition 7.1 . Let G be a k -graph on V and A\in E(\partial_{k-2}(G)) . Set C_{A}(G) be the induced graph of largest component in L_{G}(A) . In our setting, L_{G}(A) is a 2 -graph and C_{A}(G) will be uniquely defined. If G is clear from the context, then we use C_{A} instead of C_{A}(G) . Let E_{A}=\{A\cup uv~|~uv\in E(C_{A})\text{ and }A\in E(\partial_{k-2}(G))\} . We define a spanning subgraph G^{*} of G with edge set E(G^{*})=\bigcup_{A\in\partial_{k-2}(G)}E_{A} . For 0\leq s\leq(k-2) and A\in E(\partial_{s}(G)) , let \displaystyle E_{A}=\bigcup_{A\cup B\in E(\partial_{k-2}(G))}E_{A\cup B}=\bigcup_{A\subseteq A^{\prime}\in E(\partial_{k-2}(G))}E_{A^{\prime}}. Hence E(G^{*})=E_{\emptyset} . By the above definition, we can imply a proposition about link graphs. Proposition 7.2 . Let G be a k -graph and B\in E(\partial_{j}(G)) with j\leq k-4 . Then (L_{G}(B))^{*}\subseteq L_{G^{*}}(B) Proof. Let e be an edge in (L_{G}(B))^{*} , then e\in E_{A} for some A\in E(\partial_{k-2-j}(B)) . It implies that e\backslash A\in E(C_{A}(L_{G}(B))) by Definition 7.1 and e\backslash A\in C_{A\cup B}(G) . Since |A\cup B|=k-2 , we have e\cup B\in E(C_{A\cup B}(G)) , implying that e\in L_{G^{*}}(B) . Hence (L_{G}(B))^{*}\subseteq L_{G^{*}}(B) . ∎ The next lemma states that G^{*} is \eta -robust. Recall the definition of \eta -robust in Definition 4.5 . Lemma 7.3 . Let 1/n\ll\alpha\ll\eta\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Then its spanning subgraph G^{*} is \eta -robust. This will become immediately by Theorems 8.1 , 9.1 and 10.1 . Our main result, Theorem 1.4 immediately follows from Theorem 4.6 and Lemma 7.3 . Proof of Theorem 1.4 . By Theorem 4.6 , it is sufficient to show that \delta_{k,k-2}^{R}\leq 1/2 . Let 1/n\ll\eta\ll\gamma . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Let G^{*} be the corresponding spanning graph of G as in Definition 7.1 . By Lemma 7.3 . G^{*} is \eta -robust. Hence, \delta_{k,k-2}^{R}\leq 1/2 . ∎ 8 Robust fractional matching In this section, our aim is to prove Lemma 8.1 , the existence of robust fractional matching for G^{*} . Lemma 8.1 . Let 1/n\ll\alpha\ll\eta\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Suppose that \omega:V(G)\rightarrow[0,1] with \sum_{v\in V(G)}\omega(v)\geq(1-\eta)n and \omega(v)=0 for all isolated vertices v\in V(G) . Then there exists a perfect \omega -fractional matching \omega^{\ast} on G^{*} . We need the following well-known results. Theorem 8.2 (Erdős and Gallai [ 5 ] ) . Any graph G on N vertices with \displaystyle e(G)>\max\{\binom{2k-1}{2},\binom{k-1}{2}+(k-1)(N-k+1)\} admits a matching of size k . Theorem 8.3 (Karamata [ 14 ] ) . Let \mathbf{a}=(a_{i})_{i=1}^{n} and \mathbf{b}=(b_{i})_{i=1}^{n} be (finite) sequences of real numbers from an interval (\alpha,\beta) . Let f:(\alpha,\beta)\rightarrow\mathbf{R} be a convex function. If the sequence \mathbf{a} majorizes \mathbf{b} , that is \sum_{i=1}^{j}a_{i}\geq\sum_{i=1}^{j}b_{i} for j\in[n] , then the following holds \sum_{i=1}^{n}f(a_{i})\geq\sum_{i=1}^{n}f(b_{i}). Now we state a key structural lemma about C_{A} for all A\in E(\partial_{k-2}(G)) . Lemma 8.4 . Let 1/n\ll\gamma\ll 1 . Let G_{1} , G_{2} and G_{3} be 2 -graphs on vertex set V with |V|=n and e(G_{1}),e(G_{2}),e(G_{3})>(1/2+\gamma)\binom{n}{2} . Let C_{1} , C_{2} and C_{3} be the induced subgraphs of the largest connected components in G_{1} , G_{2} and G_{3} , respectively. Then the following statements hold for all i\in[3] (M1) |V(C_{i})|>(1/2+\gamma)n and e(C_{i})>(1/2+\gamma)\binom{n}{2}-\binom{n-|V(C_{i})|}{2}\geq(1/4+\gamma)\binom{n}{2} ; (M2) C_{i} contains a matching of size \left(1/4+\gamma/3\right)n ; (M3) C_{i} contains a triangle; (M4) there exist distinct i_{1},i_{2}\in[3] such that E(C_{i_{1}})\cap E(C_{i_{2}})\neq\emptyset . Proof. Suppose for a contradiction that G_{i} has no component with at least (\frac{1}{2}+\gamma)n vertices. Then we could write V=V_{1}\cup V_{2}\cup\dots\cup V_{s} , such that V_{j} are disjoint connected components of G_{i} with |V_{j}|\leq(1/2+\gamma)n . Let f(x)=x(x-1)/2 for x\geq 0 . So f is a convex function. Note that ((1/2+\gamma)n,(1/2-\gamma)n,0,\dots,0) majorizes the sequence of components size (|V_{1}|,\dots,|V_{s}|) . By Theorem 8.3 , e(G_{i})\leq\sum_{j\in[s]}\binom{|V_{j}|}{2}\leq\binom{(\frac{1}{2}+\gamma)n}{2}+\binom{(\frac{1}{2}-\gamma)n}{2}\leq\left(\frac{1}{2}+\gamma\right)\binom{n}{2}, a contradiction. Hence, |V(C_{i})|>(1/2+\gamma)\binom{n}{2} . Moreover, e(C_{i})=e(G_{i})-e(G_{i}\backslash C_{i})>\left(\frac{1}{2}+\gamma\right)\binom{n}{2}-\binom{\left(\frac{1}{2}-\gamma\right)n}{2}\geq\left(\frac{1}{4}+\gamma\right)\binom{n}{2}. Thus, (M1) holds. Let |V(C_{i})|=(1-x_{i})n . Note that x_{i}\leq\left(1/2-\gamma\right) and there are at most \binom{x_{i}n}{2} edges not in C_{i} . Hence we have \displaystyle e(C_{i}) \displaystyle\geq\left(\frac{1}{2}+\gamma\right)\binom{n}{2}-\binom{x_{i}n}{2}\geq\left(\frac{1}{2}+\gamma-x_{i}^{2}\right)\frac{n^{2}}{2} \displaystyle= \displaystyle\left(\frac{1}{4}+\gamma\right)^{2}\frac{n^{2}}{2}+\left(\frac{3}{16}-x_{i}^{2}+\frac{\gamma}{2}-\frac{\gamma^{2}}{4}\right)\frac{n^{2}}{2}\geq\binom{(\frac{1}{4}+\gamma)n}{2}+\left(\frac{3}{16}-\frac{x_{i}}{2}+\frac{\gamma}{4}\right)\frac{n^{2}}{2} \displaystyle> \displaystyle\binom{(\frac{1}{4}+\frac{\gamma}{3})n}{2}+\left((\frac{1}{4}+\frac{\gamma}{3})n-1\right)\left((1-x_{i})n-(\frac{1}{4}+\frac{\gamma}{3})n+1\right), where the second inequality holds as x_{i}\leq 1/2 . Also, e(C_{i})>(1/4+\gamma)\binom{n}{2}\geq\binom{(2(1/4+\gamma/3)n}{2} . By Theorem 8.2 , there exists a matching in G_{i} of size (1/4+\gamma/3)n implying (M2) . Note that e(C_{i})\geq\left(\frac{1}{2}+\gamma\right)\binom{n}{2}-\binom{x_{i}n}{2}>\frac{(1-x_{i})^{2}n^{2}}{4}=\frac{|V(C_{i})|^{2}}{4}. Thus, (M3) holds by Mantel’s Theorem. Suppose that (M4) is false, so E(C_{1}),E(C_{2}),E(C_{3}) are pairwise disjoint. Without loss of generality, assume that x_{1}\leq x_{2}\leq x_{3} . By (M1) , \displaystyle e(C_{1})+e(C_{2})+e(C_{3}) \displaystyle>\sum_{i\in[3]}\left(\left(\frac{1}{2}+\gamma\right)\binom{n}{2}-\binom{x_{i}n}{2}\right)\geq\left(\frac{3}{2}+3\gamma-x_{1}^{2}-x_{2}^{2}-x_{3}^{2}\right)\binom{n}{2}. (8.1) On the other hand, since there is no common edge, the inclusion-exclusion principle implies that, \displaystyle e(C_{1})+e(C_{2})+e(C_{3}) \displaystyle\leq\sum_{i\in[3]}\binom{|V(C_{i})|}{2}-\sum_{i,j\in[3],i\neq j}\binom{|V(C_{i}\cap C_{j})|}{2}+\binom{|V(C_{1}\cap C_{2}\cap C_{3})|}{2} \displaystyle\leq\sum_{i\in[3]}\binom{|V(C_{i})|}{2}-\sum_{i,j\in[3],i\neq j}\binom{|V(C_{i}\cap C_{j})|}{2}+\binom{|V(C_{1}\cap C_{2})|}{2} \displaystyle=\sum_{i\in[3]}\binom{|V(C_{i})|}{2}-\binom{|V(C_{1}\cap C_{3})|}{2}-\binom{|V(C_{2}\cap C_{3})|}{2} \displaystyle\leq\binom{n}{2}\left(\sum_{i\in[3]}(1-x_{i})^{2}-(1-x_{1}-x_{2})^{2}-(1-x_{1}-x_{3})^{2}+\gamma\right) \displaystyle=\binom{n}{2}\left(1+2x_{1}-x_{1}^{2}-2x_{1}x_{2}-2x_{1}x_{3}+\gamma\right). Together with ( 8.1 ) and the fact that x_{1}\leq x_{2}\leq x_{3}<1/2 , we have \displaystyle 0 \displaystyle<\left(1+2x_{1}-x_{1}^{2}-2x_{1}x_{2}-2x_{1}x_{3}+\gamma\right)-\left(\frac{3}{2}+3\gamma-x_{1}^{2}-x_{2}^{2}-x_{3}^{2}\right) \displaystyle=(x_{2}-x_{1})^{2}+(x_{3}-x_{1})^{2}-\frac{(1-2x_{1})^{2}}{2}\leq 2(x_{3}-x_{1})^{2}-\frac{(1-2x_{1})^{2}}{2} \displaystyle=\frac{1}{2}(1-2x_{3})(4x_{1}-2x_{3}-1)\leq-\frac{1}{2}(1-2x_{3})^{2}<0, a contradiction. Hence (M4) holds. ∎ By this structural lemma, we immediately deduce that there exists a fractional matching with size n/4 in C_{A} for all A\in E(\partial_{k-2}(G)) . Proposition 8.5 . Let 1/n\ll\alpha\ll\eta\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma and \omega:V(G)\rightarrow[0,1] with \sum_{v\in V(G)}\omega(v)\geq(1-\eta)n and \omega(v)=0 for all isolated vertices v\in V(G) . Let A\in E(\partial_{k-2}(G)) . Then there is an \omega -fractional matching with size at least n/4 in C_{A} . Proof. By Lemma 8.4 (M2) , there exists a matching M of size (1/4+\gamma/3)n in C_{A} . Define a fractional matching \omega^{*}:E(C_{A})\rightarrow[0,1] such that \omega^{*}(e)=\min_{v\in e}\{\omega(v)\}\text{ for all $e\in E(M)$}. So \omega^{*} is a \omega -fractional matching with size \sum_{e\in E(C_{A})}\omega^{*}(e)\geq\left(\frac{1}{4}+\frac{\gamma}{3}\right)n-2\eta n\geq\frac{1}{4}n. ∎ To prove the existence of perfect \omega -fractional matching in G^{*} , we will use the following result, which is a consequence of linear programming. Proposition 8.6 ( [ 21 , Proposition 2.11] ) . Let G be a k -graph and a weight function \omega:V(G)\rightarrow[0,1] with \omega(v)=0 for isolated vertices. Suppose that there exists an m\leq(\sum_{v\in V(G)}\omega(v))/k such that for every non-isolated vertex v\in V(G) , the link graph L_{G}(\{v\}) has an \omega -fractional matching with size m . Then G has an \omega -fractional matching with size m . We now prove Lemma 8.1 . Proof of Lemma 8.1 . Let m=\sum_{v\in V(G)}\omega(v) . Let 0\leq j\leq k-2 and S\in E(\partial_{j}(G)) . We claim that in L_{G^{*}}(S) , there exists an \omega -fractional matching with size m/k . We prove this claim by induction on |S| from k-2 to 0 . First if |S|=k-2 , then our claim follows from Proposition 8.5 . For j=|S|0 . By Definition 2.3 , the degree of S in \overline{\partial_{j+1}(G)} is at most \alpha n . Then |I_{S}|\leq\alpha n and \frac{\sum_{v\in V(G^{*})\backslash I_{S}}\omega(v)}{k-j}=\frac{m-\sum_{v\in I_{S}}w(v)}{k-j}\geq\frac{m-\alpha n}{k-j}\geq\frac{m}{k}. The above inequality follows m\geq(1-\eta)n . If S=\emptyset , then \sum_{v\in V(G)\backslash I_{S}}\omega(v)/k=m/k . By Proposition 8.6 with (H,k)=(L_{G^{*}}(S)\backslash I_{S},k-j) , there exists an \omega -fractional matching with size m/k in L_{G^{*}}(S) . Thus, our claim holds and the lemma follows S=\emptyset case. ∎ 9 Reachable Lemma Let C\in\mathbb{N} , let G be a k -graph and e=u_{1}\dots u_{k}\in E(G) . Recall that e is C -reachable from u if for any rooted k -loose tree T at r , there exists a homomorphism \phi from T to G such that \phi(r)=u and \phi(v)\in e for v with \text{dist}(r,v)>C . Moreover, for an edge e^{\prime}\in E(G) , if e is C -reachable from all u\in e^{\prime} , then we say e is C -reachable from e^{\prime} . Recall the definition of G^{*} in Definition 7.1 . Our aim in this section is to prove the existence of the edge enumeration of E_{\emptyset} with tree reachable proposition. Lemma 9.1 (Reachable lemma) . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Then there is an enumeration e_{1},\dots,e_{m} of all edges in G^{*} such that e_{j} is n^{4k} -reachable from e_{i} for i\leq j\leq m . In the next subsection, we give an overview of a key step in our proof and the definition of (\mathcal{A},\mathcal{K}) -reachable. In Section 9.2 , we list some properties about reachability. In Section 9.3 , we give an auxiliary colouring method of shadow graphs to partition edges. In Section 9.4 , we show a key lemma for proving Lemma 9.1 . In Section 9.5 , we prove Lemma 9.1 . 9.1 Sketch of Proof of Lemma 9.1 and (\mathcal{A},\mathcal{K}) -reachable We give an overview of one step in the proof of Lemma 9.1 when k is even. Consider A\in E(\partial_{k-2}(G)) . Note that all edges in E_{A} are reachable from themselves since E_{A} is tight connected. This leads to an equivalent relationship on E(\partial_{k-2}(G)) such that A\sim A^{\prime} if and only if E_{A}\cup E_{A^{\prime}} are reachable within themselves. This can be represented by a colouring of E(\partial_{k-2}(G)) . When k=4 , this is just an edge-colouring of \delta_{2}(G) . It turns out that this is Gallai locally 2 -edge colouring. By analysing monochromatic components, we obtain the desired enumeration of E_{\emptyset} . In particular, we can partition E(\partial_{k-2}(G)) into those A such that each edge in E_{A} is reachable from all edges in E_{\emptyset} . Such edges can be placed at the end of the enumeration of E_{\emptyset} . We call edges in these E_{A} “good” otherwise “bad”. It turns out that the set of bad edges are reachable themselves. We now discuss the case when k=6 . Consider A\in E(\partial_{k-4}(G))=E(\partial_{2}(G)) . Then E_{A} can be viewed as a 4 -graph. By the discussion above, we can partite E_{A} into A -good or A -bad edges. This gives us an ordering within E_{A} . We would like to extend these into a total ordering of E_{\emptyset} . This can be done via defining a similar colouring on E(\partial_{2}(G)) as in the case when k=4 . Similarly, we extend this argument for larger k . Namely, we first look at E_{A} with |A|=k-2 , then |A|=k-6 and so on. In order to track the edges as in the overview, we need the following notations. Intuitively, the non- A -label edges are the A -good edges, while the A -label edges are the A -bad. For technical reason, we also define K_{A} which is a 2 -graph, more importantly, K_{A}\cap E(\partial_{2}(e))\neq\emptyset~~~~\text{for all $A$-label edge }e. which is needed to help us define A -label edges formally. Let G be a k -graph on vertex set V . Let \partial_{\mod 2}(G)=\bigcup_{s\equiv k\mod 2,s1/2 . Proposition 9.5 . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)>1/2+\gamma . Then G is (E(\partial_{k-2}(G)),\mathcal{K}) -reachable. Proof. For all A\in E(\partial_{k-2}(G)) , we set K_{A} to be \partial_{2}(A) after removing all isolated vertices. So (A2) holds. Note that (A1) holds trivially. By Definition 2.3 , |K_{A}|\geq(1/2-\alpha)n, so (A3) holds. Since |A|=k-2 and \overline{\delta}^{\alpha}_{k-2}(G)>1/2+\gamma , then by Definition 7.1 , E_{A} is tight connected. Thus, (A4) follows Proposition 9.4 (v) . Hence, G is (E(\partial_{k-2}(G),\mathcal{K}) -reachable. ∎ Then from Definition 9.2 , we can imply following properties about (\mathcal{A},\mathcal{K}) -reachable. Proposition 9.6 . Let 1/n\ll\alpha\ll 1/k\leq 1/4 . Let G be an \alpha -perturbed k -graph on n vertices. Suppose that G is (\mathcal{A},\mathcal{K}) -reachable. Then the following hold for A,A_{1},A_{2}\in\mathcal{A} (i) E_{A}^{+}\cup E_{A}^{-}=E_{A} ; (ii) if |A|6\alpha n. By Proposition 2.4 (L2) , there exists an edge x_{i^{*}}y_{i^{*}}\in E(K_{B_{1}})\cap E(K_{B_{2}}) as we desire. ∎ In addition, the following lemma states that if there is no two label edges for two sets which are reachable, then the corresponding K_{A} of these two sets in \mathcal{K} will intersect in a large size. Lemma 9.8 . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Suppose that G is (\mathcal{A},\mathcal{K}) -reachable. Let A\subseteq V with |A|<(k-4) . Let z_{1},z_{2}\in V\backslash A be such that A\cup z_{1},A\cup z_{2}\in\mathcal{A} . Suppose that for every e\in E_{A\cup z_{1}}^{+} and every e^{\prime}\in E^{+}_{A\cup z_{2}} , e is not n^{3k-2|A|-2} -reachable from e^{\prime} or e^{\prime} is not n^{3k-2|A|-2} -reachable from e . Then for any (A\cup z_{1},A\cup z_{2},i) -common set C with 2i\leq k-|A|-5 , we have |V(K_{A\cup z_{1}\cup C})\cap V(K_{A\cup z_{2}\cup C})|>n/2. Proof. Let A_{i}=A\cup z_{i}\cup C and K_{i}=K_{A_{i}} for i\in[2] . Note that |A_{i}|=|A|+1+2i\leq k-4. Suppose to the contrary that |V(K_{1})\cap V(K_{2})|\leq n/2 . We claim the following hold (k {}_{1}) |V(K_{1})\cap V(K_{2})|>3\alpha n and E(K_{1})\cap E(K_{2})\neq\emptyset ; (k {}_{2}) |V(K_{i})|<(1-3\alpha)n and E(K_{i})\neq E(\partial_{2}(A)) ; (k {}_{3}) for \{i,j\}=[2] , |V(K_{i})\backslash V(K_{j})|>3\alpha n. By (A3) , we have |V(K_{1})\cap V(K_{2})|\geq|V(K_{1})|+|V(K_{2})|-n\geq 3\alpha n. By Proposition 2.4 (L2) , E(K_{1})\cap E(K_{2})\neq\emptyset . Thus (k ) 1 holds. If |K_{1}|\geq(1-3\alpha)n , then |V(K_{1})\cap V(K_{2})|\geq|V(K_{1})|+|V(K_{2})|-n>n/2, a contradiction and similarly we have |V(K_{2})|<(1-3\alpha)n . Hence (k ) 2 holds. for \{i,j\}=[2] , \displaystyle|V(K_{i})\backslash V(K_{j})|\geq|V(K_{i})|-|V(K_{i})\cap V(K_{j})|\overset{\ref{Reach3}}{\geq}(1/2+3\alpha)n-n/2>3\alpha n. This implies (k ) 3 . Let v_{1}v_{2}\in E(K_{1})\cap E(K_{2}) which exists by (k ) 1 . Since K_{1} is an induced subgraph of \partial_{2}(A_{1}) without isolated vertices and by Definition 2.3 , the relative degree of v_{1} in \overline{\partial_{2}(A_{1})} is at most \alpha . Then by (k ) 3 , there exists u_{2}\in V(K_{2})\backslash V(K_{1}) such that v_{1}u_{2}\in E(\partial_{2}(A_{1})) . By Proposition 9.7 , there exists an (A_{1}\cup v_{1}v_{2},A_{2}\cup v_{1}v_{2},\frac{k-(|A^{*}|+|C|+1)-2-2}{2}) -common set D . Then consider the following three (k-2) -subsets B_{1}=A_{1}\cup v_{1}v_{2}\cup D=A\cup C\cup D\cup z_{1}v_{1}v_{2}, B_{2}=A_{2}\cup v_{1}v_{2}\cup D=A\cup C\cup D\cup z_{2}v_{1}v_{2}, B_{3}=A_{1}\cup v_{1}u_{2}\cup D=A\cup C\cup D\cup z_{1}v_{1}u_{2}. We have (R {}_{1}) E_{B_{1}}\subseteq E^{+}_{A_{1}}=E^{+}_{A\cup z_{1}} (by Proposition 9.6 (ii) and v_{1}v_{2}\in E(K_{1})\cap E(K_{2}) ); (R {}_{2}) E_{B_{2}}\subseteq E^{+}_{A_{2}}=E^{+}_{A\cup z_{2}} (by Proposition 9.6 (ii) and v_{1}v_{2}\in E(K_{1})\cap E(K_{2}) ); (R {}_{3}) E_{B_{3}}\subseteq E^{-}_{A_{1}} (as u_{2}\notin V(K_{1}) ). By Lemma 8.4 (M4) , there exist i,j\in[3] such that E(C_{B_{i}})\cap E(C_{B_{j}})\neq\emptyset . Next we discuss the following cases: Case 1: E(C_{B_{1}})\cap E(C_{B_{2}})\neq\emptyset . Let y_{1}y_{2}\in E(C_{B_{1}})\cap E(C_{B_{3}}) , e_{1}=B_{1}\cup y_{1}y_{2} , e_{2}=B_{2}\cup y_{1}y_{2} . Then |e_{1}\cap e_{2}|=k-|B_{1}\backslash B_{2}|=k-1. Hence e_{1}\in E_{A_{1}}^{+} is 1 -reachable from e_{2}\in E_{A_{2}}^{+} by Proposition 9.4 (iv) , and vice versa. This is a contradiction. Case 2: E(C_{B_{1}})\cap E(C_{B_{3}})\neq\emptyset . Let y_{1}y_{2}\in E(C_{B_{1}})\cap E(C_{B_{3}}) , e_{1}=B_{1}\cup y_{1}y_{2} and e_{3}=B_{3}\cup y_{1}y_{2} . Note that |e_{1}\cap e_{3}|=k-|B_{1}\backslash B_{3}|=k-1. Hence e_{1}\in E_{A_{1}}^{+} is 1 -reachable from e_{3} by Proposition 9.4 (iv) and vice versa. By Proposition 9.6 (vi) , E(K_{1})=E(K_{A_{1}})=E(\partial_{2}(A)) . This contradicts with (k ) 2 . Case 3: E(C_{B_{2}})\cap E(C_{B_{3}})\neq\emptyset . Let y_{1}y_{2}\in E(C_{B_{2}})\cap E(C_{B_{3}}) . Let e_{2}=B_{2}\cup y_{1}y_{2} and e_{3}=B_{3}\cup y_{1}y_{2} . Next, we claim that e_{2} is 2n^{3k-2|A_{2}|} -reachable from e_{3} . Note that e_{3}\backslash e_{2}=B_{3}\backslash B_{2}=\{z_{1},u_{2}\}. By Proposition 9.4 (iii) and (i) , it suffices to show that e_{2} is (2n^{3k-2|A_{2}|}-1) -reachable from u_{2} . By u_{2}\in V(K_{2}) and Proposition 9.6 (ii) , there exists an edge f\in E_{A_{2}}^{+} containing u_{2} . Since e_{2}\in E_{A_{2}}^{+} , by Definition 9.2 (A5)(A5.2) and Proposition 9.4 (i) , e_{2} is n^{3k-2|A_{2}|} -reachable from f and so from u_{2} . Hence, e_{2} is 2n^{3k-2|A_{2}|} -reachable from e_{3} . Meanwhile, e_{3}\in E^{-}_{A_{1}} by (R ) 3 . By Proposition 9.6 (iv) , e_{3} is n^{3k-2|A_{1}|} -reachable from all edges e^{\prime}\in E_{\emptyset} . By Proposition 9.4 (ii) , e_{2} is 3n^{3k-2|A_{2}|} -reachable from all edges in E_{\emptyset} . Since E(K_{2})\neq E(\partial_{2}(A_{2})) by (k ) 2 , there is e^{\prime\prime}\in E_{A_{2}}^{-} . So e_{2}\in E_{A_{2}}^{+} is 3n^{3k-2|A_{2}|} -reachable from e^{\prime\prime}\in E_{A_{2}}^{-} . This contradicts with Proposition 9.6 (vi) and (k ) 2 . ∎ 9.3 Auxiliary edge-colouring Recall that \partial_{\mod 2}(G)=\bigcup_{s\equiv k\mod 2,sn/2. Since A is the maximal set of \partial_{\mod 2}(G)\backslash\mathcal{A} , we have A_{1},A_{2},A_{3}\in\mathcal{A} . By (A3) , |V(K_{A_{3}\cup X_{j^{*}}})|\geq(1/2+3\alpha)n . Thus we have \displaystyle|\bigcap_{i\in[3]}V(K_{A_{i}\cup X_{j^{*}}})|\geq|V(K_{A_{1}\cup X_{j^{*}}})\cap V(K_{A_{2}\cup X_{j^{*}}})|+|V(K_{A_{3}\cup X_{j^{*}}})|-n>3\alpha n. By Proposition 2.4 (L2) , there exists x_{j^{*}+1}y_{j^{*}+1}\in\bigcap_{i\in[3]}E(K_{A_{i}\cup X_{j^{*}}}) . Let C=\{x_{1},y_{1}\dots,x_{m},y_{m}\} as required. ∎ For i\in[3] , let B_{i}=A_{i}\cup C . Note that B_{i}\in E(\partial_{k-2}(G)) for i\in[3] . By Lemma 8.4 (M4) , there exist B_{i_{1}} and B_{i_{2}} such that E(C_{B_{i_{1}}})\cap E(C_{B_{i_{2}}})\neq\emptyset for distinct i_{1},i_{2}\in[3] . Let u_{1}u_{2}\in E(C_{B_{i_{1}}})\cap E(C_{B_{i_{2}}}) . Let f_{j}=B_{i_{j}}\cup u_{1}u_{2} for j\in[2] . Then f_{j}\in E_{B_{i_{j}}}\subseteq E^{+}_{A_{i_{j}}}=E^{+}_{A\cup wz_{i_{j}}} . Note that \displaystyle|f_{1}\cap f_{2}|=|(B_{i_{1}}\cup u_{1}u_{2})\cap(B_{i_{2}}\cup u_{1}u_{2})|=|A\cup(wz_{i_{1}}\cap wz_{i_{2}})\cup C\cup u_{1}u_{2}|=k-1. Then by Proposition 9.4 (iv) , f_{i} is 1 -reachable from f_{j} for \{i,j\}=[2] . However, f_{j}\in E^{+}_{A\cup wz_{i_{j}}} for j\in[2] . This contradicts the fact that \phi_{A}(wz_{i_{1}})\neq\phi_{A}(wz_{i_{2}}) . Hence, \phi_{A} is locally 2 -edge-coloured. Suppose that \phi_{A} is not Gallai-coloured. Then there exists a rainbow triangle u_{1}u_{2}u_{3} . We replace ( wz_{1} , wz_{2} , wz_{3} ) by (u_{1}u_{2},u_{1}u_{3},u_{2}u_{3}) in the above argument. We can deduce that there is no rainbow triangle in \phi_{A} . ∎ Then the following lemma shows that if H is almost complete with a Gallai locally 2 -edge-colouring, we can describe its structure. Lemma 9.13 . Let 1/n\ll\alpha\ll 1 and H be a 2 -graph on n vertices with \delta(H)\geq(1-\alpha)n . Suppose that H is Gallai locally 2 -edge-coloured by \phi with monochromatic components H_{1},\dots,H_{m} with |V(H_{1})|\geq\dots\geq|V(H_{m})| . Then the following hold (g 1 ) if H_{1} spans H , then H_{2},\dots,H_{m} are vertex-disjoint and |V(H_{1})|=n ; (g 2 ) if H_{1} does not span H , then |V(H_{2})|\geq(1-2\alpha)n and H_{1}\cup H_{2} spans H ; (g 3 ) |V(H_{1})|\geq(1-2\alpha)n and |V(H_{i})|\leq n/2 for i\in[3,m] . Proof. For each vertex v\in V(H) , let N_{i}(v) be the set of u such that \phi(uv)=i and H_{v}=H[v\cup N(v)] , then Claim 9.14 . There exists a colour j_{v} in H_{v} such that N_{j_{v}}(v)\neq\emptyset and |\{z\in V(H_{v})~|N_{j}(z)\neq\emptyset\}|\geq(1-2\alpha)n. Proof of claim. Suppose the claim is false for some v\in V(H) . Without loss of generality, suppose that \{\phi(vu)~|~u\in N(v)\}=[2] . As \delta(H)\geq(1-\alpha)n , if for every u\in N_{1}(v) with N_{2}(u)\neq\emptyset , then |\{z\in V(H_{v})~|N_{2}(z)\neq\emptyset\}|\geq\deg(v)\geq(1-\alpha)n, a contradiction. Furthermore, let u\in N_{1}(v) with N_{2}(u)=\emptyset . Since there is no rainbow triangle for all w\in N_{2}(v)\cap N(v) , \phi(uw)=1 . Hence \displaystyle|\{u\in N(v)|N_{1}(u)\neq\emptyset\}| \displaystyle\geq|N_{1}(v)|+|N_{2}(v)\cap N(u)| \displaystyle\geq|N_{1}(v)|+(\deg(v)-|N_{1}(v)|)+\deg(u)-n\geq 2\delta(H)-n\geq(1-2\alpha)n, a contradiction. ∎ Next, we claim that there exist i_{1},i_{2} such that j_{v}\in\{i_{1},i_{2}\} for all v\in V(H) . Otherwise, assume that j_{u},j_{v},j_{w} are pairwise distinct. Then |\{z~|N_{j_{v}}(z)\neq\emptyset\}\cap\{z~|N_{j_{u}}(z)\neq\emptyset\}\cap\{z~|N_{j_{w}}(z)\neq\emptyset\}|\geq 3(1-2\alpha)n-2n>0. So there is a vertex z^{\prime} with N_{j_{v}}(z^{\prime}),N_{j_{w}}(z^{\prime}),N_{j_{u}}(z^{\prime})\neq\emptyset . This contradicts with that \phi is locally 2 -edge-coloured. To see (g1) , if H_{1} spans H , then |V(H_{1})|=n . Moreover, after removing edges of H_{1} , every vertex is incident to edges of at most one colour. So the remaining graph are separated monochromatic components. If H_{1} does not span H , then i_{1}\neq i_{2} . By Claim 9.14 , for all v\in V(H) , j_{v}\in\{i_{1},i_{2}\} and so N_{i_{1}}(v)\neq\emptyset or N_{i_{2}}(v)\neq\emptyset . This implies that V(H)=V(H_{i_{1}})\cup V(H_{i_{2}}) and |V(H_{i_{j}})|\geq(1-2\alpha)n for j\in[2] . After removing edges of H_{1}\cup H_{2} , every vertex is incident to edges of at most one colour. So the remaining graph are separated monochromatic components. If |V(H_{i_{3}})|\geq 4\alpha n with i_{3}\neq i_{1},i_{2} , then |V(H_{i_{3}})\cap V(H_{i_{1}})\cap V(H_{i_{2}})|>4\alpha n+(1-2\alpha)n+(1-2\alpha)n-2n\geq 0. So there is a vertex u\in V(H_{i_{3}})\cap V(H_{i_{1}})\cap V(H_{i_{2}}) . It implies that N_{i_{j}}(u)\neq\emptyset for j\in[3] . This contradicts with locally 2 -edge-coloured. Meanwhile, by Claim 9.14 , we have that |V(H_{i_{1}})| and |V(H_{i_{2}})| are larger than (1-2\alpha)n . It indicates that \{i_{1},i_{2}\}=[2] . Thus |V(H_{2})|\geq(1-2\alpha)n and H_{1}\cup H_{2} spans H . Therefore, (g2) holds. For (g3) , if H_{1} spans H , then |V(H_{1})|=n and H_{2},H_{3},\dots,H_{m} are vertex-disjoint. Hence for i\in[3,m] , 2|V(H_{i})|\leq|V(H_{2})|+\dots+|V(H_{m})|\leq n implying V(H_{i})\leq n/2 . If H_{1} does not span H , then |V(H_{1})|\geq(1-2\alpha)n and |V(H_{i})|\leq 4\alpha n\leq n/2 for i\in[3,m] by the argument of (g2) . ∎ Let |A|\leq k-4 and I_{A} be the set of isolated vertices in \partial_{2}(A) . By Definition 2.3 , |V(\partial_{2}(A))\backslash I_{A}|\geq(1-\alpha)n and the minimum degree of V(\partial_{2}(A))\backslash I_{A} is at least (1-\alpha)n . Next by Lemma 9.13 with H=\partial_{2}(A)\backslash I_{A} , we obtain following structural statement for \phi_{A} . Corollary 9.15 . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Suppose that G is (\mathcal{A},\mathcal{K}) -reachable with E(\partial_{k-2}(G))\subseteq\mathcal{A} . Let A be a maximal element of \partial_{\mod 2}(G)\backslash\mathcal{A} . Let \phi_{A} be the edge-colouring of \partial_{2}(A) as defined in Definition 9.9 with colours [m] . Let H_{1},\dots H_{m} be monochromatic components of \phi_{A} such that |V(H_{1})|\geq\dots\geq|V(H_{m})| . Let I_{A} be the set of isolated vertices in \partial_{2}(A) . Then the following hold (c {}_{1}) if H_{1} spans \partial_{2}(A)\backslash I_{A} , then H_{2},\dots,H_{m} are vertex-disjoint and |V(H_{1})|\geq(1-\alpha)n ; (c {}_{2}) if H_{1} does not span \partial_{2}(A)\backslash I_{A} , then |V(H_{2})|\geq(1-3\alpha)n and H_{1}\cup H_{2} spans \partial_{2}(A)\backslash I_{A} ; (c {}_{3}) |V(H_{1})|\geq(1-3\alpha)n and |V(H_{i})|\leq n/2 for i\in[3,m] . Then according to the size of each component, we discuss reachable properties in different way. First, we show that if |V(H_{i})| is near n , then all edges in E(H_{i}) are reachable from all edges in E_{\emptyset} . Lemma 9.16 . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Suppose that G is (\mathcal{A},\mathcal{K}) -reachable with E(\partial_{k-2}(G))\subseteq\mathcal{A} . Let A be a maximal element of \partial_{\mod 2}(G)\backslash\mathcal{A} . Let \phi_{A} be the edge-colouring of \partial_{2}(A) as defined in Definition 9.9 with colours [m] . Suppose that H_{i} is a monochromatic component of \phi_{A} with |V(H_{i})|>(1-3\alpha)n . Then any e\in E_{A\cup u_{1}v_{1}} with u_{1}v_{1}\in E(H_{i}) is n^{3k-2|A|-1} -reachable from every edge in E_{\emptyset} . Proof. It suffices to show that e\in E^{+}_{A\cup u_{1}v_{1}} is n^{3k-2|A|-1} -reachable from all vertices v\in V(G) . First, if v\in V(H_{i}) , then there exists a vertex v^{\prime} such that vv^{\prime}\in E(H_{i}) . Let e^{\prime}\in E^{+}_{A\cup vv^{\prime}} . Then since \phi_{A}(vv^{\prime})=\phi_{A}(u_{1}v_{1}) , by Proposition 9.10 , e^{\prime} is 3n^{3k-2|A|-2} -reachable from e and so from v . Hence we may assume that v\notin V(H_{i}) . Claim 9.17 . There exists an edge e^{\prime}\in E_{\emptyset} such that v\in e^{\prime} and e^{\prime}\backslash v\subseteq V(H_{i}) . Proof of claim. Since |V(H_{i})|\geq(1-3\alpha)n and any S\in E(\partial_{j}(G)) has relative degree at most \alpha in \overline{\partial_{j+1}(G)} for j\in[k-2] , we can iteratively choose u_{2},\dots,u_{k-2}\in V(H_{i}) such that vu_{2}\dots u_{k-2}\in E(\partial_{k-2}(G)) . Let B=vu_{2}\dots u_{k-2} . Since \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma , by Lemma 8.4 (M1) , there exist at least \frac{1}{4}\binom{n}{2} edges in C_{B} . Note that |E(C_{B})\cap\binom{V(H_{i})}{2}|\geq\frac{1}{4}\binom{n}{2}+\binom{(1-3\alpha)n}{2}-\binom{n}{2}>0. Let u_{k-1}u_{k}\in E(C_{B})\cap\binom{V(H_{i})}{2} . So vu_{2}\dots u_{k}\in E_{\emptyset} as desired. ∎ Let e^{\prime} be the edge such that v\in e^{\prime} and e^{\prime}\backslash v\subseteq V(H_{i}) , so e is 3n^{3k-2|A|-2} -reachable from all vertices of e^{\prime} except v . By Proposition 9.4 (iii) , e is n^{3k-2|A|-1} -reachable from e^{\prime} and so from v . ∎ Then we show that edges in small components are also reachable from every edge in E_{\emptyset} . Lemma 9.18 . Let 1/n\ll\alpha\ll\gamma\ll 1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Suppose that G is (\mathcal{A},\mathcal{K}) -reachable with E(\partial_{k-2}(G))\subseteq\mathcal{A} . Let A be a maximal element of \partial_{\mod 2}(G)\backslash\mathcal{A} . Let \phi_{A} be the edge-colouring of \partial_{2}(A) as defined in Definition 9.9 with colours [m] . Suppose that H_{i} is a monochromatic component of \phi_{A} with |V(H_{i})|<(1/2+3\alpha)n for some i\in[m] . Then any e\in E_{A\cup u_{1}v_{1}} with u_{1}v_{1}\in E(H_{i}) is 4n^{3k-2|A|-1} -reachable from every edge in E_{\emptyset} . Proof. Let e\in E_{A\cup u_{1}v_{1}} . By Lemma 9.16 and Proposition 9.4 (ii) , it suffices to show that e is 3n^{3k-2|A|-1} -reachable from some edge e^{\prime}\in E_{A\cup u_{2}v_{2}} such that u_{2}v_{2}\in E(H_{j}) with |V(H_{j})|\geq(1-3\alpha)n for some j\in[m] . Consider following cases. Case 1: |A\cup u_{1}v_{1}|0. Let x\in V(K_{A\cup u_{1}v_{1}})\backslash V(H_{i}) . Note that x is not isolated in \partial_{2}(A\cup u_{1}v_{1}) by (A2) . By Definition 2.3 , (A2) and |V(K_{A\cup u_{1}v_{1}})|\geq(1/2+3\alpha)n , there exists xy\in E(K_{A\cup u_{1}v_{1}}) . Choose e^{\prime}\in E^{+}_{A\cup u_{1}v_{1}xy} , so e^{\prime}\in E^{+}_{A\cup u_{1}v_{1}} . Then by Proposition 9.6 (v) and e\in E_{A\cup u_{1}v_{1}} , e is n^{3k-2|A|-1} -reachable from e^{\prime} . Note that x\notin V(H_{i}) , u_{1}\in V(H_{i}) and so xu_{1}\notin E(H_{i}) . By Corollary 9.15 (c ) 1 and (c ) 2 , u_{1}\in V(H_{j}) with |V(H_{j})|\geq(1-3\alpha)n . Since \phi_{A} is locally 2 -edge colouring, xu_{1}\in E(H_{j}) . By Definition 9.4 , e^{\prime}\in E_{A\cup u_{1}v_{1}xy}\subseteq E_{A\cup u_{1}x} with u_{1}x\in E(H_{j}) as required. Case 2: |A\cup u_{1}v_{1}|=k-2 . By Lemma 8.4 (M1) , |V(C_{A\cup u_{1}v_{1}})|\geq(1/2+\gamma)n and then |V(C_{A\cup u_{1}v_{1}})\backslash V(H_{i})|\geq|V(C_{A\cup u_{1}v_{1}})|-|V(H_{i})|>\alpha n. By Definition 2.3 , there exists a vertex x\notin V(H_{i}) such that u_{1}x\in E(\partial_{2}(A)) . Note that u_{1}\in V(H_{i}) and so xu_{1}\notin E(H_{i}) . By Corollary 9.15 (c ) 1 and (c ) 2 , u_{1}\in V(H_{j}) with |V(H_{j})|\geq(1-3\alpha)n for some j\in[2] . Since \phi_{A} is locally 2 -edge-colouring, this implies that u_{1}x\in E(H_{j}) . By Lemma 8.4 (M1) , |V(C_{A\cup u_{1}x})|\geq(1/2+\gamma)n . Then |V(C_{A\cup u_{1}x})\cap V(C_{A\cup u_{1}v_{1}})|\geq|V(C_{A\cup u_{1}v_{1}})|+|V(C_{A\cup u_{1}x})|-n\geq 0. Let w\in V(C_{A\cup u_{1}x})\cap V(C_{A\cup u_{1}v_{1}}) , wz_{1}\in E(C_{A\cup u_{1}x}) and wz_{2}\in E(C_{A\cup u_{1}u_{2}}) . Let f=A\cup u_{1}v_{1}wz_{1}\text{ and }f^{\prime}=A\cup u_{1}xwz_{2}. So f\in E_{A\cup u_{1}v_{1}}^{+} . Note that f^{\prime}\in E_{A\cup u_{1}x} with u_{1}x\in E(H_{j}) and |V(H_{j})|\geq(1-3\alpha)n . Since f,e\in E^{+}_{A\cup u_{1}v_{1}} , e is n^{3k-2|A|-2} -reachable from f by (A4) . Therefore to complete the proof, by Proposition 9.4 (ii) , it suffices to show that f is 2n^{3k-2|A|-1} -reachable from f^{\prime} . Since f^{\prime}\backslash f=\{x,z_{2}\} , by Proposition 9.4 (iii) and (i) , it suffices to show that f is n^{3k-2|A|-1} -reachable from x . Since x\in V(C_{A\cup u_{1}v_{1}}) , let xy\in E(C_{A\cup u_{1}v_{1}}) and f^{\prime\prime}=A\cup u_{1}v_{1}xy . Then f^{\prime\prime},f\in E_{A\cup u_{1}v_{1}} . Thus f and f^{\prime\prime} is tight connect by Definition 7.1 . By Proposition 9.4 (v) , f is n^{k} -reachable from f^{\prime\prime} . Since x\in f^{\prime\prime} and |A|0. Let x\in V(C_{B_{1}})\cap V(C_{B_{2}}) , xy\in E(C_{B_{1}}) and xz\in E(C_{B_{2}}) . Let f=B_{1}\cup xy=A\cup u_{1}v_{1}\cup C\cup xy\text{ and }f^{\prime}=B_{2}\cup xz=A\cup u_{2}v_{2}\cup C\cup xz. Note that f^{\prime}\backslash f=\{z,u_{2},v_{2}\} . Next we claim that f is 2n^{3k-2|A|-1} -reachable from f^{\prime} . By Proposition 9.4 (i) and (iii) , it suffices to show that f is n^{3k-2|A|-1} -reachable from u_{2},v_{2} . Note that u_{2}\in V(H_{2}) implying that there exists an edge u_{2}u^{\prime}\in E(H_{2}) such that \phi_{A}(u_{2}u^{\prime})=\phi_{A}(u_{1}v_{1}) . Let f^{\prime\prime}\in E^{+}_{A\cup u_{2}u^{\prime}} . Since f\in E^{+}_{A\cup u_{1}v_{1}} and u_{2}\in f^{\prime\prime} , by the definition of \phi_{A} and Proposition 9.10 , f is n^{3k-2|A|-1} -reachable from f^{\prime\prime} and so from u_{2} . Note that v_{2}\in V(H_{2}) as well. We replace u_{2} by v_{2} in the above argument. We can deduce that f is also n^{3k-2|A|-1} -reachable from v_{2} . Thus f is 2n^{3k-2|A|-1} -reachable from f^{\prime} . Meanwhile, e,f\in E^{+}_{A\cup u_{1}v_{1}} and e^{\prime},f^{\prime}\in E^{+}_{A\cup u_{2}v_{2}} . Then by Proposition 9.4 (ii) and (A5)(A5.2) , we obtain that e is n^{3k-2|A|} -reachable from e^{\prime} . ∎ 9.4 (\mathcal{A},\mathcal{K}) -reachable In this subsection, we aim to prove that our host graph G is (\mathcal{A},\mathcal{K}) -reachable for \mathcal{A}=\partial_{\mod 2}(G) . Recall the definition of G^{*} and E_{\emptyset} in Definition 7.1 . Proof of Lemma 9.3 . Suppose that G is (\mathcal{A},\mathcal{K}) -reachable for some upward closed subset \mathcal{A}\subseteq\partial_{\mod 2}(G) . If \mathcal{A}=\partial_{\mod 2}(G) , then we are done. Otherwise, let A be a maximal subset of \partial_{\mod 2}(G)\backslash\mathcal{A} . By Proposition 9.5 , we can assume that |A|n/2. Since |V(K_{z_{3}\cup X_{j^{*}}})|\geq(1/2+3\alpha)n by (A3) , we have \displaystyle|\bigcap_{i\in[3]}V(K_{z_{i}\cup X_{j^{*}}})|\geq|V(K_{z_{1}\cup X_{j^{*}}})\cap V(K_{z_{2}\cup X_{j^{*}}})|+|V(K_{z_{3}\cup X_{j^{*}}})|-n\geq 3\alpha n. Then there exists x_{j^{*}+1}y_{j^{*}+1}\in\bigcap_{i\in[3]}E(K_{z_{i}\cup X_{j^{*}}}) by Proposition 2.4 (L2) . Let C=\{x_{1},y_{1}\dots,x_{m},y_{m}\} as required. ∎ Let B_{i}=z_{i}\cup C\text{ for }i\in[3]. Note that |B_{i}|=k-2 for i\in[3] . By Lemma 8.4 , there exist B_{i_{1}} and B_{i_{2}} such that E(C_{B_{i_{1}}})\cap E(C_{B_{i_{2}}})\neq\emptyset for distinct i_{1},i_{2}\in[3] . Let u_{1}u_{2}\in E(C_{B_{i_{1}}})\cap E(C_{B_{i_{2}}}) and e_{j}=B_{i_{j}}\cup u_{1}u_{2}\in E_{z_{i_{j}}}^{+} for j\in[2] . Then \displaystyle|e_{1}\cap e_{2}|=|(B_{i_{1}}\cup u_{1}u_{2})\cap(B_{i_{2}}\cup u_{1}u_{2})|=k-|B_{i_{1}}\backslash B_{i_{2}}|=k-1 and so e_{j} is 1 -reachable from e_{j^{\prime}} for \{j,j^{\prime}\}=[2] by Proposition 9.4 (iv) . However, e_{i_{j}}\in E^{+}_{z_{i_{j}}} for j\in[2] . This contradicts with the fact that \psi(z_{i_{1}})\neq\psi(z_{i_{2}}) . ∎ Finally, we show the reachable lemma for odd case. Proof of Lemma 9.1 for odd k . By Lemma 9.3 , G is (\mathcal{A},\mathcal{K}) -reachable for \mathcal{A}=\partial_{\mod 2}(G) . Let I_{G} be the set of isolated vertices in G . Define a vertex-colouring \psi on V(G)\backslash I_{G} as in Definition 9.21 . By Lemma 9.23 , \psi is 2-vertex coloured. Let H_{1} and H_{2} be the colour classes of \psi with |H_{1}|\geq|H_{2}| . Note that |I_{G}|\leq\alpha n by Definition 2.3 . Then |H_{1}|\geq(1-\alpha)n/2 . Let B_{i}=\{e~|~e\in E_{x}^{+}\text{ with }x\in H_{i}\} . Now, we enumerate all edges in E(G^{*})=E_{\emptyset} such that if e_{i_{1}}\in B_{1},e_{i_{2}}\in B_{2}\backslash B_{1} and e_{i_{3}}\in E_{\emptyset}\backslash(B_{1}\cup B_{2}) , then i_{1}\leq i_{2}\leq i_{3} . We claim this is the enumeration as required. If e\in E_{\emptyset}\backslash(B_{1}\cup B_{2}) , then by Proposition 9.6 (i) , e\in E_{x}^{-} for some x\in V(G) . By Proposition 9.6 (iv) , e is n^{3k} -reachable from all edges in E_{\emptyset} . Claim 9.25 . If e\in B_{2} , then e is n^{3k+1} -reachable from all e^{\prime}\in B_{1}\cup B_{2} . Proof of claim. Suppose that e\in E_{x}^{+} for some x\in H_{2} and e^{\prime}\in E_{y}^{+} for some y\in V(G) . If y\in H_{2} , then our claim follows \psi(x)=\psi(y) and Proposition 9.22 . If y\in H_{1} , then e^{\prime}\in B_{1} . Since |V(K_{x})|>(1/2+3\alpha)n by (A3) , |V(K_{x})\cap H_{1}|\geq|V(K_{x})|+|H_{1}|-n>0. Let z\in V(K_{x})\cap H_{1} . By Proposition 9.7 , there exists a (x,z,(k-3)/2) -common set C . Then |x\cup C|=|z\cup C|=k-2 . By Lemma 8.4 (M1) , we have that |V(C_{x\cup C})\cap V(C_{z\cup C})|\geq|V(C_{x\cup C})|+|V(C_{z\cup C})|-n>0. Let w_{1}\in V(C_{x\cup C})\cap V(C_{z\cup C}) , w_{1}w_{2}\in E(C_{x\cup C}) and w_{1}w_{3}\in E(C_{x\cup C}) . Let f=x\cup C\cup w_{1}w_{2}\text{ and }f^{\prime}=z\cup C\cup w_{1}w_{3}. Then f\in E_{x}^{+} and f^{\prime}\in E_{z}^{+} . We claim that f is 2n^{3k} -reachable from f^{\prime} . Note that f^{\prime}\backslash f=\{z,w_{3}\} . By Proposition 9.4 (iii) and (i) , it suffices to show that f is n^{3k} -reachable from z . Since z\in V(K_{x}) , by Proposition 9.6 (ii) , there exists an f^{\prime\prime}\in E_{x}^{+} with z\in f^{\prime\prime} . Then f is n^{3k} -reachable from f^{\prime\prime} by (A5)(A5.2) . Hence, f is n^{3k} -reachable from z and so 2n^{3k} -reachable from f^{\prime} . Note that f and e are both in E_{x}^{+} . So e is n^{3k} -reachable from f by (A5)(A5.2) . Since f^{\prime}\in E_{z}^{+} and e^{\prime}\in E_{y}^{+} with y,z\in H_{1} , by \psi(y)=\psi(z) and Proposition 9.22 , f^{\prime} is n^{3k} -reachable from e^{\prime} . Therefore, by Proposition 9.4 (ii) with (e,e^{\prime},e^{\prime\prime})=(f^{\prime},f,e) and (e^{\prime},f^{\prime},e) , e is n^{3k+1} -reachable from e^{\prime} . ∎ Finally, if e,e^{\prime}\in B_{1} , suppose that e\in E_{x}^{+} with x\in H_{1} and e^{\prime}\in E_{y}^{+} with y\in H_{1} . Then by \psi(x)=\psi(y) and Proposition 9.22 , e is n^{3k+1} -reachable from e^{\prime} . Therefore our enumeration is as required. ∎ 10 Rotatable lemma Let C\in\mathbb{N} , let G be a k -graph, and e=u_{1}\dots u_{k}\in E(G) . Recall that e is C -rotatable if for any u\in e , \sigma\in S_{k} and any rooted k -loose tree T at r , there exists a homomorphism \phi from T to G such that \phi(r)=u and \phi(v)=u_{\sigma(s)} for all v\in C_{s}(T) with \text{dist}(r,v)\geq C . Our aim of this section is to prove the rotatable proposition for G^{*} . Lemma 10.1 . Let 1/n\ll\alpha\ll\gamma\leq{1}/{k}\leq{1}/{4} . Let G be a k -graph on n vertices with \overline{\delta}^{\alpha}_{k-2}(G)\geq 1/2+\gamma . Then all edges in G^{*} is 10^{7}(k!)n^{4} -rotatable. When k=4 , we prove the following (slightly stronger) statement. Lemma 10.2 . Let 1/n\ll\alpha\ll\gamma\leq 1/4 . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Then all edges in G^{*} is 10^{7}n^{4} -rotatable. Then together with Lemmas 8.1 and 9.1 , these imply Lemma 7.3 . Proof of Lemma 7.3 . By Lemmas 8.1 , 9.1 and 10.1 , (R1) , (R2) and (R3) in Definition 4.5 hold for G^{*} . Therefore G^{*} is \eta -robust. ∎ In the next subsection, we refine the definition of rotatable. In Section 10.2 we show that Lemma 10.1 can be deduced from Lemma 10.2 . We show some auxiliary structures in Section 10.3 when k=4 . At last, We prove Lemma 10.2 in Section 10.4 . 10.1 Definitions refinement and basic properties We refine the definition of rotatable as follows. Let C\in\mathbb{N} and s\in[k] . Let G be a k -graph and e=u_{1}\dots u_{k}\in E(G) . Let T be a rooted k -loose tree at r . Recall that C_{j}(T) in Section 2.2 . For j\geq 0 and s\in[k] , let C_{s}^{j}(T)=\{v~|~v\in C_{s}(T):\text{dist}(r,v)=j\} , C_{s}^{\leq j}(T)=\bigcup_{i\in[j]}C_{s}^{i}(T) and C_{s}^{\geq j}(T)=\bigcup_{j\geq i}C_{s}^{i}(T) . Let \sigma,\pi\in S_{k} . We say that e is (C,\pi,\sigma) -rotatable if, for any rooted k -loose tree T at r , there exists a homomorphism \phi from T to G such that \displaystyle\phi(v)=\begin{cases}u_{\pi(1)}&\text{if $v=r$},\\ u_{\sigma(s)}&\text{if $v\in C^{\geq C}_{s}(T)$}.\end{cases} We say that e is [C,\pi,\sigma] -rotatable if e is (C,\pi,\sigma\pi) -rotatable. We say that e is [C,i,\sigma] -rotatable if e is [C,\pi,\sigma] -rotatable for all \pi\in S_{k} with \pi(1)=i . We say that e is [C,*,\sigma] -rotatable if e is [C,\pi,\sigma] -rotatable for all \pi\in S_{k} . Note that the order of vertices of e matters, but it will be known from context. We illustrate one key idea used in the proof of Lemma 10.2 . Suppose that \sigma\in S_{k} . Let e=u_{1}\dots u_{k} be an k -edge. Consider a tree T rooted at r . Let \mathcal{T}_{i}=\{T(v):v\in C_{i}^{1}(T)\} for i\in[k-1] . By Fact 2.2 , r,V(\mathcal{T}_{1}),\dots,V(\mathcal{T}_{k-1}) partition V(T) . If e is [C,i,\sigma] -rotatable for i\neq 1 . Then we attempt to initially embed r to u_{1} and C_{i}^{1}(T) to u_{i} . Next we extend our embedding for each T^{\prime}\in\mathcal{T}_{i} such that the root vertex in T^{\prime} mapping to u_{i} and most vertices of C_{i}(T)\cap V(T^{\prime}) mapping to u_{\sigma(i)} . We now list some basic properties of rotatable. Proposition 10.3 . Let C\in\mathbb{N} . Let G be a k -graph and e=u_{1}\dots u_{k}\in E(G) . Let \pi,\sigma,\tau\in S_{k} with \tau=(123\dots k)\in S_{k} . Then the following holds (i) if \sigma(i)=i , then e is [1,i,\sigma] -rotatable and so e is [1,*,\emph{\textbf{id}}] -rotatable; (ii) if e is (C,\pi\tau^{j},\sigma\tau^{j}) -rotatable for all j\in[k-1] , then e is (C+1,\pi,\sigma) -rotatable; (iii) if i_{0}\in[k] and e is [C,i,\sigma] -rotatable for all i\in[k]\backslash\{i_{0}\} , then e is [C+1,*,\sigma] -rotatable; (iv) if e is C -rotatable, then e is [C,*,\sigma] -rotatable; (v) if e is [C,*,\sigma] -rotatable for all \sigma\in S_{k} , then e is C -rotatable; (vi) if e is [C,*,\sigma] -rotatable, then e^{\prime}=u_{\pi(1)}\dots u_{\pi(k)} is [C,*,\pi\sigma\pi^{-1}] -rotatable.; (vii) if \sigma_{1},\sigma_{2}\in S_{k} and e is [C,*,\sigma_{i}] -rotatable for i\in[2] , then e is [2C,*,\sigma_{1}\sigma_{2}] -rotatable; (viii) if A is a generator of S_{k} and e is [C,\ast,\sigma] -rotatable for all \sigma\in A , then e is k!C -rotatable. Proof. For (i) , note that if \pi\in S_{k} and \pi(1)=i , then \sigma\pi(1)=i . Set \phi:V(T)\rightarrow V(G) to be such that, for all v\in C_{s}(T) , \phi(v)=u_{\sigma\pi(s)} . Then e is [1,i,\sigma] -rotatable and so e is [1,*,\textbf{id}] -rotatable. We now prove (ii) . Consider any rooted k -loose tree T at r . For j\in[k-1] , let \mathcal{T}_{j} be all rooted subtrees T(v) with v\in C_{\tau^{j}(1)}^{1}(T) . Note that r,V(\mathcal{T}_{1}),\dots,V(\mathcal{T}_{k-1}) partition V(T) . Consider j\in[k-1] , let T^{\prime}\in\mathcal{T}_{j} rooted at r^{\prime} . Let C_{s}(T^{\prime})=C_{\tau^{j}(s)}(T)\cap V(T^{\prime}) for s\in[k] and C^{C}_{s}(T^{\prime})=C^{C+1}_{\tau^{j}(s)}\cap V(T^{\prime}) . By our assumption, there exists a homomorphism \phi_{T^{\prime}} from T^{\prime} to G such that \displaystyle\phi_{T^{\prime}}(v)=\begin{cases}u_{\pi\tau^{j}(1)}&\text{if $v=r^{\prime}\in C^{1}_{\tau^{j}(1)}(T)$},\\ u_{\sigma\tau^{j}(s)}&\text{if $v\in C^{\geq C}_{s}(T^{\prime})$}=C^{\geq(C+1)}_{\tau^{j}(s)}(T)\cap V(T^{\prime}).\end{cases} Define \phi:V(T)\rightarrow V(G) to be such that \displaystyle\phi(v)=\begin{cases}u_{\pi(1)}&\text{if $v=r$,}\\ \phi_{T^{\prime}}(v)&\text{if $v\in V(T^{\prime})$ for some $T^{\prime}\in\bigcup_{j\in[k-1]}\mathcal{T}_{j}$}.\end{cases} It is easy to check that \phi is a homomorphism from T to G with \phi(r)=u_{\pi(1)} and for all v\in C_{s}^{\geq C+1}(T) , \phi(v)=u_{\sigma(s)} . For (iii) , it suffices to show that e is [C+1,i_{0},\sigma] -rotatable. Let \pi\in S_{k} with \pi(i)=i_{0} . Note that for j\in[k-1] , \pi\tau^{j}(1)\neq i_{0} . Then e is (C,\pi\tau^{j},\sigma\pi\tau^{j}) -rotatable by our assumption. So e is (C+1,\pi,\sigma\pi) -rotatable by (ii) . Hence e is [C+1,i_{0},\sigma] -rotatable. It is easy to see that (iv) , (v) and (vi) hold. For (vii) , consider any rooted k -loose tree T at r . By our assumption, there exists a homomorphism \phi_{1} from T to G such that \displaystyle\phi_{1}(v)=\begin{cases}u_{\pi(1)}&\text{if $v=r$,}\\ u_{\sigma_{1}\pi(s)}&\text{if $v\in C^{\geq C}_{s}(T)$.}\end{cases} For j\in[k] , let \mathcal{T}_{j} be all rooted subtrees T(v) with v\in C_{j}^{C}(T) . Consider j\in[k] and let T^{\prime}\in\mathcal{T}_{j} rooted at r^{\prime} . Let \pi_{j}=\sigma_{1}\pi\tau^{j-1} and C_{s}(T^{\prime})=C_{\tau^{j-1}(s)}(T)\cap V(T^{\prime}) for s\in[k] . So C^{C^{\prime}}_{s}(T^{\prime})=C^{C+C^{\prime}}_{\tau^{j-1}(s)}(T)\cap V(T^{\prime}) . Since e is [C,*,\sigma_{2}] -rotatable, there exists a homomorphism \phi^{\prime}_{T^{\prime}} from T^{\prime} to G to be such that \displaystyle\phi^{\prime}_{T^{\prime}}(v)=\begin{cases}u_{\pi_{s}(1)}=u_{\sigma_{1}\pi(j)}&\text{if $v=r^{\prime}$,}\\ u_{\sigma_{2}\pi_{s}(s)}=u_{\sigma_{2}\sigma_{1}\pi\tau^{j-1}(s)}&\text{if $v\in C^{\geq C}_{s}(T^{\prime})=C^{\geq 2C}_{\tau^{j-1}(s)}(T)\cap V(T^{\prime})$.}\end{cases} Next, define \phi:V(T)\rightarrow V(G) to be such that \displaystyle\phi(v)=\begin{cases}\phi_{1}(v)&\text{if $\text{dist}(r,v)\leq C$,}\\ \phi_{T^{\prime}}(v)&\text{if $v\in V(T^{\prime})$ for some $T^{\prime}\in\bigcup_{j\in[k-1]}\mathcal{T}_{j}$}.\end{cases} It is easy to check that \phi is a homomorphism from T to G with \phi(r)=u_{\pi(1)} and for all v\in C_{s}^{\geq 2C}(T) , \phi(v)=u_{\sigma_{1}\sigma_{2}\pi(s)} . Therefore (vii) holds and (viii) follows. ∎ 10.2 Reduction to the case k=4 We now prove Lemma 10.1 assuming Lemma 10.2 . Recall the Definition 7.1 of G^{*} . Proof of Lemma 10.1 . Let e=u_{1}\dots u_{k}\in E_{\emptyset}=E(G^{*}) with u_{1}u_{2}\in C_{u_{3}\dots u_{k}} . Note that \{(1i):i\in[2,k]\} is a generator set of S_{k} . By Proposition 10.3 (viii) , it suffices to show that for i\in[2,k] , e is [10^{7}n^{4},\ast,(1i)] -rotatable. Let i\in[4,k] , X=\{1,2,3,i\} and \sigma\in S_{X} . We now show that e is [10^{7}n^{4},*,\sigma] -rotatable (which implies the lemma). Let L be the link graph of e\backslash\{u_{1},u_{2},u_{3},u_{i}\} in G and L^{\prime} be the link graph of e\backslash\{u_{1},u_{2},u_{3},u_{i}\} in G^{*} . So \alpha -perturbed relative 2 -degree in L is at least 1/2+\gamma by Proposition 2.4 (L1) . Let L^{*} be the corresponding graph of L as in Definition 7.1 . Then by Proposition 7.2 , we have that L^{*}\subseteq L^{\prime} . Let T be a rooted k -loose tree at r and \pi\in S_{k} with \pi(1)=y . If y\notin X , then \sigma(y)=y . Thus by Proposition 10.3 (i) , e is [1,y,\sigma] -rotatable for y\notin X . Suppose that \pi(1)=y for some y\in X . Remove vertices in \bigcup_{j\in[k]\backslash X}C_{\pi^{-1}(j)}(T) from each edge of T . Then we obtain a set \mathcal{T} of vertex-disjoint 4 -trees. Let T^{\prime}\in\mathcal{T} be the unique tree with root vertex r . Let C_{\pi^{-1}(j)}(T^{\prime})=C_{\pi^{-1}(j)}(T)\cap V(T^{\prime}) for j\in X . By our assumption, each edge in L^{*} is 10^{7}n^{4} -rotatable. Then there is a homomorphism \phi_{T^{\prime}} from T^{\prime} to L^{*} such that for u\in V(T^{\prime}) and s\in\pi^{-1}(X) , \displaystyle\phi_{T^{\prime}}(u)=\begin{cases}u_{\pi(1)}&\text{if $u=r$,}\\ u_{\sigma\pi(s)}&\text{if $u\in C^{\geq 10^{7}n^{4}}_{s}(T^{\prime})$}.\end{cases} Define \phi:V(T)\rightarrow V(G) to be such that \phi(u)=\begin{cases}u_{\pi(s)}=u_{\sigma\pi(s)}&~\text{ if }u\in C_{s}(T)\text{ with }\pi(s)\notin X,\\ u_{\sigma\pi(s)}&~\text{ if }u\in C_{s}(T)\backslash V(T^{\prime})\text{ with }\pi(s)\in X,\\ \phi_{T^{\prime}}(u)&~\text{ if }u\in V(T^{\prime}).\par\end{cases} Note that \phi is the desired homomorphism from T to G . ∎ 10.3 Rotatable Structures for 4 -graphs We now establish some rotatable structures for proving Lemma 10.2 . Thus throughout this subsection, we will take k=4 . We will also adapt the following notation throughout. Let G be a 4 -graph and e an edge in G^{*} . We write e=\overline{u_{1}u_{2}}u_{3}u_{4} to mean that e\in E_{u_{1}u_{2}} . We sketch the proof for Lemma 10.2 . Let A=\{(13),(23),(43)\}\subseteq S_{4} . Note that A is a generator set of S_{4} . By Proposition 10.3 (viii) , if any edge e is [C,*,\sigma] -rotatable for all \sigma\in A , then e is rotatable and we are done. In this subsection, we will focus on the cases that \sigma=(34) and (23) (see more in Lemmas 10.7 and 10.8 ). Furthermore, we will show a structure in Lemma 10.10 with a transitive property which will help us prove [C,*,(13)] -rotatable for edge e in Section 10.4 . The next proposition states that the relationship between rotatablility of two edges that are tight connected. Proposition 10.4 . Let C\in\mathbb{N} . Let G be a 4 -graph. Let e=u_{1}\dots u_{4} and f=u_{1}^{\prime}\dots u_{4}^{\prime} be two edges in G . Suppose that there is a tight walk W=w_{1}\dots w_{4\ell} from e to f such that \displaystyle w_{i}=u_{\rho_{e}(i)}\text{ and }w_{4(\ell-1)+i}=u_{\rho_{f}(i)}^{\prime}\text{ for }i\in[4]. Let T be a rooted k -loose tree at r , j\in[4] and \sigma\in S_{4} . Suppose that \phi is a homomorphism from T to G such that \displaystyle\phi(v)=\begin{cases}u_{j}&~\text{if $v=r$,}\\ u_{\sigma(s)}&~\text{if $v\in C^{\geq C}_{s}(T)$}.\end{cases} Then there exists a homomorphism \phi^{\prime} from T to G such that \displaystyle\phi^{\prime}(v)=\begin{cases}u_{j}&~\text{if $v=r$,}\\ u^{\prime}_{\rho_{f}\rho_{e}^{-1}\sigma(s)}&~\text{if $v\in C^{\geq 4(C+{\ell})}_{s}(T)$}.\end{cases} Moreover, if e is [C,*,\sigma] -rotatable, then f is [4C+8\ell,*,\rho^{-1}\sigma] -rotatable, where \rho=\rho_{e}\rho_{f}^{-1} . Furthermore, if e is C -rotatable, then f is (4C+8\ell) -rotatable. Proof. Recall that the definition of layers L_{j} of T for j\geq 1 in Section 2.2 . Note that if u\in L_{j} , then j/4\leq\text{dist}(r,u)\leq j . For all t\geq 0 and j\in[4] , let w_{4(\ell-1+t)+j}=w_{4(\ell-1)+j} . To define \phi , we first embed the first 4C layers of T as \phi^{\prime} so that it has the correct “orientation”. We then use W to transfer the embedding onto f . Formally, we define \phi^{\prime}:V(T)\rightarrow V(G) to be such that \displaystyle\phi^{\prime}(v)=\begin{cases}\phi(v)&~\text{ if $v\in L_{i}$ with~$i\leq 4C$,}\\ w_{\rho_{e}^{-1}\sigma(s)+4(i-1)}&~\text{ if $v\in L_{4C+4i+s}$ with~$i\geq 1$ and $s\in[4]$}.\end{cases} Then for each i\geq\ell and s\in[4] , if v\in L_{4C+4i+s} , we have \phi^{\prime}(v)=w_{4(l-1)+\rho_{e}^{-1}\sigma(s)}=u^{\prime}_{\rho_{f}\rho_{e}^{-1}\sigma(s)}. Therefore \phi^{\prime} is the desired homomorphism. For the moreover statement, suppose that e is [C,*,\sigma] -rotatable. Let \pi\in S_{k} . Let w\in T with w\in\bigcup_{j\in[4]}L_{4\ell+j} . Consider subtree T(w) . Then for each i\in[4] , there exists a homomorphism \phi_{w,i} from T(w) to G^{*} such that \displaystyle\phi_{w,i}(v)=\begin{cases}u_{i}&~\text{if $v=w$,}\\ u^{\prime}_{\rho_{f}\rho_{e}^{-1}\sigma(s)}&~\text{if $v\in C^{\geq 4(C+{\ell})}_{s}(T(w))$.}\end{cases} Thus, define \phi_{0}:V(T)\rightarrow V(G) to be such that for j\in[4] , \displaystyle\phi_{0}(v)=\begin{cases}\phi_{1}(v)=w_{4(\ell-i)+\rho_{f}^{-1}\pi(j)}&~\text{if $v\in L_{4(i-1)+j}$ and $1\leq i\leq\ell$,}\\ \phi_{w,i}(v)&~\text{if $v\in V(T(w))$ with~$w\in\bigcup_{j\in[4]}L_{4\ell+j},\phi_{1}(w)=u_{i}$.}\end{cases} Note that we have that \phi_{0}(r)=w_{4(\ell-1)+\rho_{f}^{-1}\pi(1)}=u^{\prime}_{\pi(1)} and for vertex v\in C_{s}^{\geq 8\ell+4C}(T) , \phi_{0}(v)=u^{\prime}_{\rho^{-1}\sigma(s)} . Hence, f is [4C+8\ell,*,\rho^{-1}\sigma] -rotatable and so the furthermore statement follows. ∎ The next proposition states that there is an even tight walk between any edges in E_{uv} . Recall that C_{uv} is the induce graph of the largest component in the link graph of uv in G . Proposition 10.5 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Let \overline{u_{1}u_{2}}u_{3}u_{4},\overline{u_{1}u_{2}}y_{3}y_{4}\in E(G) . Then there exists a tight 4 -walk W=w_{1}w_{2}\dots w_{4\ell} such that, \displaystyle(w_{1},w_{2},w_{3},w_{4},w_{4\ell-3},w_{4\ell-2},w_{4\ell-1},w_{4\ell})=(u_{1},u_{2},y_{3},y_{4},u_{1},u_{2},u_{3},u_{4}). Proof. Note that there is a 2 -walk W^{\prime}=w^{\prime}_{1}\dots w^{\prime}_{2\ell} with \ell\leq 2n^{2} and (w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{2\ell-1},w^{\prime}_{2\ell})=(y_{3},y_{4},u_{3},u_{4}) in C_{u_{1}u_{2}} . Indeed, C_{u_{1}u_{2}} is a connect component and there exists a triangle in C_{u_{1}u_{2}} by Lemma 8.4 (M3) . Using this triangle, we can adjust the length of walk between u_{3}u_{4} and y_{3}y_{4} to be a even number. Then define W to be w_{4(i-1)+j}=u_{j} and w_{4(i-1)+2+j}=w^{\prime}_{2(i-1)+j} for i\in[\ell] and j\in[2] . Note that W is the desired tight walk. ∎ Let e=\overline{u_{1}u_{2}}u_{3}u_{4}\text{ and }f=\overline{u_{1}u_{2}}y_{3}y_{4} . Together with Lemma 10.4 (with \rho_{e}=\rho_{f}=\mathbf{id} ), we immediately imply following corollary for edges in E_{u_{1}u_{2}} . Corollary 10.6 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Suppose that \overline{u_{1}u_{2}}u_{3}u_{4}\in E(G) is [C,*,\sigma] -rotatable. Then all edges e=\overline{u_{1}u_{2}}u^{\prime}u^{\prime\prime}\in E_{u_{1}u_{2}} are [4C+16n^{2},*,\sigma] -rotatable. Following lemma states that every edge in G^{*} is [30n^{2},*,(34)] -rotatable. Lemma 10.7 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Then each edge \overline{u_{1}u_{2}}u_{3}u_{4}\in E(G^{*}) is [30n^{2},*,(34)] -rotatable. Proof. By Proposition 10.5 with (\overline{u_{1}u_{2}}u_{3}u_{4},\overline{u_{1}u_{2}}u_{4}u_{3}) playing the role of (\overline{u_{1}u_{2}}u_{3}u_{4},\overline{u_{1}u_{2}}y_{3}y_{4}) , there exists a tight walk W=w_{1}w_{2}\dots w_{4l} with \ell\leq 2n^{2} such that \displaystyle(w_{1},w_{2},w_{3},w_{4},w_{4\ell-3},w_{4\ell-2},w_{4\ell-1},w_{4\ell})=(u_{1},u_{2},u_{3},u_{4},u_{1},u_{2},u_{4},u_{3}). By Proposition 10.3 (i) , \overline{u_{1}u_{2}}u_{3}u_{4} is [1,*,\mathbf{id}] -rotatable. Apply Proposition 10.4 with (\overline{u_{1}u_{2}}u_{3}u_{4},\overline{u_{1}u_{2}}u_{3}u_{4},\mathbf{id},(34)) playing the role of (e,f,\rho_{e},\rho_{f}) . It implies that \overline{u_{1}u_{2}}u_{3}u_{4} is [30n^{2},*,(34)] -rotatable. ∎ Next, we show that under some circumstances, \overline{u_{1}u_{2}}u_{3}u_{4} is (23) -rotatable. Lemma 10.8 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Let \overline{u_{1}u_{2}}u_{3}u_{4} , \overline{u_{1}u_{2}}y_{3}y_{4} , u_{1}u_{3}y_{3}y_{4}\in E(G) . Then \overline{u_{1}u_{2}}u_{3}u_{4} is [10n^{2},*,(23)] -rotatable. Proof. Let \sigma=(23) and T be a rooted k -loose tree at r . Since \sigma(i)=i for i\in\{1,4\} , by Proposition 10.3 (i) , \overline{u_{1}u_{2}}y_{3}y_{4} is [1,i,\sigma] -rotatable for i\in\{1,4\} . By Proposition 10.3 (iii) , it suffices to show that \overline{u_{1}u_{2}}u_{3}u_{4} is [9n^{2},3,\sigma] -rotatable. Let \pi\in S_{4} with \pi(1)=3 . By Proposition 10.5 with \overline{u_{2}u_{1}}y_{3}y_{4} and \overline{u_{2}u_{1}}u_{3}u_{4} , there exists a tight walk W=w_{1}w_{2}\dots w_{4l} with \ell\leq 2n^{2} such that (w_{1},w_{2},w_{3},w_{4},w_{4\ell-3},w_{4\ell-2},w_{4\ell-1},w_{4\ell})=(u_{2},u_{1},y_{3},y_{4},u_{2},u_{1},u_{3},u_{4}). Let W^{\prime} be the tight walk obtained by concatenating u_{3}u_{1}y_{3}y_{4} and W . Rewrite W^{\prime}=w^{\prime}_{1}\dots w^{\prime}_{4(\ell+1)} such that (w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3},w^{\prime}_{4},w^{\prime}_{4\ell+1},w^{\prime}_{4\ell+2},w^{\prime}_{4\ell+3},w^{\prime}_{4\ell+4})=(u_{3},u_{1},y_{3},y_{4},u_{2},u_{1},u_{3},u_{4}). Define the homomorphism \phi^{\prime} from T to G such that \displaystyle\phi^{\prime}(v)=\begin{cases}u_{1}&\text{if $v\in C_{s}(T)$ and $\sigma\pi(s)=1$,}\\ u_{3}&\text{if $v\in C_{s}(T)$ and $\sigma\pi(s)=2$,}\\ y_{3}&\text{if $v\in C_{s}(T)$ and $\sigma\pi(s)=3$,}\\ y_{4}&\text{if $v\in C_{s}(T)$ and $\sigma\pi(s)=4$.}\end{cases} (10.1) In particular, \phi^{\prime}(r)=u_{3} as \sigma\pi(1)=2 . Apply Proposition 10.4 with (u_{3}u_{1}y_{3}y_{4},u_{2}u_{1}u_{3}u_{4},W^{\prime},\mathbf{id},\mathbf{id})=(e,f,W,\sigma\pi,\rho_{e},\rho_{f}). Then there exists a homomorphism \phi from T to G to be such that \displaystyle\phi(v)=\begin{cases}u_{3}&\text{if $v=r$,}\\ u_{1}&\text{if $v\in C^{\geq 4(\ell+2)}_{s}(T)$ and $\sigma\pi(s)=1$,}\\ u_{2}&\text{if $v\in C^{\geq 4(\ell+2)}_{s}(T)$ and $\sigma\pi(s)=2$,}\\ u_{3}&\text{if $v\in C^{\geq 4(\ell+2)}_{s}(T)$ and $\sigma\pi(s)=3$,}\\ u_{4}&\text{if $v\in C^{\geq 4(\ell+2)}_{s}(T)$ and $\sigma\pi(s)=4$}\end{cases}=\begin{cases}u_{3}&~\text{if $v=r$,}\\ u_{\sigma\pi(s)}&~\text{if $v\in C^{\geq 4(\ell+2)}_{s}(T)$}.\end{cases} Note that \ell\leq 2n^{2} . Hence, \overline{u_{1}u_{2}}u_{3}u_{4} is [9n^{2},3,\sigma] -rotatable as required. ∎ By the lemma, we have the following corollary. Corollary 10.9 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Let \overline{u_{1}u_{2}}u_{3}u_{4}\in G^{*} . Suppose that E(C_{u_{1}u_{2}})\cap E(C_{u_{1}u_{3}})\neq\emptyset . Then \overline{u_{1}u_{2}}u_{3}u_{4} is [30n^{2},*,(23)] -rotatable. Proof. Let y_{3}y_{4}\in E(C_{u_{1}u_{2}})\cap E(C_{u_{1}u_{3}}) . Then \overline{u_{1}u_{2}}y_{3}y_{4} and \overline{u_{1}u_{3}}y_{3}y_{4}\in E(G) . By Lemma 10.8 , we are done. ∎ Next, we use a special structure to imply a rotation transitivity lemma. Lemma 10.10 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Let \sigma\in S_{3} . Let \overline{u_{1}u_{2}}u_{3}u_{4} , \overline{u_{1}u_{2}}y_{3}y_{4}\in E(G) . Suppose that xu_{2}u_{3}y_{4}\in E(G) which is [C,*,\sigma] -rotatable. Then \overline{u_{1}u_{2}}u_{3}u_{4} is [C+30n^{2},*,\sigma] -rotatable. Moreover, if xu_{2}u_{3}y_{4} is C -rotatable, then \overline{u_{1}u_{2}}u_{3}u_{4} is 4!(C+30n^{2}) -rotatable. Proof. By Proposition 10.3 (iii) , it suffices to show that \overline{u_{1}u_{2}}u_{3}u_{4} is [C+10n^{2},i^{*},\sigma] -rotatable for i^{*}\in\{2,3,4\} . Consider i^{*}\in\{2,3,4\} . Let \pi\in S_{4} be with \pi(1)=i^{*} . Let T be a rooted 4 -tree at r . If i^{*}=4 , then \sigma(4)=4 . By Proposition 10.3 (i) , \overline{u_{1}u_{2}}u_{3}u_{4} is [1,4,\sigma] -rotatable. We may assume that i^{*}=2 or 3 . Let \displaystyle(v_{1},v_{2},v_{3},v_{4})=(x,u_{2},u_{3},y_{4}). Since v_{1}v_{2}v_{3}v_{4} is [C,*,\sigma] -rotatable, there is a homomorphism \phi^{\prime} from T to G such that \displaystyle\phi^{\prime}(u)=\begin{cases}v_{i^{*}}~&\text{ if }u=r,\\ v_{\sigma\pi(j)}~&\text{ if }u\in C^{\geq C}_{j}(T).\end{cases} Next consider each rooted subtree T(v) with \text{dist}(r,v)=C . Claim 10.11 . Let v\in\bigcup_{i\in[4]}C_{i}^{C^{\prime}}(T) with C^{\prime}\geq C and \phi^{\prime}(v)=v_{j} . Then there exists a homomorphism \phi_{v} from T(v) to G such that \displaystyle\phi_{v}(u)=\begin{cases}\phi^{\prime}(v)=v_{j}~&\text{ if }u=v,\\ u_{\sigma\pi(s)}~&\text{ if }u\in C^{\geq C^{\prime}+10n^{2}}_{s}(T)\cap V(T(v)).\end{cases} Proof of claim. If j=2\text{ or }3 , then \phi^{\prime}(v)=v_{j}=u_{j} and v\in C_{j_{0}}(T) with \sigma\pi(j_{0})=j . Define \phi_{v} be such that \phi_{v}(w)=u_{\sigma\pi(s)}~\text{ if }w\in C_{s}(T)\cap V(T(v)). If j=4 , then \phi^{\prime}(v)=v_{4}=y_{4} and v\in C_{j_{0}}(T) with \sigma\pi(j_{0})=4 . Let \tau=(1234) . for s\in[k] , let C_{s}(T(v))=C_{\tau^{j_{0}-1}(s)}(T)\cap V(T(v)). Note that C^{i}_{s}(T(v))=C^{(i+C^{\prime})}_{\tau^{j_{0}-1}(s)}(T)\cap V(T(v)) . Let u_{1}^{\prime}u_{2}^{\prime}u_{3}^{\prime}u_{4}^{\prime}=u_{1}u_{2}y_{3}y_{4} . Since \sigma(4)=4 , by Proposition 10.3 (i) , u_{1}u_{2}y_{3}y_{4} is [1,4,\sigma] -rotatable and so (1,\pi\tau^{j_{0}-1},\sigma) -rotatable. Then define a homomorphism \phi^{\prime}_{v} from T(v) to G to be such that \displaystyle\phi^{\prime}_{v}(u)=\begin{cases}u_{4}^{\prime}&\text{if $u=v$, }\\ u^{\prime}_{\sigma\pi\tau^{j_{0}-1}(s)}&\text{if $u\in C_{s}^{\geq 1}(T(v))$}\end{cases}=\begin{cases}u_{1}^{\prime}=u_{1}&\text{if $u\in C_{s}(T(v))$ and $\sigma\pi\tau^{j_{0}-1}(s)=1$,}\\ u_{2}^{\prime}=u_{2}&\text{if $u\in C_{s}(T(v))$ and $\sigma\pi\tau^{j_{0}-1}(s)=2$,}\\ u_{3}^{\prime}=y_{3}&\text{if $u\in C_{s}(T(v))$ and $\sigma\pi\tau^{j_{0}-1}(s)=3$,}\\ u_{4}^{\prime}=y_{4}&\text{if $u\in C_{s}(T(v))$ and $\sigma\pi\tau^{j_{0}-1}(s)=4$.}\end{cases} By Proposition 10.3 , there exists a tight walk W=w_{1}\dots w_{4\ell} with \ell\leq 2n^{2} such that \displaystyle(w_{1},w_{2},w_{3},w_{4},w_{4\ell-3},w_{4\ell-2},w_{4\ell-1},w_{4\ell})=(u_{1},u_{2},y_{3},y_{4},u_{1},u_{2},u_{3},u_{4}). Apply Proposition 10.4 and obtain a homomorphism \phi_{v} from T(v) to G such that \displaystyle\phi_{v}(u)=\begin{cases}y_{4}=v_{4}&\text{if $u=r$,}\\ u_{\sigma\pi\tau^{j_{0}-1}(s)}&\text{if $u\in C_{s}^{\geq 4(\ell+1)}$}(T(v))=C_{\tau^{j_{0}-1}(s)}^{\geq 4(\ell+1)+C^{\prime}}(T)\cap V(T(v)).\end{cases} (10.2) For vertex u\in C_{s}^{\geq C^{\prime}+9n^{2}}(T)\cap V(T(v)) with s\in[4] , we have \phi_{v}(u)=u_{\sigma\pi(s)} . Therefore we may assume j=1 . Consider w\in V(T(v)) with \text{dist}(v,w)=1 . Then w\in\bigcup_{i\in[4]}C_{i}^{(C^{\prime}+1)}(T) and \phi^{\prime}(w)\neq\phi^{\prime}(v)=v_{1} . Since \phi^{\prime}(w)\in\{v_{2},v_{3},v_{4}\} , by our previous argument, there exists a homomorphism \phi_{w} from T(w) to G such that \displaystyle\phi_{w}(u)=\begin{cases}\phi^{\prime}(w)~&\text{ if }u=w,\\ u_{\sigma\pi(s)}~&\text{ if }u\in C^{\geq(C^{\prime}+1)+9n^{2}}_{s}(T)\cap V(T(w)).\end{cases} Define the homomorphism \phi_{v} from T(v) to G to be such that \phi_{v}(u)=\begin{cases}v_{1}~&\text{ if $u=v$},\\ \phi_{w}(u)~&\text{ if $v\in V(T(w))$ for some $w$ with~$\text{dist}(v,w)=1$}.\end{cases} in \phi_{v} , we have that \phi_{v}(u)=u_{\sigma\pi(s)}\text{ if }u\in C^{\geq C^{\prime}+10n^{2}}_{s}(T)\cap V(T(v)) for s\in[4] . Therefore our claim holds. ∎ Now we can give the final homomorphism \phi from T to G^{*} . Define \phi as follow \phi(u)=\begin{cases}\phi^{\prime}(u)~~~&\text{ if }u\in\bigcup_{j\in[4]}C_{j}^{\leq C}(T),\\ \phi_{v}(u)~~~&\text{ if }u\in V(T(v))\text{ for some }v\in\bigcup_{j\in[4]}C^{C}_{j}(T).\end{cases} Therefore, \overline{u_{1}u_{2}}u_{3}u_{4} is [C+10n^{2},i^{*},\sigma] -rotatable for i^{*}\in\{2,3\} . Note that S_{3}\cup\{(34)\} is a generator set of S_{4} . The moreover statement follows from Lemma 10.7 and Proposition 10.3 (viii) . ∎ 10.4 Proof of Lemma 10.2 In this subsection, we will prove the final ingredient that e is [C,*,(13)] by digraph. First we show that there is a special vertex from V(G) . Proposition 10.12 . Let 1/n\ll\alpha\ll\gamma . Let G be a 4 -graph on n vertices with \overline{\delta}^{\alpha}_{2}(G)\geq 1/2+\gamma . Let u be a non-isolated vertex in V(G) . Then there exists a vertex w such that the number of v\in V(G) with E(C_{uw})\cap E(C_{uv})\neq\emptyset is at least (1/2-2\alpha)n . Proof. Let N_{1}(u) be the neighbour set of u in \partial_{2}(G) . Then |N_{1}(u)|\geq(1-\alpha)n by Definition 2.3 . Let x\in N_{1}(u) and X=\{x^{\prime}\in N_{1}(u):E(C_{ux})\cap E(C_{ux^{\prime}})\neq\emptyset\} . If |X|\geq(1/2-2\alpha)n , then we are done by setting w=x . We may assume that |X|<(1/2-2\alpha)n . By Lemma 8.4 (M4) , for all z,z^{\prime}\in N_{1}(u)\backslash(X\cup\{u,x\}) , E(C_{uz})\cap E(C_{uz^{\prime}})\neq\emptyset . Note that |N_{1}(u)\backslash(X\cup\{u,x\})|>(1-\alpha)n-({1}/{2}-2\alpha)n-2\geq{n}/2. We are done by setting w=z\in N_{1}(u)\backslash(X\cup\{u,x\}) . ∎ Now, we are ready to prove Lemma 10.2 . Proof of Lemma 10.2 . Define a digraph D on V(G) to be \overrightarrow{u_{1}u_{2}}\in E(D) if each edge \overline{u_{1}u_{2}}u^{\prime}u^{\prime\prime} in E_{u_{1}u_{2}} is [n^{4},*,(23)] -rotatable. Claim 10.13 . For any non-isolated vertex u_{1}\in V(G) , d_{D}^{+}(u_{1})\geq(1/2-2\alpha)n . Proof of claim. By Proposition 10.12 , there exists a vertex u_{2} such that the number of v\in V(G^{*}) with E(C_{u_{1}u_{2}})\cap E(C_{u_{1}v})\neq\emptyset is at least (1/2-2\alpha)n . Let A=\{v\in V(G)~|~E(C_{u_{1}u_{2}})\cap E(C_{u_{1}v})\neq\emptyset\} . Then |A|\geq(1/2-2\alpha)n . By Lemma 8.4 (M1) , we have that \displaystyle|V(C_{u_{1}u_{2}})\cap A|\geq|V(C_{u_{1}u_{2}})|+|A|-n>0. Let u_{3}\in V(C_{u_{1}u_{2}})\cap A and \overline{u_{1}u_{2}}u_{3}u_{4}\in E(G^{*}) . Since E(C_{u_{1}u_{2}})\cap E(C_{u_{2}u_{3}})\neq\emptyset , by Corollary 10.9 , \overline{u_{1}u_{2}}u_{3}u_{4} is [10n^{2},*,(23)] -rotatable. For x_{2}\in A and \overline{u_{1}x_{2}}x_{3}x_{4}\in E(G^{*}) , let y_{3}y_{4}\in E(C_{u_{1}u_{2}})\cap E(C_{u_{1}x_{2}}) . By Proposition 10.5 , there exist two tight walks W=w_{1}\dots w_{4\ell} and W^{\prime}=w^{\prime}_{1}\dots w^{\prime}_{4\ell^{\prime}} with \ell,\ell^{\prime}\leq 2n^{2} such that \displaystyle(w_{1},w_{2},w_{3},w_{4},w_{4\ell-3},w_{4\ell-2},w_{4\ell-1},w_{4\ell})=(u_{1},x_{2},x_{3},x_{4},u_{1},x_{2},y_{3},y_{4}) and \displaystyle(w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3},w^{\prime}_{4},w^{\prime}_{4\ell^{\prime}-3},w^{\prime}_{4\ell^{\prime}-2},w^{\prime}_{4\ell^{\prime}-1},w^{\prime}_{4\ell^{\prime}})=(u_{1},u_{2},y_{3},y_{4},u_{1},u_{2},u_{3},u_{4}). Note that WW^{\prime}=w_{1}\dots w_{4\ell}w_{1}^{\prime}\dots u_{4\ell^{\prime}} is a tight 4 -walk. Hence by Proposition 10.5 with \overline{u_{1}u_{2}}u_{3}u_{4},\overline{u_{1}x_{2}}x_{3}x_{4} , \textbf{id},\textbf{id}) playing the role of (e,f,\rho_{e},\rho_{f}) , we have \overline{u_{1}x_{2}}x_{3}x_{4} is [n^{4},*,(23)] -rotatable. Thus, each edge e in E_{u_{1}v} with v\in A is [n^{4},*,(23)] -rotatable. It implies that A\subseteq N_{D}^{+}(u_{1}) and d_{D}^{+}(u_{1})\geq(1/2-2\alpha)n . ∎ Claim 10.14 . Let \overrightarrow{u_{1}u_{2}}\in E(D) . Then every edge e\in E_{u_{1}u_{2}} is 10^{4}n^{4} -rotatable. Proof of claim. By Lemma 8.4 (M1) and Claim 10.13 , we have that \displaystyle|V(C_{u_{1}u_{2}})\cap N_{D}^{+}(u_{2})|\geq|V(C_{u_{1}u_{2}})|+|N_{D}^{+}(u_{2})|-n>0. Let u_{3}\in V(C_{u_{1}u_{2}})\cap N_{D}^{+}(u_{2}) and \overline{u_{1}u_{2}}u_{3}u_{4}\in E(G) . Meanwhile, by Lemma 8.4 (M1) , we obtain that \displaystyle|V(C_{u_{1}u_{2}})\cap V(C_{u_{2}u_{3}})|\geq|V(C_{u_{1}u_{2}})|+|V(C_{u_{2}u_{3}})|-n>0. Let y_{4}\in V(C_{u_{1}u_{2}})\cap V(C_{u_{2}u_{3}}) and \overline{u_{1}u_{2}}y_{3}y_{4} , \overline{u_{2}u_{3}}xy_{4}\in E(G^{*}) . Note that u_{3}\in N^{+}_{D}(u_{2}) , so \overline{u_{2}u_{3}}xy_{4} is [n^{4},*,(23)] -rotatable. Hence xu_{2}u_{3}y_{4} is [n^{4},*,(13)] -rotatable by Proposition (vi) with \pi=(132) . By Lemma 10.10 , it implies that \overline{u_{1}u_{2}}u_{3}u_{4} is [2n^{4},*,(13)] -rotatable. By Lemma 10.7 , \overline{u_{1}u_{2}}u_{3}u_{4} is [n^{4},*,(34)] -rotatable. Meanwhile, since u_{2}\in N_{D}^{+}(u_{1}) , \overline{u_{1}u_{2}}u_{3}u_{4} is [n^{4},*,(23)] -rotatable. Note that \{(13),(34),(23)\} is a generator of S_{4} , so \overline{u_{1}u_{2}}u_{3}u_{4} is 10^{3}n^{4} -rotatable by Proposition 10.3 (viii) . By Corollary 10.6 , each edge e\in E_{u_{1}u_{2}} is 10^{4}n^{4} -rotatable. ∎ Suppose that e\in E_{u_{1}u_{2}} is not 10^{7}n^{4} -rotatable for some distinct u_{1}u_{2}\in E(\partial_{2}(G)) . By Claim 10.14 , \overrightarrow{u_{1}u_{2}}\notin E(D) . Then by Lemma 8.4 (M1) , we have \displaystyle|V(C_{u_{1}u_{2}})\cap N_{D}^{+}(u_{2})|\geq|V(C_{u_{1}u_{2}})|+d^{+}(u_{2})-n>0. Let u_{3}\in V(C_{u_{1}u_{2}})\cap N^{+}(u_{2}) and \overline{u_{1}u_{2}}u_{3}u_{4}\in E(G) . Meanwhile, by Lemma 8.4 (M1) , we obtain that \displaystyle|V(C_{u_{1}u_{2}})\cap V(C_{u_{2}u_{3}})|\geq|V(C_{u_{1}u_{2}})|+|V(C_{u_{2}u_{3}})|-n>0. Let y_{4}\in V(C_{u_{1}u_{2}})\cap V(C_{u_{2}u_{3}}) and \overline{u_{1}u_{2}}y_{3}y_{4} , \overline{u_{2}u_{3}}xy_{4}\in E(G^{*}) . Note that u_{3}\in N^{+}_{D}(u_{2}) . \overline{u_{2}u_{3}}xy_{4} is 10^{4}n^{4} -rotatable. So xu_{2}u_{3}y_{4} is 10^{4}n^{4} -rotatable. By Lemma 10.10 , it implies that \overline{u_{1}u_{2}}u_{3}u_{4} is 10^{6}n^{4} -rotatable. By Corollary 10.6 , each edge e\in E_{u_{1}u_{2}} is 10^{7}n^{4} -rotatable, a contradiction. ∎ 11 Concluding Remark In this paper, we showed that \delta_{k,k-2}^{T}=1/2 for k\geq 4 . However, our proof is unable to map the root vertex to an arbitrary vertex due to (R2) . Then we may ask whether this is possible. Question 11.1 . Let 1/n\ll\gamma\ll 1/\Delta,1/k\leq 1/4 . Let G be a k -graph on n vertices with \overline{\delta}_{k-2}(G)\geq 1/2+\gamma and v\in V(G) . Let T be a rooted n -vertex k -loose tree at r with \Delta_{1}(T)\leq\Delta . Is there an embedding \psi from T to G such that \psi(r)=v ? Another direction is to investigate how large \Delta_{1}(T) in Theorem 4.6 can be. For 2 -graph case, result in [ 18 ] shows that tree T with \Delta(T)\leq cn/\log n can be embedded to a graph G with \overline{\delta}_{1}(G)>1/2 and this is tight up to a constant c . Furthermore, for almost spanning loose trees, there are two directions to consider. 11.1 Almost Spanning loose trees in general hypergraphs Rödl, Ruciński and Szemerédi [ 29 ] showed that in k -graph G , if \overline{\delta}_{k-1}(G)>1/k , then there exists an almost perfect matching in k -graphs. However, the perfect matching threshold \delta_{k,k-1}^{PM}=1/2 . Note that in Theorem 4.6 , the 1/2 for embedding spanning tree is needed due to the absorption step. So we wonder whether the relative minimum degree threshold for existence of almost spanning loose trees is smaller than the threshold for spanning loose trees. Problem 11.2 . Let 1/n\ll\varepsilon\ll\gamma\ll 1/\Delta,1/k and \ell\in[k-1] . Determine infimum \delta such that if G is a k -graph on n vertices with \overline{\delta}_{\ell}(G)\geq\delta+\gamma and T be a k -loose tree on (1-\varepsilon)n vertices with \Delta_{1}(T)\leq\Delta , then there is an embedding from T to G . In particular, when \ell=k-1 , is \delta<\delta^{T}_{k,k-1}=1/2 ? Recall that a binary k -loose tree of even depth containing a perfect matching. On the other hand, there is no perfect matching in loose Hamiltonian path. Keevash, Kühn, Mycroft and Osthus [ 16 ] showed that if a k -graph G with sufficient large n vertices and \overline{\delta}_{k-1}(v)>\frac{1}{2(k-1)} , then there exists a loose Hamiltonian cycle and so a loose Hamiltonian path in G . Hence, we ask whether the minimum degree threshold for the existence of embedding for a loose tree T depends on the size of the largest matching in T . Problem 11.3 . Let 1/n\ll\gamma\ll 1/\Delta,1/k , \ell\in[k-1] and \theta\in[0,1] . Determine the infimum \delta such that if G is a k -graph on the n vertices with \overline{\delta}_{\ell}(G)\geq\delta+\gamma and T is a n -vertex k -loose tree with the largest matching size \theta n and \Delta_{1}(T)\leq\Delta , then there exists an embedding from T to G . 11.2 Almost Spanning loose trees in linear hypergraphs The other direction is the existence of loose trees embedding in linear hypergraphs. We say a hypergraph is linear if any two edges share at most one vertex. Recently, Im and Lee [ 12 ] considered the Dirac type problem on linear hypergraphs. They showed that in linear k -graph G , if \delta_{1}(G)>1/k , then there exists an almost perfect matching in G and this bound is asymptotically tight. Moreover, they showed that in G , there exists an embedding for every spanning k -loose tree with bounded vertex degree and o(|V(G)|) leaves. In [ 11 ] , Im, Kim, Lee and Methuku showed that \delta_{1}(G)>(1/2-o(1))n is sufficient for the existence of embedding. We note that in general, finding perfect matchings in linear hypergraphs is not possible. Even if the graph is a Steiner triple system, it may not contain a perfect matching. Since a binary k -loose tree with even depth contains a perfect matching, we can not guarantee the existence for all spanning k -loose trees in linear hypergraphs. Hence, it would be interesting to consider the following generalization problem for almost spanning loose trees. Question 11.4 . Let 1/n\ll\varepsilon\ll\gamma\ll\Delta,1/k . Determine the infimum \delta such that if G is a linear k -graph on n vertices, \overline{\delta}_{1}(G)\geq\delta+\gamma and T is a k -loose tree on (1-\varepsilon)n vertices and \Delta_{1}(T)\leq\Delta , then there exists an embedding from T to G . Note that Im, Kim, Lee and Methuku [ 11 ] showed that \delta\leq 1/2 .