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

Tid: On 2019-05-22 kl 15.15 - 16.15

Föreläsare: Tony Johansson (Stockholm University)

Plats: Room 306, House 6, Kräftriket, Department of Mathematics, 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.            
Innehållsansvarig:webmaster@math.kth.se
Tillhör: Institutionen för matematik
Senast ändrad: 2019-05-17