Title: Robust Hamiltonicity of Directed and Oriented Graphs via Vertex-Spread Distributions

Xuanang Li
School of Mathematics

Date: November 18, 2026
Time: 12:30 PM (EST)
Location: Skiles 114
Microsoft Teams Link: Join the meeting

Committee:
Prof. Tom Kelly (Advisor, School of Mathematics, Georgia Tech)
Prof. Xingxing Yu (School of Mathematics, Georgia Tech)
Prof. Will Perkins (School of Computer Science, Georgia Tech)
Prof. Xiaoyu He (School of Mathematics, Georgia Tech)
Prof. Rose McCarty (School of Mathematics, Georgia Tech)

Abstract:
Dirac's classical theorem states that every graph on n vertices with minimum degree at least n/2 contains a Hamilton cycle. This fundamental result has inspired extensive research on Hamiltonicity in directed and oriented graphs. In our work, we establish robust versions of Dirac-type theorems for Hamilton cycles in directed and oriented graphs using vertex-spread distributions.

We prove that there exists a constant C such that every sufficiently large oriented graph G on n vertices with minimum semidegree at least (3n-4)/8 admits a (C/n)-vertex-spread distribution on Hamilton cycles. We also establish a corresponding result for robust out-expanders with linear minimum semidegree. Building on the recent resolution of the Kahn–Kalai conjecture by Park and Pham, we further obtain the following robust Dirac result: if each edge is kept independently with probability at least Clog n/n, then the resulting random subgraph contains a Hamilton cycle for every sufficiently large oriented graph with minimum semidegree at least (3n-4)/8. Our work is the first robust Dirac-type results for oriented graphs.