Sufficient conditions for Hamilton cycles: old results and new viewpoints
数学学科创建110周年系列报告
报告题目(Title)： Sufficient conditions for Hamilton cycles: old results and new viewpoints
报告人(Speaker)：宁博 教授 （南开大学）
地点(Place)：后主楼1124
时间(Time)：2025 年 4 月 11 日（周五） 16：00-17：00
邀请人(Inviter)：徐敏
报告摘要
As an extension of Ore's condition on Hamilton cycles, Fan in 1984 proved that every 2-connected graph $G$ on $n\geq 3$ vertices is hamiltonian if $G$ satisfies Fan's condition, i.e., for every pair of vertices $x,y\in V(G)$, the fact $d(x,y)=2$ implies that $\max\{d(x),d(y)\}\geq \frac{n}{2}$. Moreover, Fan constructed a family of graphs called $F_{4r}$ which satisfies Fan’s condition but can imply its n-closure is not complete. In this talk, we first report a structural theorem for the new graph $G'$ which is obtained from a graph $G$ satisfying Fan's condition, by adding a series of new edges whose two end vertices are not adjacent and with degree sum at least $|G|$, and finally doing the Ryjacek's claw-free closure of the resulting graph. Our theorem shows that this new graph $G'$ (in the spirit of closure theory) looks like the structure of $F_{4r}$. We also show that the lower bound of the number of edges in a graph satisfying Fan's condition satisfies $\frac{n^2}{8}+Ώ(n)$, which is motivated by a classical theorem of Bondy. Moreover, this bound is best possible by considering the graph $F_{4r}$. With these two theorems in mind, we can see the graph $F_{4r}$ plays an important role in reasoning Fan's condition for Hamilton cycles. Besides the results mentioned above, we shall give a brief introduction to several different topics on Hamiltonicity of graphs.
主讲人简介
宁博，南开大学计算机学院、密码与网络空间安全学院博士生导师、南开大学百名青年学科带头人（运筹学与控制论、图论方向、A类）、国家高水平青年人才。研究方向是图论，在离散数学类主流期刊JCTB、Combinatorica等发表论文50余篇，在图谱领域发表综述论文1篇；主持完成国家自然科学基金3项，主持在研面上项目1项，参与国家重点研发计划2项。承担和参与科技部重点专项、中国工程院战略咨询项目、密码学国家重点实验室等密码网安项目5项。曾在第九届世界华人数学家大会作45分钟报告，并荣获第八届中国运筹学会青年科技奖。
