北京雁栖湖应用数学研究院 北京雁栖湖应用数学研究院

  • 关于我们
    • 院长致辞
    • 理事会
    • 协作机构
    • 参观来访
  • 人员
    • 管理层
    • 科研人员
    • 博士后
    • 来访学者
    • 行政团队
    • 学术支持
  • 学术研究
    • 研究团队
    • 公开课
    • 讨论班
  • 招生招聘
    • 教研人员
    • 博士后
    • 学生
  • 会议
    • 学术会议
    • 工作坊
    • 论坛
  • 学院生活
    • 住宿
    • 交通
    • 配套设施
    • 周边旅游
  • 新闻
    • 新闻动态
    • 通知公告
    • 资料下载
关于我们
院长致辞
理事会
协作机构
参观来访
人员
管理层
科研人员
博士后
来访学者
行政团队
学术支持
学术研究
研究团队
公开课
讨论班
招生招聘
教研人员
博士后
学生
会议
学术会议
工作坊
论坛
学院生活
住宿
交通
配套设施
周边旅游
新闻
新闻动态
通知公告
资料下载
清华大学 "求真书院"
清华大学丘成桐数学科学中心
清华三亚国际数学论坛
上海数学与交叉学科研究院
BIMSA > Research seminar in Discrete Mathematics Hamilton cycles in pseudorandom graphs: Dirac’s theorem and approximate decompositions.
Hamilton cycles in pseudorandom graphs: Dirac’s theorem and approximate decompositions.
组织者
马杰 , 本杰明·苏达科夫
演讲者
Jaehoon Kim
时间
2025年10月21日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899 (BIMSA)
摘要
Dirac’s classical theorem asserts that, for $n\ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian. Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, Kühn, Lo, Osthus and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash‑Williams conjecture.
In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs.
We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield asymptotically optimal resilience and Hamilton‑decomposition results in sparse pseudorandom graphs. In particular, our results imply that for every fixed $\gamma>0$, there exists a constant $C>0$ such that if $G$ is a spanning subgraph of an $(n,d,\lambda)$-graph satisfying
$\delta(G)\ge\bigl(\tfrac{1}{2}+\gamma\bigr)d$ and $d/\lambda\ge C,$ then $G$ must contain a Hamilton cycle.

Secondly, we show that for every $\varepsilon>0$, there is $C>0$ so that any $(n,d,\lambda)$-graph with $d/\lambda\ge C$ contains at least $\bigl(\tfrac{1}{2}-\varepsilon\bigr)d$ edge‑disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $\bigl(\tfrac12+\varepsilon\bigr)d$ such cycles. All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs. This is joint work with Nemanja Draganic, Hyunwoo Lee, David Munha Correia, Matias Pavez-Signe and Benny Sudakov.

北京雁栖湖应用数学研究院
CONTACT

No. 544, Hefangkou Village Huaibei Town, Huairou District Beijing 101408

北京市怀柔区 河防口村544号
北京雁栖湖应用数学研究院 101408

Tel. 010-60661855 Tel. 010-60661855
Email. administration@bimsa.cn

版权所有 © 北京雁栖湖应用数学研究院

京ICP备2022029550号-1

京公网安备11011602001060 京公网安备11011602001060