Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, June 02, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Ulysse Schaller

Block-monotone subsequences

(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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login