Erd\H{o}s-Szekeres On-Line

Abstract: In 1935, ErdH{o}s and Szekeres proved that

(m - 1) (k - 1) + 1

is the minimum number of points in the plane which definitely contain an increasing subset of

m

points or a decreasing subset of

k

points (as ordered by their

x

-coordinates). We consider their result from an on-line game perspective: Let points be determined one by one by player A first determining the

x

-coordinate and then player B determining the

y

-coordinate. What is the minimum number of points such that player A can force an increasing subset of

m

points or a decreasing subset of

k

points? We introduce this as the ErdH{o}s-Szekeres on-line number and denote it by

e x t E S O (m, k)

. We observe that

e x t E S O (m, k) < (m - 1) (k - 1) + 1

for

m, k g e 3

, provide a general lower bound for

e x t E S O (m, k)

, and determine

e x t E S O (m, 3)

up to an additive constant.

This page was built for publication: Erd\H{o}s-Szekeres On-Line