超图和随机超图的关于哈密顿圈的Dirac类型的问题

Over the last decade, with the increasing popularity of computer and scale of the integrated circuits, the research on the hypergraph theory and its applications has become a new hotspot. In 1952, Dirac proved a celebrated theorem stating that if the minimum degree in an n-vertex graph G is at least n/2 then G contains a Hamilton cycle. In 1999, Katona and Kierstead initiated a new stream of research devoted to studying similar questions for hypergraphs, and subsequently, for perfect matchings. Such problems are called Dirac-type problems. Recently, Dirac's theorem was extended to hypergraphs(2010) and random graphs(2012), respectively. However, the study on the Dirac-type problems on random hypergraph is little and there are also many Dirac-type problems on hypergraph which have not been considered. The main problems of this project are to consider Dirac-type problems on random k-uniform hypergraph and other Dirac-type problems on hypergraphs. As they are the important basis problems of random hypergraph theory, the study will be the foundation for the further development of the hypergraph theory and provides theoretical guarantees for the application of hypergraph theory. The study on this subject has a certain theoretical and practical value.

近十几年来，随着电子计算机的普及和集成电路规模的增大，超图理论及其应用的研究已成为一个新的研究热点。自1999年Katona和Kierstead给出超图哈密顿圈的一种新的结构化定义以来，超图的哈密顿问题，作为超图理论最基本的也是最具挑战的问题之一，吸引了很多世界一流图论和随机图论大师的关注。首先受到关注的问题之一就是超图中是不是也有类似于Dirac定理(一个图是哈密顿图的充分条件是该图的最小度至少是顶点数的一半)的结论。这类问题被称为Dirac类型的问题。最近，Dirac定理分别被推广到超图(2010)和随机图(2012)，但总的来说，超图的Dirac类型的问题的研究还处于初步阶段。本项目考虑的是随机超图中关于哈密顿圈的Dirac类型的问题和超图中关于一个d子集的最小度的Dirac类型的问题。目前为止，这两方面的研究结果几乎没有。本项目属于超图理论的基础理论研究，具有一定的理论与应用价值。

研究一个图性质的稳健性（robustness）是最近几年的热门问题之一。其中最为经典的结果就是Dirac‘s 定理：完全图Kn的每个顶点去掉不超过[n/2]的边仍然具有哈密顿性质。2012 年Lee 和Sudakov [7]把Dirac 定理推广到随机图，证明了在随机图G(n,p)中，如果p>>logn/n, 那么几乎所有G(n,p)的每个最小度不小于（1/2+o(1))np 的子图都是哈密顿图。但是，关于随机超图的哈密顿Berge圈的Dirac 类型的问题的研究结果几乎有甚至连阈函数问题都没有被解决 随机k 一致超图Hk (n, p) 中关于哈密顿Berge圈性质的稳健性的问题。本项目的主要研究内容就是研究随机超图的哈密顿Berge圈的Dirac 类型的问题。目前，（一）我们已经将上面的两个经典结果推广到随机超图的哈密顿Berge圈性质上：在随机k一致超图H_k(n,p)中，如果p>>logn/n^{k-1}, 那么几乎所有H_k(n,p)的每个最小度不小于（1/2^{k-1}+o(1)){n-1\choose k}p 的子图都有一个哈密顿Berge圈，并且两个界在某种程度上都是最好的。我们的结果顺便也解决了随机k一致超图 的阈函数问题：logn/n^{k-1} 是H_k(n,p) 的Hamiltonian Berge cycle性质的阈函数。另外，我们还将上面的结论中的度条件推广到不相容系统，也得到了相应的结果，其中的两个界在某种程度上也是最好的。Berge cycle 是最早最经典的一种超图圈定义，但是由于其结构比较复杂，研究难度比较大。关于现代图论关于Berge cycle的研究较少。我们的结果解决了随机k一致超图 的Hamiltonian Berge cycle 理论中比较关键的两个问题，这对于该理论的进一步发展有着破冰的作用，和比较重要的理论应用价值。