【作者】 孙琳；

【导师】 王光辉； 李皓； 韩杰；

【作者基本信息】 山东大学 ， 数据科学， 2024， 博士

【摘要】 超图的极值问题是图论研究领域中的重要分支,主要研究的是超图中某些结构出现或者性质成立的临界条件.临界条件通常涉及超图中的某些参数,如边数、最小度、最大度、色数等达到一定的阈值时,必然能包含特定的结构.这类问题不仅内容丰富,还与加性组合、离散几何、概率论、代数等学科密切相关,在理论计算机方面也有广泛应用.本文的主要研究内容是超图中平铺存在的边条件问题以及哈密顿圈存在的最小度条件问题.匹配是图论中的基础研究对象,Erd(?)s在1965年提出了一个极值组合领域中的重要问题:给定n个点的k-一致超图H,如果H没有大小为s+1的匹配,那么H中至多会有多少条边?并猜想H的最大边数为(?).给定两个超图F和H,H中的一个F-平铺是指H中的一组顶点不相交的F的副本.F-平铺的大小指的是其中包含的F的副本数目.当F是一条边时,F-平铺即为匹配.因此,F-平铺是匹配的一个自然推广.对于k>b≥0,定义Yk,b是由两条恰好相交b个顶点的边构成的k-一致超图.Kühn和Osthus等人刻画了k-一致超图中包含一个Yk,b-平铺作为支撑子图的最小度条件.如果给定n个点的k-一致超图H,其不包含大小为s+1的Yk,b-平铺,那么H中至多有多少条边?本文猜想H的边数至多为(?).此猜想是上述Erd(?)s匹配猜想的推广,刻画了 k-一致超图中包含大小为s+1的Yb-平铺的边条件.本文证明了此猜想对于足够大的s和n≥(2(2k-b)2+1)(k-1)s+s是成立的,并应用超图正则引理将Yk,b-平铺问题转化成了由点不交的Yk,b和边构成的平铺问题,证实了此猜想对于k=3,b=2成立.本文将Yk,b-平铺的结果应用到了哈密顿圈问题中并得到相关结果.哈密顿圈问题是图论研究的核心课题之一,Dirac于1952年证明了图中哈密顿圈存在的最小度条件.近年来,学者们一直致力于将这一经典结果扩展到k-一致超图中.给定1≤l≤k,如果一个k-一致超图的顶点集存在一个圈序列,使得每条边都是由圈序列中k个连续的顶点组成,并且相邻的两条边恰好交于l个顶点,则称这个k-一致超图为一个l-圈.如果一个超图包含一个l-圈作为支撑子图,那么称它包含一个哈密顿l-圈.Katona和Kierstead于1999年提出超图Dirac阈值的问题,即刻画k-一致超图中哈密顿l-圈存在的最小d-度条件.对于最小余度的渐近阈值,目前已经解决.对于d=k-2,Bastos和Moto等人确定了在1≤l<k/2或l=k-1的条件下,哈密顿l-圈存在的渐近最优的最小(k-2)-度条件.对于 d≤k-3,Hàn、Han 和 Zhao 以及 Lang、Schacht和Vollc分别解决了偶数k≥6,l=k/2且l≤d≤k-1的情况以及d=k-3和l=k-1的情况.本文应用吸收方法以及基于格的交换吸收方法,结合超图正则引理,给出了对于d≥l和1≤l<k/2,哈密顿l-圈存在的最小d-度条件.在最小d-度条件下,本文将哈密顿l-圈的嵌入问题转化为Yk,2l-平铺的嵌入问题.本文进一步应用分数匹配覆盖原理,将问题转化为Yk,b-平铺在边条件下的嵌入问题,然后应用本文证明的关于Yk,b-平铺的结果,刻画了奇数k≥5,l=(k-1)/2且d=k-3时,或者满足k≥3,1≤d<2l≤k-1,2k-2l≥(2(2k-2l-d)2+1)(k-d-1)+1时,哈密顿l-圈存在的渐近最优的最小d-度阈值条件.更多还原

