F-factors In Quasi-random Hypergraphs

Quasi-random(hyper)graphs are explicit(hyper)graphs exhibiting various properties that resemble the binomial random(hyper)graph,and the study of them leads to major developments of extremal combinatorics,such as,Ramsey theory,expander graphs,and property testing,etc.Unlike random graphs,it is relatively easy to verify that a particular family of graphs possess some property in this class.Turán-type problems study the maximum edge density in discrete structures given a family of forbidden subpatterns of fixed-order.The Turán problems for hypergraphs are notoriously difficult,and an important reason is the emergence of certain quasi-random F-free hypergraphs serving as extremal examples,which clearly diverges from the graph case as quasi-random graphs with positive density contain all fixed-order graphs as subgraphs.This suggests the significance of the study of subgraph emergence in quasi-random k-graphs.In this thesis we focus on a significant strengthening of the Turán-type problem-the Ffactor problem,in quasi-random k-graphs.Given two k-graphs(k-uniform hypergraphs)F and H,if H contains a k-graph F’ which is isomorphic to F as a subhypergraph,then we say F’ is a copy of F in H.Given k≥ 2 and two k-graphs F and H,an F-factor in H is a set of vertex disjoint copies of F that together cover the vertex set of H.Let V(H)and E(H)be the vertex set and edge set of H respectively.Let N(υ)denote the neighbor set of υ.Given n≥ k≥2 and 0<μ,p<1,let H be a k-graph with n vertices.We say that H is(p,μ)-dense if for all X1,…,Xk?V(H),eH(X1,…,Xk)≥p|X1|…|Xk|-μnk where eH(X1,…,Xk)is the number of(x1,…,xk)∈X1×…×Xk such that{x1,…,xk}∈E(H).We say that H is an(n,p,μ)k-graph if H has n vertices and is(p,μ)-dense.Lenz and Mubayi[J.Combin.Theory Ser.B,2016]studied the F-factor problem in(n,p,μ)k-graphs with minimum degreeΩ(nk-1).They posed the problem of characterizing the k-graphs F such that every sufficiently large(n,p,μ)k-graph with constant edge density and minimum degree Ω(nk-1)contains an F-factor,and in particular,they showed that all linear k-graphs satisfy this property.For factor problems,a necessary condition is that every vertex of H is covered by at least one copy of F.We say a set of copies of F is an F-cover if it covers the vertex set of H.In the thesis we prove a general theorem on F-factors which reduces the F-factor problem of Lenz and Mubayi to F-cover problem.As long as the quasi-randomness and degree condition force the appearance of an F-cover in H,H indeed has an F-factor.By using this result,we answer the question of Lenz and Mubayi for those F which are k-partite k-graphs,and for all 3-graphs F,separately.A characterization for k-partite k-graphs F is the following:there exists υ*∈ V(F)such that |e∩e’|≤1 for any two edges e,e’ withυ*∈e and υ*?e’.We introduce a formal definition of Turán densities in(p,μ)-dense kgraphs.Given a k-graph F,we define π∴(F)=sup{p∈[0,1]:for every μ>0 and n0∈N,there exists an F-free(n,p,μ,)k-graph H with n≥n0｝.We give a characterization of the 3-graphs as follows:(1)π∴(F)=0;(2)there is a vertex υ*∈V(F)and a partition P={X,Y,{υ*｝ of V(F)such that N(υ*)?X×Y and for any x∈X and y∈Y,N(x),N(y)and N(υ*)are pairwise disjoint.