【数学与统计及交叉学科前沿论坛------高端学术讲座第156场】

报告题目：Dirac-type condition for Hamilton-generated graphs

报 告 人：侯新民教授 中国科学技术大学

报告时间：5月17日星期六16:00-17:00

报告地点：阜成路西区综合楼1116会议室

报告摘要：The cycle space $\mathcal{C}(G)$ of a graph $G$ is defined as the linear space spanned by all cycles in $G$. For an integer $k\ge 3$, let $\mathcal{C}_k (G)$ denote the subspace of $\mathcal{C}(G)$ generated by the cycles of length exactly $k$. A graph $G$ on $n$ vertices is called Hamilton-generated if $\mathcal{C}_n (G) = \mathcal{C}(G)$, meaning every cycle in $G$ is a symmetric difference of some Hamilton cycles of $G$. Heinig (European J. Combin., 2014) showed that for any $\sigma >0$ and sufficiently large              odd $n$, every $n$-vertex graph with minimum degree $(1+ \sigma)n/2$ is Hamilton-generated. He further posed the question that whether the minimum degree requirement could be lowered to the Dirac threshold $n/2$. Recent progress by Christoph, Nenadov, and Petrova~(arXiv:2402.01447) reduced the minimum degree condition to $n/2 + C$ for some large constant $C$. In this talk, we resolve Heinig's problem completely by proving that for sufficiently large odd $n$, every Hamilton-connected graph $G$ on $n$ vertices with minimum degree at least $(n-1)/2$ is Hamilton-generated. Moreover, this result is tight for the minimum degree and the Hamilton-connected condition. The proof relies on the parity-switcher technique introduced by Christoph, et al in their recent work, as well as a classification lemma that strengthens a previous result by Krivelevich, Lee, and Sudakov~(Trans. Amer. Math. Soc., 2014).

报告人简介：侯新民，中国科学技术大学 教授，博士生导师。2002年博士毕业于大连理工大学。2009到2010在西弗吉尼亚大学学术访问，2013到2014在佐治亚理工大学学术访问。研究领域包括结构图论、极值图论及图论应用，已发表学术论文70余篇，主持完成国家自然科学基金5项，省部级项目2项，参与科技部重点专项2项。