Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 30, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Miloš Trujić
In 1998, Komlós, Sárközy, and Szemerédi confirmed the famous Pósa-Seymour conjecture stating that for every positive integer k, every sufficiently large graph with minimum degree at least kn/(k + 1) contains the k-th power of a Hamilton cycle. Very recently, Dudek, Reiher, Ruciński, and Schacht showed that if the minimum degree of a graph is at least (k/(k + 1) + o(1))n then adding O(n) random edges on top almost surely results in a graph which contains the (k + 1)-st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely that in the same setting one can almost surely find the (2k + 1)-st power. This is a joint work with Rajko Nenadov.
Automatic MiSe System Software Version 1.4803M | admin login