Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 26, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Matija Bucic
The classical Erdos-Szekeres theorem dating back almost a hundred years states that any sequence of (n-1)2+1 distinct real numbers contains a monotone subsequence of length n. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They defined the concept of a monotone and a lex-monotone array and asked how large an array one needs in order to be able to find a monotone or a lex-monotone subarray of size n times n times ... times n. Fishburn and Graham obtained Ackerman-type bounds in both cases. We significantly improve these results. Regardless of the dimension we obtain at most a triple exponential bound in n in the monotone case and a quadruple exponential one in the lex-monotone case. This is joint work with Benny Sudakov and Tuan Tran.
Automatic MiSe System Software Version 1.4803M | admin login