Skip to main content
To KTH's start page To KTH's start page

Tony Johansson: On the resiliency of Dirac's Hamilton cycle theorem

Time: Wed 2019-05-22 15.15 - 16.15

Location: Room 306, House 6, Kräftriket, Department of Mathematics, Stockholm University 

Participating: Tony Johansson (Stockholm University)

Export to calendar

Abstract: A Hamilton cycle in a finite graph G is a cycle that passes through every vertex exactly once. A necessary condition for G to contain a Hamilton cycle is clearly that G has minimum degree at least 2, while the best possible sufficient minimum degree condition is n/2, where n denotes the number of vertices (Dirac's theorem). In random graph theory, minimum degree 2 is often both a necessary and sufficient condition for containing a Hamilton cycle. I will explain and explore this informal claim, considering the random graph G(p) obtained by
independently deleting any edge of G with probability p. If G satisfies Dirac's condition, it turns out that G(p) contains a Hamilton cycle if and only if it has minimum degree 2, in a strong sense.