Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 02, 2022, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Ulysse Schaller
(This is from a paper by Andrew Suk and Ji Zeng.) A famous theorem of Erdös and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least n^(1/2). Here, we prove a positive fraction version of this theorem. For n > (k − 1)^2, any sequence A of n distinct real numbers contains a collection of subsets A_1, ..., A_k appearing sequentially, all of size s >= cst*(n/k^2), such that every subsequence (a_1, ..., a_k), with a_i in A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1, ..., A_k) described above is called block-monotone of depth k and block-size s. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k^2 log k) block-monotone subsequences of depth at least k, upon deleting at most (k − 1)^2 entries.
Automatic MiSe System Software Version 1.4803M | admin login