- Series
- Graph Theory Seminar
- Time
- Tuesday, September 28, 2021 - 3:45pm for
- Location
- Skiles 005
- Speaker
- Misha Lavrov – Kennesaw State University – mlavrov@kennesaw.edu – http://facultyweb.kennesaw.edu/mlavrov/
- Organizer
- Anton Bernshteyn
This talk is motivated by the Erdős–Szekeres theorem on monotone subsequences: given a sequence of $rs+1$ distinct numbers, there is either a subsequence of $r+1$ of them in increasing order, or a subsequence of $s+1$ of them in decreasing order.
We'll consider many related questions with an algorithmic flavor, such as: if we want to find one of the subsequences promised, how many comparisons do we need to make? What if we have to pre-register our comparisons ahead of time? Does it help if we search a longer sequence instead?
Some of these questions are still open; some of them have answers. The results I will discuss are joint work with Jozsef Balogh, Felix Clemen, and Emily Heath at UIUC.