当前位置: 首页 > 科研学术 > 科研成果 > 正文

大数据理论研究中心——(常渝林, 韩杰, Yoshiharu Kohayakawa, Patrick Morris, Guilherme Oliveira Mota)随机扰动超图中的因子

【 发布日期:2022-10-14 】

随机扰动图模型由Bohman、Frieze和Martin提出,其目的在于研究少量随机边扰动的情况下对于图性质的影响。对于匹配在该模型下的存在性问题,Krivelevich、Kwan和 Sudakov证明了,在具有线性最小余度条件的k-一致超图中添加线性多条随机边可以保证以高概率出现完美匹配。他们提出了将最小余度条件换成其他更弱的度条件来研究此问题。注意到完美匹配是特殊的F-因子(取F为一条单边)。根据他们的问题,我们研究了使用最弱的度条件(即点度)时,随机扰动超图中因子的存在性问题。我们确定了一个最小点度为的k-一致超图中需要添加的最优的边数,可以保证以高概率出现一个F-因子,其中F可以取k-部k-一致超图、 以及Fano 平面等。特别地,当取F是一条单边时,该结果解决了 Krivelevich、Kwan和Sudakov提出的随机扰动超图中关于完美匹配的猜想。

本项研究工作是由山东大学常渝林博士后、北京理工大学韩杰教授、Universidade de São Paulo Yoshiharu Kohayakawa教授和Guilherme OliveiraMota教授、Freie Universität Berlin and Berlin Mathematical School PatrickMorris教授共同合作完成。相关论文见:Yulin Chang, Jie Han, Yoshiharu Kohayakawa, PatrickMorris, and Guilherme Oliveira Mota. Factorsin randomly perturbed hypergraphs, Random Structures and Algorithms, 60(2):153-165, 2022.