On Embedding (Hyper) Graphs And Related Problems

Embedding problem is a classic problem in graph theory.In this article,we inves-tigate the problem of embedding(hyper)graphs and some related problems,such as the minimum degree thresholds for perfect graph packings,minimum H-decomposition of hypergraphs,and the spectral extremal problem of embedding trees.In section 1,we introduce some basic definitions and background of our research.Given two k-graphs F and H,a perfect F-tiling(also called an F-factor)in H is a set of vertex disjoint copies of F that together cover the vertex set of H.Let tk-1(n,F)be the smallest integer t such that every k-graph H on n vertices with minimum code-gree at least t contains a perfect F-tiling.Mycroft(JCTB,2016)determined an asymp-totic value of tk-1(n,F)for k-partite k-graphs F,and moreover the error term o(n)in tk-i(n,F)is tight for complete k-partite k-graphs.Mycroft also conjectured that the error term can be replaced by a constant that depends only on F.In this paper,we improve the error term of MycroCtVs result to a sub-linear term when F=K3(m),the complete 3-partite 3-graph with each part of size m.We also show that the sub-linear term is tight for K3(2).The result also provides another family of counterexamples to Mycroft’s conjecture(Gao,Han,Zhao(arXiv,2016)gave a family of counterexamples when H is a k-partite k-graph with some restrictions.)Finally,we show that Mycroft’s conjecture holds for generalized 4-cycle C43(the 3-graph on six vertices and four distinct edges A,B,C,D with A U B=C U D and A∩B＝C ∩ D＝(?)),i.e.we determine the exact value of t2(n,C4).In section 3,we investigate t1(n,F)for two 3-graphs of small order.Let C63 be a 3-graph on 6 vertices[6],where the edge set consists of{123,345,561}.Han,Zang and Zhao(JCTA,2017)determined an asymptotic value of t1(n,K)for 3-partite 3-graphs K.Their results imply the asymptotic value of t1(n,C6),and we determine the exact value of C63.Let K43-e be the 3-graph obtained by deleting any edge from the complete graph K43.We show a lower bound of t1(n,K43-e),disproving a conjecture of Han et al.(CPC,2017).Let 4k(n,H)be the smallest integer such that,for all k-graphs G on n vertices,the edge set E(G)can be partitioned into at most φk(n,H)parts,of which every part either is a single edge or forms an k-graph isomorphic to H.The function φk(n,H)has been well studied in literature,but for the case k)3,the problem that determining the value of φk(n,H)is widely open.Sousa(2010)gave an asymptotic value of φk(n,H)when H is a k-graph with exactly 2 edges,and determined the exact value of φk(n,H)in some special cases.In section 4,we first give the exact value of φk(n,H)when H is a k-graph with exactly 2 edges,which improves Sousa’s result.Second we determine the exact value of φk(n,H)when H is a k-graph consisting of exactly r independent edges.Motivated by Erdos-Sos conjecture,Nikiforov(LAA,2010)conjectured that for a given integer k,any graph G of sufficiently large order n with spectral radius μ(G)≥μ(Sn,k)contains all trees of order 2k+2,unless G=Sn,k,where Sn,k =Kk(?)denotes the join of a complete graph of order k and an empty graph of order n-k.In section 5,we show that the conjecture is true for trees of diameter at most four.