# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 23.02.2012 at 12:20 in S6, there is the following noon lecture:

# Higher-order Erdõs-Szekeres theorems

## Marek Eliáš

## Abstract

Let P=(p_1,p_2,...,p_N) be a sequence of points in the plane, where p_i=(x_i,y_i) and x_1<x_2<...<x_N. A famous 1935 Erdos-Szekeres theorem asserts that every such P contains a monotone subsequence S of sqrt(N) points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Omega(log N) points.

Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a (k+1)-tuple K\subseteq P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k+1)-tuple. Then we say that S\subseteq P is kth-order monotone if its (k+1)-tuples are all positive or all negative.

We investigate quantitative bound for the corresponding

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010