【作者】 王斌；

【导师】 王光辉； 李皓；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2024， 博士

【摘要】 极值组合是近几十年来组合数学中发展最为蓬勃的一个分支,近年来受到了极大的关注,它在计算机科学,网络设计和编码设计中有着广泛的应用,研究的是特定条件下的特定组合结构的最大或最小的规模.极值组合有众多研究对象,例如有向图,随机图,超图,整数集,素数集,集合,边染色图等,研究的局部结构也有多样性,例如匹配,团,圈,树,支撑子图,相交集,等差数列,方程解,彩虹结构等.特别地,极值图论是极值组合中的重要分支,主要研究图的全局特性如何影响其局部子结构.一个k-图系统H={H_i}_i∈[m]是一些定义在相同顶点集V上的k-图的集合,这m个图不一定是不同的.给定一个顶点集V上的k-图系统H={H_i}_i∈[m]和顶点集V上的k-图H,如果存在一个单射φ:E（H）→[m],使得对于每个e∈E（H）,都有e∈E(H_φ（e）,则称H是H-彩虹的本文主要进行了如下三部分的研究.（1）研究超图系统中的彩虹哈密尔顿圈的存在性.Dirac定理有很多变形.第一种是在图系统中研究彩虹哈密尔顿性,第二种是在超图中研究哈密尔顿性.循着同样的思路,一个自然的问题就是在特定条件下,能否在超图系统中找到彩虹哈密尔顿圈?本文证明了如下结论.对任意的k≥3,γ>0,充分大的n ∈ N和n-顶点的k-图系统H={H_i}_i∈[n],如果δ_k-1（H_i）≥（1/2+γ）_n对任意的i∈[n]成立,则存在一个H-彩虹哈密尔顿圈.进一步地,学者们致力于刻画保证哈密尔顿圈存在的（k-2）-度条件.Lang和Sanhueza-Matamala以及Polcyn,Reiher,R?dl和Schülke独立证明了对任意的γ>0和充分大的n∈N,每个具有（?）的n-顶点的k-图H都包含一个哈密尔顿圈.但是,给出上述结果的彩虹版本要困难得多.Gupta,Hamann,Müyesser,Parczyk和Sgueglia将以下问题称作“一个众所周知的Dirac-型结果,其彩虹版本尚未得证”,并且“证明这一结果将是一个有趣的挑战”:给定一个3-图系统H=｛H_i｝_i∈[n],若每个图有最小1-度条件,则是否存在一个H-彩虹哈密尔顿圈?本文提出了扩展哈密尔顿框架结构,解决了上述问题,并得出了k≥3时的一般结论.（2）研究超图系统中彩虹匹配的存在性.设c_k,d是k-图中存在完美分数匹配的最小d-度阈值,即对任意的ε>0和充分大的n∈N,每个具有δ_d（H）≥(c_k,d+ε)（?）的n-顶点的k-图H都包含一个完美分数匹配.已知每个具有δd（H）≥(max{c_k,d,1/2]+o（1）)（?）的n-顶点的k-图H都有一个完美匹配,该结果是渐近最优的.本文证明了k-图中有完美匹配的最小d-度条件也会渐近保证k-图系统中包含彩虹完美匹配,其中d ∈[k-1].更一般地,本文还可以给出解决超图系统中彩虹因子存在性问题的一般框架.（3）研究正常边染色图中彩虹长圈的存在性.1989年,Andersen猜想任意正常边染色的K_n都有n-1个点的彩虹路.Akbari,Etesami,Mahini和Mah-moody证明了任意正常边染色的K_n有长度至少为n/2-1的彩虹圈.Gyárfás,Ruszinkó,Sárk?zy 和 Schelp 将其改进到（4/7-o（1））n.Gebauer 和 Mousset 及Chen和Li独立证明了任意正常边染色的K_n包含长度为(3/4-o（1）n的彩虹圈.Alon,Pokrovskiy和Sudakov证明了任意正常边染色的K_n包含长度为n-O(n^3/4)的彩虹圈,误差项已由Balogh和Molla改进.本文证明了任意正常边染色的K_n,n都有长度至少为n-28n^3/4的彩虹圈,其中n是充分大的.这一界是渐近最优的,因为正常边染色的K_n,n可能只出现n种颜色且每个颜色类为完美匹配.更多还原

【Abstract】 Extremal Combinatorics is one of the most vigorous branch of Combinatorial Mathematics in recent decades and it has been widely used in Computer Science,Network Design and Coding Design.It focuses on determining the maximum or minimum possible size of certain combinatorial structures,subject to certain conditions.The host sets could be graphs,digraphs,random graphs,hypergraphs,integers,primes,sets,edge-colored graphs and so on.The local structures could be matchings,cliques,cycles,trees,spanning subgraphs,intersecting families,arithmetic progressions,solutions for some equations,rainbow subgraphs and so on.In particular,Extremal Graph Theory is a significant branch of Extremal Combinatorics,which primarily explores how the overall properties of a graph influence its local structures.A k-graph system H={H_i}_i∈[m]is a collection of not necessarily distinct k-graphs on the same vertex set V.For a k-graph system H={H_i}_i∈[m]on V,a graph H on V is H-rainbow if there exists an injection φ:E（H）→[m]such that e∈E(H_φ（e）)for each e ∈ E（H）.This thesis presents a three-part study.（1）We study the existence of rainbow Hamilton cycles in hypergraph systems.Dirac’s theorem has many variants.Firstly,it was generalized in graph systems.Secondly,it was generalized in hypergraphs.Following the same idea,we aim to find a rainbow Hamilton cycle in a hypergraph system and derive the following conclusion.Given k≥ 3,γ>0,sufficiently large n and an n-vertex k-graph system H={H_i}_i∈[m],if δ_k-1（H_i）≥（1/2+γ）_n for each i ∈[n],then there exists an H-rainbow Hamilton cycle.Further,scholars devoted to characterizing the（k-2）-degree condition for the existence of a Hamilton cycle.Lang and Sanhueza-Matamala,Polcyn,Reiher,R?dl and Schülke independently proved that for any γ>0 and sufficiently large n,every n-vertex k-graph withδk-2（H）≥（5/9+γ）（?）contains a Hamilton cycle.However,the rainbow version of the above conclusion is much more difficult.Gupta,Hamann,Müyesser,Parczyk,and Sgueglia mentioned the following problem as“there is a well-known Dirac-type result whose rainbow version is missing”and "it would be an interesting challenge to obtain this result":Given a 3-graph system H={H_i}_i∈[n]with minimum 1-degree condition of each Hi,does there exist an H-rainbow Hamilton cycle?We develop a sequentially Hamilton framework,which is of independent interest,settling the above problem,and draw the general conclusion for any k≥3.（2）We study the existence of rainbow perfect matchings in hypergraph systems.Let c_k,d be the minimum d-degree threshold for perfect fractional matchings in k-graphs,namely,for every ε>0 and sufficiently large n ∈ N,every n-vertex k-graph H with δd（H）≥(c_k,d+ε)（?）contains a perfect fractional matching.It is known that every n-vertex k-graph H with δd（H）≥(max{c_k,d,1/2}+o（1）)（?）has a perfect matching,and this condition is asymptotically best possible.We proved that a minimum d-degree condition forcing a perfect matching in a k-graph also asymptotically forces a rainbow perfect matching in a k-graph system for d∈E[k-1].More generally,a general framework for finding rainbow factors in hypergraph systems can also be given.（3）We study the existence of long rainbow cycles in properly edge-colored graphs.In 1989,Andersen conjectured that every proper edge-coloring of K_n admits a rainbow path which omits only one vertex.Akbari,Etesami,Mahini and Mahmoody proved that every properly edge-colored K_n has a rainbow cycle of length at least n/2-1.Gyárfás,Ruszinkó,Sárk?zy improved this to（4/7o（1））n.Gebauer and Mousset,and Chen and Li independently proved that any properly edge-colored K_n contains a rainbow cycle of length（3/4-o（1））n.Alon,Pokrovskiy and Sudakov demonstrated that any properly edge-colored K_n contains a rainbow cycle of length n-O(n^3/4),the error term has been improved by Balogh and Molla.We proved that every properly edge-colored K_n,n contains a rainbow cycle of length at least n-28n^3/4 for sufficiently large n.The bound above is asymptotically optimal as each color class could be a perfect matching of K_n,n and only n colors occur in E(K_n,n).更多还原