2018/04/16 by Kirk Boyer, Lauren M. Nelsen, Boyer, Kirk +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #Graph Theory and Algorithms #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1804.05952
openalex publication_date 2018/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1935, Erdő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 Erdős-Szekeres on-line number and denote it by ESO(m,k). We observe that ESO(m,k) < (m-1)(k-1)+1 for m,k ≥ 3, provide a general lower bound for ESO(m,k), and determine ESO(m,3) up to an additive constant.