Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 23, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Matija Bucic
How long a monotone path can one always find in any edge-ordering of the complete graph Kn? This appealing question was first asked by Chvátal and Komlós in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was n2/3-o(1). We almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length n1-o(1). This is joint work with Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran and Adam Zsolt Wagner.
Automatic MiSe System Software Version 1.4803M | admin login