【Abstract】 Extremal problem in hypergraphs is an important research topic in graph theory,primarily focusing on the critical conditions for the appearance of certain structures or the validity of properties within hypergraphs.These critical conditions typically involve certain parameters in the hypergraph,such as the number of edges,minimum degree,maximum degree,chromatic number and so on,reaching a specific threshold,at which point certain specific structures are inevitably formed.This problem is not only rich in content but also closely related to additive combinatorics,discrete geometry,probability theory,algebra,and other disciplines.It also has widespread applications in theoretical computer science.This dissertation mainly studies the edge condition for the existence of tilings and the minimum degree condition for the existence of Hamilton cycles.Matching is a fundamental research object in graph theory.Erd(?)s proposed an important problem in the field of extremal combinatorics in 1965:Given a k-uniform hypergraph H on n vertices,if H does not have a matching of size s+1,then what is the maximum number of edges in H?He conjectured that the maximum number of edges in H is max(?).Given two k-uniform hypergraphs F and H,an F-tiling in H is a subgraph of H consisting of vertex-disjoint copies of F.The number of copies of F is called the size of the F-tiling.When F is a single edge,an F-tiling is known as a matching.Therefore,F-tiling is a natural generalization of matching.For k>b≥0,let Yk,b be the k-uniform hypergraph consisting of two edges intersecting in exactly b vertices.Kühn and Osthus,among others studied the minimum degree conditions guaranteeing the existence of a Yk,b-tiling as a spanning subhypergraph in a k-uniform hypergraph.If a k-uniform hypergraph H on n vertices does not have a Yk,b-tiling of size s+1,then what is the maximum number of edges in H?This dissertation conjectures that the maximum number of edges in H is max(?),which is a generalization of the Erd(?)s matching conjecture.It specifies the edge condition for a k-graph on n vertices to contain a Yk,b-tiling of size s.This dissertation verifies the conjecture for sufficiently large s and n≥(2(2k-b)2+1)(k-l)s+ s,and applies the hypergraph regularity lemma to transform the Yk,b-tiling problem into another tiling problem consisting of disjoint copies of Yk,b and edges to verify the conjecture for k=3,b=2.Moreover,we apply the results on Yk,b-tiling to obtain related results on the Hamilton cycle problem.The Hamilton cycle problem is one of the core topics in graph theory.In 1952,Dirac gave the minimum degree condition for the existence of Hamilton cycles in graphs.In recent years,researchers have been striving to extend this classic result to k-uniform hypergraphs.For 1≤l<k,a k-graph is called an l-cycle if there exists a cyclic ordering of its vertices such that every edge is composed of k consecutive vertices and two consecutive edges share exactly l vertices.A k-uniform hypergraph contains a Hamilton l-cycle if it contains an l-cycle as a spanning subhypergraph.For the asymptotic threshold of minimum co-degree,the problem has been solved.For d=k-2,Bastos,Moto and others established the asymptotically optimal minimum(k-2)-degree condition for the existence of Hamilton l-cycles under the conditions 1<l<k/2 or l=k-1.However,for d≤k-3,Hàn,Han and Zhao as well as Lang,Schacht and Volec have respectively solved the cases of k being even,k≥6,l=k/2,and k/2≤k-1 as well as the cases for d=k-3 and l=k-1.This dissertation applies the absorbing method and the lattice-based swapping-absorbing method,combining with the hypergraph regularity lemma.For d≥l and 1 ≤l<k/2 in k-uniform hyper graphs,we present minimum d-degree conditions for the existence of Hamilton l-cycles.This dissertation transforms the embedding problem of Hamilton l-cycles into a Yk,2l-tiling problem with minimum d-degree condition.Furthermore,we reduce the problem via a fractional matching-covering argument to finding a large Yk,b-tiling of given size under edge condition,so that we are able to apply the results on Yk,b-tiling we have showed.Specifically,the dissertation characterizes the minimum ddegree thresholds for the existence of Hamilton l-cycles when k is odd,k≥5,l=(k-l)/2,and d=k-3,or when k≥3,1≤d<2l≤k-1 and 2k-2l≥(2(2k-2l-d)2+1)(k-d-1)+ 1,which are asymptotically optimal.更多还原