Beijing Institute of Mathematical Sciences and Applications Beijing Institute of Mathematical Sciences and Applications

  • About
    • President
    • Governance
    • Partner Institutions
    • Visit
  • People
    • Management
    • Faculty
    • Postdocs
    • Visiting Scholars
    • Administration
    • Academic Support
  • Research
    • Research Groups
    • Courses
    • Seminars
  • Join Us
    • Faculty
    • Postdocs
    • Students
  • Events
    • Conferences
    • Workshops
    • Forum
  • Life @ BIMSA
    • Accommodation
    • Transportation
    • Facilities
    • Tour
  • News
    • News
    • Announcement
    • Downloads
About
President
Governance
Partner Institutions
Visit
People
Management
Faculty
Postdocs
Visiting Scholars
Administration
Academic Support
Research
Research Groups
Courses
Seminars
Join Us
Faculty
Postdocs
Students
Events
Conferences
Workshops
Forum
Life @ BIMSA
Accommodation
Transportation
Facilities
Tour
News
News
Announcement
Downloads
Qiuzhen College, Tsinghua University
Yau Mathematical Sciences Center, Tsinghua University (YMSC)
Tsinghua Sanya International  Mathematics Forum (TSIMF)
Shanghai Institute for Mathematics and  Interdisciplinary Sciences (SIMIS)
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.
Organizers
Jie Ma , Benjamin Sudakov
Speaker
Jaehoon Kim
Time
Tuesday, October 21, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899 (BIMSA)
Abstract
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.

Beijing Institute of Mathematical Sciences and Applications
CONTACT

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

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

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

Copyright © Beijing Institute of Mathematical Sciences and Applications

京ICP备2022029550号-1

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