Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 15, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Domagoj Bradac
The Pósa-Seymour conjecture asserts that every graph on n vertices with minimum degree at least (1 − 1/(r + 1))n contains the r-th power of a Hamilton cycle. Komlós, Sárközy and Szemerédi famously proved the conjecture for large n. The notion of discrepancy appears in many areas of mathematics, including graph theory. In this setting, a graph G is given along with a 2-coloring of its edges. One is then asked to find in G a copy of a given subgraph with a large discrepancy, i.e., with many more edges in one of the colors. For r ≥ 2, we determine the minimum degree threshold needed to find the r-th power of a Hamilton cycle of large discrepancy, answering a question posed by Balogh, Csaba, Pluhár and Treglown. Notably, for r ≥ 3, this threshold matches the minimum degree requirement of the Pósa-Seymour conjecture.
Automatic MiSe System Software Version 1.4803M | admin login