Tony Johansson: On the resiliency of Dirac's Hamilton cycle theorem
Wed 2019-05-22 15.15 - 16.15
Room 306, House 6, Kräftriket, Department of Mathematics, Stockholm University ￼
Tony Johansson (Stockholm University)
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.