Two Player Game Variant Of The Erdos Szekeres Problem

Abstract

The following problem has been known for its beauty and elementary character. The Erd˝os Szekeres problem[7]: For any integer k ≥ 3, determine if there exists a smallest positive integer N(k) such that any set of atleast N(k) points in general position in the plane(i.e no three points are in a line) contains k points that are the vertices of a convex k-gon. The finiteness of (k)is proved by Erd˝os and Szekeres using Ramsey theory[7]. In 1978, Erd˝os [6] raised a similar question on empty convex k-gon (convex k-gon without out any interior points) and it has been extensively studied[18]. Several other variants like the convex k-gon with specified number interior points[2] and the chromatic variant[5] have been well studied. In this thesis, we introduce the following two player game variant of the Erd˝os Szekeres problem: Consider a two player game where each player places a point in the plane such that the point set formed will not contain a convex k-gon. The game will end when a convex k-gon is formed and the player who placed the last point loses the game. In our thesis we show a winning strategy forplayer2inthe convex5-gongame and the empty convex5-gongame and argue that the game always ends in the 9th step. We also give an alternative proof for the statement that any point set containing 10 or more points contains an empty convex 5-gon.