Embedding Problems In Uniformly Dense Hypergraphs

Embedding problem has long been an important research topic in extremal combinatorics,focusing on establishing extremal conditions to ensure that a combinatorial object contains a given substructure.There are two types of embedding problems that have played significant roles in the development of extremal combinatorics:the Turán problem and the perfect tiling problem.Given a k-graph(k-uniform hypergraph)F,the Turán density πr(F)of F is the maximum density among all k-graphs which contains no copy of F.Determining π(F)for a given k-graph F is a classical and central problem in extremal combinatorics,namely Turán,problem.Given two k-graphs F and H,a perfect F-tiling(or F-factor)of H is a collection of vertex-disjoint copies of F in H that together cover all vertices of H.Perfect tiling problems,as a strengthening of the Turán problem,aim to find extremal conditions on H which guarantee a perfect F-tiling,which also have a long and profound history in extremal combinatorics.In this dissertation,we use many powerful and deep tools including the probabilistic method,hypergraph regularity method and absorbing method to study Turán densities and perfect tilings of given k-graphs F in uniformly dense hypergraphs.Regarding quasi-random graphs,we know that there are several equivalent definitions.In contrast to graphs,when k≥ 3,there are non-equivalent notions of quai-randomness for k-graphs.Uniformly dense hypergraphs,as a generalization of quai-random hypergraphs,also have several inequivalent definitions.Roughly speaking,a k-graph H is(d,μ,*)-dense means that H is at least d-dense with respect to a given random structure*and error μ.In this paper,we refer to all(d,μ,*)-dense k-graphs as uniformly dense hypergraphs.In the first part of this thesis,we first study Turán problem in(d,μ,1)-dense 3graphs,where(d,μ,1)-dense means that every linear-size subhypergraph has density at least d.Restricting to(d,μ,1)-dense 3-graphs,the 1-uniform Turan density of a given 3-graph F is deonted by π1(F),that is the supremum over all d ∈[0,1]for which there is an F-free(d,μ,1)-dense 3-graph for any μ>0.Determining π1(F)was suggested by Erdos and Sos in 1980s.In particular,they raised the questions of determining 7Ti(K4(3)-)and π1(K4(3)).Recently,Glebov,Kral’ and Volec and independently Reiher,R(?)dl and Schacht proved that π1(K4(3)-)=1/4.In 2018,Reiher,Rodl and Schacht extended the definition of(d,μ,1)-dense 3-graphs to(d,μ,k-2)-dense k-graphs for k≥2,where(d,μ,k-2)-dense means that edge distribution of host hypergraphs with respect to every(k-2)-graph with the same vertex set has density at least d.They proposed the study of uniform Turan density πk-2(F)for a given k-graphs F in(d,μ,k-2)-dense k-graphs.In particular,they characterised all k-graphs satisfyingπk-2(F)=0 and shown that πk-2(·)"jumps" from 0 to at least k-k.Motivated by these results,for 3-graphs,we first prove a sufficient condition for 3graphs F satisfying π1(F)=1/4.In particular,all currently known 3-graphs F whoseπ1(F)is 1/4 satisfy this condition.In addition,we also construct some intriguing 3graphs F with π1(F)=1/4.For k-graphs with k≥3,we give a general framework for studying πk-2(F)of k-graphs F.By using this framework,we also give a sufficient condition for k-graphs F satisfying πk-2(F)=k-k,and construct an infinite family of k-graphs with πk-2(F)=k-k.In 2016,Lenz and Mubayi posed the problem of characterizing the k-graphs F such that every sufficiently large(d,μ,∴)-dense k-graph H with d>0,v(F)| v(H)and minimum degree Ω(nk-1)contains a perfect F-tiling.In particular,they showed that all linear k-graphs satisfy this property.In the work of Lenz and Mubayi,they also constructed a sequence of(1/8,μ.∴)-dense 3-graphs Hn with minimum degree Ω(n2) having no perfect K2,2,2(3)-tilings.In the second part of this thesis,we first study k-graphs F such that every sufficiently large(d,μ,G)-dense k-graph H with d>0,v(F)| v(H)and minimum degreeΩ(nk-1)contains a perfect F-tiling,where G(?)2[k]can also be∴.We first reduce the perfect tiling problem in(d,μ,G)-dense k-graphs to a natural subproblem,namely the F-cover problem.Using this reduction,we can answer the question of Lenz and Mubayi for those F which are k-partite k-graphs,and for all 3-graphs F,separately.In addition,using this reduction,we get a result for K4(3)--factors.Secondly,we also study the perfect tiling of multipartite hypergraphs in uniformly dense hypergraphs.We prove that 1/8 is the density threshold for ensuring all 3-partite 3-graphs perfect tilings in(d,μ,∴)-dense 3-graphs given a minimum codegree condition Ω(n).Moreover,we show that one cannot replace the minimum codegree condition with a minimum vertex degree condition.Furthermore,we study the perfect tiling problem in(d,μ,∴)dense k-graphs with positive density d>0 and minimum s-degree condition Ω(nk-s),and give some sufficient characterizations for this type of problems.With these characterizations,for(d,μ,∴)-dense 3-graphs with minimum codegree condition Ω(n),we determine the optimal density threshold for each 3-partite 3-graph F to ensure perfect F-tiling in(d,μ,∴)-dense 3-graphs given a minimum codegree condition Ω(n).Finally,we also study perfect tilings of k-partite k-graphs in(d,μ,∴)-dense k-graphs(stronger quasi-random assumptions)with minimum codegree Ω(n).