Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 16, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Shoham Letzter (ITS)
Given a tournament on n vertices, it is not hard to see that there is a 2-colouring of the edges such that the longest directed path has length O(n/sqrt(log n)). We show that for almost all tournaments, this bound is tight. I.e., for almost all tournaments, given any 2-colouring, there is a monochromatic directed path of length at least Omega(n/sqrt(log n)). This is joint work with Matija Bucić and Benny Sudakov.
Automatic MiSe System Software Version 1.4803M | admin login