### Two player game variant of the Erdős-Szekeres problem

*Parikshit Kolipaka, Sathish Govindarajan*

#### Abstract

The classical Erdős-Szekeres theorem states that a convex
k-gon exists in every sufficiently large point set. This
problem has been well studied and finding tight asymptotic bounds is
considered a challenging open problem. Several variants of the
Erdős-Szekeres problem have been posed and studied in the last
two decades. The well studied variants include the empty convex
k-gon problem, convex k-gon with specified
number of interior points and the chromatic variant. In this paper, we
introduce the following two player game variant of the
Erdős-Szekeres problem: Consider a two player game where each
player playing in alternate turns, place points in the plane. The
objective of the game is to avoid the formation of the convex k-gon
among the placed points. The game ends when a convex k-gon is formed
and the player who placed the last point loses the game. In our paper
we show a winning strategy for the player who plays second in the
convex 5-gon game and the empty convex 5-gon game by considering
convex layer configurations at each step. We prove that the game
always ends in the 9th step by showing that the game reaches a
specific set of configurations.

Full Text: PDF PostScript