# Two player game variant of the Erdos-Szekeres problem.

1 Introduction

The Erdos-Szekeres Problem is defined as follows:

For any integer k, k [greater than or equal to] 3, determine the smallest positive integer N(k) such that any planar point set in general position that has at least N(k) points contains k points that are the vertices of a convex k-gon.

In 1935 Erdos and Szekeres proved the finiteness of N(k) using Ramsey theory [10]. There has been a series of improvements to bound the value of N(k) and the current best known bounds are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

see [9, 18, 28]. Erdos and Szekeres conjectured that the current lower bound is tight. This conjecture has been proved for k [less than or equal to] 6. N(4) = 5 was a geometric observation by Esther Klien. N(5) = 9 was shown by Kalbfeisch et al. [26]. N(6) = 17 has been proved by Szekeres and Peters using an combinatorial model of planar configurations [27]. See survey [23, 4] for a detailed description about the history of the problem and its variants.

Erdos asked the Empty Convex k-gon Problem which is defined as follows:

It is easy to see that H(4) = 5. H(5) = 10 was proved by Harboth [14]. Gerken [13] and Nicholes [24] proved independently the existence of a empty hexagon. The current best bounds on H(6) are 30 [less than or equal to] H(6) [less than or equal to] 463 [19, 25]. Horton showed that H(k) does not exist for any k, k [greater than or equal to] 7 [16].

The Erdos-Szekeres Problem has been studied in higher dimensions [10, 9, 29]. Other related variants that are well studied are the convex k-gon with specified number of interior points [2, 3, 11, 17, 30] and the chromatic variant [8, 1].

We introduce a two player game variant of Erdos-Szekeres Problem:

Consider a two player game where each player playing in alternate turns, place points in the plane. The game ends when a convex k-gon is formed and the player who placed the last point loses the game.

The goal of both the players is to avoid losing the game. In the scenario where a player is bound to lose the game, his goal is to prolong the game as much as possible.

Since computational efficiency is not an issue in our context, we assume that both players follow an optimal strategy that achieves their goal.

Since N(k) is finite, we know that the game will end in at most N(k) number of steps. Can the game end before N(k) steps?

Define NG(k) as the minimum number of steps for the game to end when both the players follow their optimal strategy.

In this paper we focus on finding the exact value of NG(k). We denote the player who plays first as player 1 and the player who plays second as player 2.

We also consider the two player game for the empty convex k-gon and correspondingly define HG(k). It is easy to see that [N.sub.G](3) = [H.sub.G](3) = 3, [N.sub.G](4) = [H.sub.G](4) = 5.

Combinatorial two player games have been well studied in the Maker/Breaker setting which is defined as follows:

Chvatal and Erdos introduced the Maker/Breaker-type game [7] for spanning trees, Hamiltonian cycles on graphs. There are a lot of results on Maker/Breaker-type games where (X, F) denotes random graphs, non planar graphs, near-perfect matchings, k-connected spanning subgraphs. There has also been a long line of research that studies the biased version of the various Maker/Breaker-type games [15, 5, 6, 12, 20, 21].

A complimentary variant of the Maker/Breaker game is the Avoider/Enforcer game where one player wants to avoid the formation of a structure and the other player wants to force the formation of that structure [22, 5].

The two player game variant of the Erdos-Szekeres Problem that we study in this paper is different from the Maker/Breaker, Avoider/Enforcer games since in our game the objective of both the players is the same, i.e., avoiding the formation of convex k-gon.

In this paper, we focus on the Erdos-Szekeres two player game for k = 5. We show a winning strategy for player 2 and prove that [N.sub.G] (5) = 9 and [H.sub.G] (5) = 9. i.e., the game will end in the 9th step.

We consider convex layer configurations at each step and give a strategy for player 2 such that the game will reach a specific set of configurations until the 8th step and finally we argue in the 9th step that a convex 5-gon or an empty convex 5-gon is formed.

We further show that the convex 5-gon and empty convex 5-gon game always ends in the 9th step, i.e., there is no strategy for player 2 to end the game earlier.

The paper is organized as follows. Section 2 contains the preliminaries and definitions that we will be using in the rest of the paper. Section 3 describes the proof for the convex 5-gon game. Section 4 describes the proof for the empty convex 5-gon game.

2 Preliminaries and Definitions

We assume in the rest of this paper that our point set P is in general position, i.e., no 3 points of the point set are collinear. We denote the convex hull of a point set P as conv(P) and the vertices of conv(P) as CH (P).

Definition 2.1 Convex k-gon: is a convex polygon with k vertices.

Definition 2.2 Empty Convex k-gon: is a convex k-gon with no points in its interior.

Definition 2.3 Points in convex position: A point set P is said to be in convex position if CH(P) = P.

Definition 2.4 Type of a point set P: A point set P is called type ([i.sub.1], [i.sub.2], ... [i.sub.k,], [absolute value of P] - [summation] [absolute value of [i.sub.k]], if [P.sub.1] = CH (P) is of size [i.sub.1], [P.sub.2] = CH (P \ [P.sub.1]) is of size [i.sub.2] ...

The type of point set P describes the sizes of the different convex layers of P. We denote [P.sub.1] as the first convex layer and [P.sub.2] as the second convex layer.

Definition 2.5 U(i,j) of point set P: Point set having i points of the first convex layer of P and j points of the second convex layer of P.

Definition 2.6 Type 1 Beam: A : BC denotes the region of the plane formed by deleting triangle ABC from the convex region in the plane bounded by the rays [??] and [??] (see Fig. 1).

Definition 2.7 Type 2 Beam: AB : CD denotes the region of the plane formed by deleting convex 4-gon ABCD from the convex region in the plane bounded by the segment [bar.AB] and the rays [??] and [??] (see Fig. 2).

Let A, B, C, D be 4 points in convex position.

Definition 2.8 Regions of convex 4-gon: The ABCD convex 4-gon divides the plane into 4 types of regions I, O, S, Z (see Fig. 3). O region is the region such that any point in it along with ABCD forms a convex 5-gon. I and Z regions are the regions such that any point in these regions along with ABCD forms a point set of type(4,1). I region is outside the convex 4-gon and Z region is inside the convex 4-gon. S region is the region such that any point in it along with ABCD forms a point set of type(3, 2).

Definition 2.9 Regions of a configuration: A configuration divides the plane into 4 types of regions I, O, S, Z. A region is called an O region of a configuration if it is an O region with respect to some convex 4-gon. The complement of the union of all the O regions of a configuration is further divided into I, S, Z regions. A region is called an I region of a configuration if it is an I region with respect to some convex 4-gon. Similarly we define S and Z regions of the configuration.

Definition 2.10 Feasible regions of a configuration for the convex 5-gon game: A feasible region of a configuration for the convex 5-gon game is a region which is not contained in any of the O regions of the convex 4-gon 's of the configuration.

Definition 2.11 Feasible regions of a configuration for the empty convex 5-gon game: A feasible region of a configuration for the empty convex 5-gon game is a region which is not contained in any of the O regions of the empty convex 4-gon's of the configuration.

We define the following set of point configurations that will be used in our proofs (see Fig. 4 and 24).

Definition 2.12 Configuration 4: A 4 point set forming a parallelogram.

Definition 2.13 Configuration 5.1: A 5 point set of type(4,1) where the 4 points in the first convex layer form a parallelogram.

Definition 2.14 Configuration 5.2: A 5 point set of type(4,1) where the 3 points in the first convex layer with the 1 point in the interior form a parallelogram.

Definition 2.15 Configuration 6.1: A 6 point set of type(4, 2) where 4 points in the first convex layer form a parallelogram and the 2 points inside the parallelogram are symmetrically placed in opposite triangles formed by diagonals of parallelogram.

Definition 2.16 Configuration 6.2: A 6 point set of type(4, 2) where 4 points in the first convex layer form a trapezoid and the 2 points inside the trapezoid are symmetrically placed in opposite triangles formed by the diagonals.

Definition 2.17 Configuration 7.1: A 7 point set of type(3,4) where the 3 points of the first convex layer are in different I regions of the parallelogram formed by the 4 points in the second convex layer.

Definition 2.18 Configuration 7.2.1: A 7point set of type(4,3) that does not have a convex 5-gon.

Definition 2.19 Configuration 7.2.2: A 7point set of type(4,3) that has a non-empty convex 5-gon.

Definition 2.20 Configuration 8: An 8 point set of type(4,4) where the 4 points of the first convex layer are placed such that each point lies in different I region of the convex 4-gon of the second convex layer.

3 Game for the convex 5-gon

In this section, we show that the second player has a winning strategy in the convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, ...) and player 2 plays in the even steps (2nd, 4th, ...). In player 1's turn, we argue that any point added without forming an convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.10) for placing the point that results in specific configurations that are favorable for player 2.

W.1.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2:

Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1 and 7.2.1 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an convex 5-gon results in configuration 5.1 or 5.2 (in the 5th step) and in configuration 7.1 or 7.2.1 (in the 7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a convex 5-gon and player 2 will always win in the 9th step.

Any convex 5-gon game follows a path in the game tree shown in Fig. 4.

We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

3.1 Proof for [N.sub.G] (5) = 9

We make the following observations on the number of points that can be contained in type 1 and type 2 beams without forming an empty convex 5-gon. We will assume that the points in the beam are in convex position with the points that form the beam. Thus, if the point set does not contain a convex 5-gon, type 1 beam has at most 1 point and type 2 beam does not contain any point.

Lemma 3.1 A strategy for player 2 exists such that convex 5-gon game will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: A triangle is formed by the first 3 points of the game. The 4th point is placed in such a manner that the resultant point set forms a parallelogram ABCD (configuration 4). For the 5th step, we divide the regions of the parallelogram into I, O, Z regions as shown in Fig. 5. The feasible regions where a point can be placed are the I and Z regions.

If the 5th point, say E, is placed in the interior of the parallelogram i.e., Z region, the resultant point set forms configuration 5.1 (see Fig. 6). If E is placed in I region the resultant point set forms configuration 5.2 (see Fig. 7).

In the 6th step we show a feasible region in configuration 5.1 and configuration 5.2 where a point is added such that the resultant point set formed is either configuration 6.1 or configuration 6.2.

If the 5 point set formed is configuration 5.1, then let us suppose that E has been placed in [Z.sub.1] region (see Fig. 6), then the 6th point, say F is placed in [Z.sub.3] such that EF is parallel to AD and this forms configuration 6.1 (see Fig. 8). Let us call this as {[Z.sub.1], [Z.sub.3}] point placement. By symmetry {[Z.sub.2,] [Z.sub.4}] point placement is similar and they form configuration 6.1.

Now we argue for configuration 5.2. Let us suppose that E has been placed in [I.sub.i] region (see Fig. 7). The 6th point, say F, is placed in [I.sub.8] region such that EF is parallel to AD (see Fig. 9). Let us call this as {[I.sub.1,] [I.sub.8}] point placement. By symmetry {[I.sub.2,] [I.sub.3}], {[I.sub.4], [I.sub.5}], {[I.sub.6], [I.sub.7}] point placements are similar and they form configuration 6.2.

Lemma 3.2 Any point added by player 1 to configuration 6.1 or configuration 6.2 without forming an convex 5-gon, results in either configuration 7.1 or configuration 7.2.1.

Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2.

Case 1 (configuration 6.1): Let us consider all the convex 4-gons of configuration 6.1 (see Fig. 10). The convex 4-gons of configuration 6.1 are of the form U(4,0), U(3,1), U(2, 2).

U(4,0) of configuration 6.1: ABCD is the only convex 4-gon of this form. Consider ABCD convex 4-gon. The regions that are contained in the O regions of ABCD are [O.sub.i], [O.sub.2], [O.sub.4], [O.sub.6], [O.sub.7], [O.sub.9].

U(3,1) of configuration 6.1: ABCF, BCDE, CDAE, DABF are the convex 4-gons of this form. The regions that are contained in O regions of ABCF, BCDE, CDAE, DABF are [O.sub.k] where k = 1, 2, ..10. [R.sub.1] [I.sub.1] is also contained in O region of ABCF. Fig. 10 shows [I.sub.1] in [R.sub.1] region. Symmetrically, there

are [I.sub.k] in other [R.sub.k] regions. So [R.sub.k] \ [I.sub.k] where k = 2, 3, 4 are also contained in the O regions BCDE, CDAE, DABF convex 4-gons.

U(2,2) of configuration 6.1: EFDA, EFCB, BEDF, AECF are the convex 4-gons of this form and these are empty. Consider EFDA empty convex 4-gon. The regions that are contained in the O regions of EFDA are [O.sub.1], [O.sub.7], [O.sub.8], [O.sub.9], [O.sub.10]. Similarly the regions that are contained in the O regions of EFCB empty convex 4-gon are [O.sub.2], [O.sub.3], [O.sub.4], [O.sub.5], [O.sub.6]. The O regions of BEDF, AECF empty convex 4-gons does not contain the entire region of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 1,2,3,4.

Thus, the feasible regions of configuration 6.1 (the regions that are not contained in any O region of convex 4-gons) are portions of [R.sub.k] where k = 1,2, 3,4 and Z region. From Fig. 10, we can verify that region [I.sub.1] of [R.sub.1] and [Z.sub.1] of Z is not contained in any of the O regions of the convex 4-gons. Fig. 10 shows [I.sub.1] in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2,3,4. Any point added in [I.sub.k] or [Z.sub.k] region will result in configuration 7.2.1.

Case 2 (configuration 6.2): Let us consider the convex 4-gons of configuration 6.2 (see Fig. 11). The convex 4-gons of configuration 6.2 are of the form U(4,0), U(3,1), U(2, 2).

U(4,0) of configuration 6.2: ABCD is the only convex 4-gon of this form. Consider ABCD convex 4-gon. The regions that are contained in the O regions of ABCD are [O.sub.2], [O.sub.3], [O.sub.5], [O.sub.6].

U(3,1) of configuration 6.2: AFCD, BEDC, ABCE, ABFD are the convex 4-gons of this form. The regions that are contained in O regions of AFCD, BEDC, ABCE, ABFD are [O.sub.2], [O.sub.3], [O.sub.5], [O.sub.6]. [R.sub.1]\[I.sub.1] is also contained in O region of AFCD. Fig. 11 shows [I.sub.1] in [R.sub.1] region. Symmetrically, there are [I.sub.k] in other [R.sub.k] regions. So [R.sub.k] \ [I.sub.k] where k = 2,3,4 are also contained in the O regions of ABCE,BEDC, ABFD convex 4-gons.

U(2,2) of configuration 6.2: EFCD, ABFE, AFCE, BEDF are the convex 4-gons of this form and these are empty. Consider EFCD empty convex 4-gon. The regions that are contained in the O regions of EFCD are [O.sub.2], [O.sub.6], [O.sub.1]. Similarly the regions contained in the O regions of ABFE empty convex 4-gon are [O.sub.3], [O.sub.5], [O.sub.4]. The O-regions of AFCE, BEDF empty convex 4-gons do not contain the entire regions of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 2, 3, 4.

Thus, the feasible regions of configuration 6.2 (the regions that are not contained in any O region of convex 4-gons) is S \ [O.sub.4] and portions of [R.sub.k] and Z regions. From Fig. 11, we can verify that region [I.sub.1] of [R.sub.1] is not contained in any of the O regions of these convex 4-gons. Fig. 11 shows [I.sub.1] in [R.sub.1] region and [Z.sub.1] in Z region. [Z.sub.1] is the region formed by triangle EDM where M is the intersection point of [??] and [??]. Symmetrically, there are feasible regions [I.sub.k] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2,3,4.

If the point is placed in [I.sub.k] of [R.sub.k] or [Z.sub.k] of Z where k = 1,2,3,4, the resultant point set is configuration 7.2.1. If the point is placed in S \ [O.sub.4] the resultant point set is configuration 7.1.

Now we prove that given a set of 7 points in configuration 7.1 or 7.2.1 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

Lemma 3.3 A (4,3) configuration where the 4 points of the outer convex layer is of the form (I,O,O,O) (3 points each in different O regions and 1 point in a I region of the inner triangle) contains a convex 5-gon.

Proof:

Let the inner triangle be ABC and the 3 points in the O regions of the triangle be F, G, H. Let the point in the I region be E and w.l.o.g let this I region be in between the O regions which contain the points F and H (see Fig. 12). We claim that the pair of rays does not intersect.

Consider the FBCH convex 4-gon. Now G should always lie in the S region of this convex 4-gon or else the 3 points F, G, H would not be containing the triangle ABC inside. To form an S region below BC, the rays [??]B and [??] intersects below BC. Hence the pair of rays do not intersect.

Now E always lies in the O region of FBCH convex 4-gon or else the point set is not a (4,3) convex layer configuration. Thus EFBCH forms an convex 5-gon.

Lemma 3.4 There exists a feasible region in configuration 7.1 and 7.2.1 such that a point added by player 2 in this feasible region results in configuration 8.

Proof: We consider 2 cases corresponding to configuration 7.1 and configuration 7.2.1.

Case 1 (configuration 7.1): Consider the region [I.sup.*] as shown in Fig. 13. We will show that this is a feasible region, i.e., [I.sup.*] is not contained in any O region of convex 4-gons.

Let us consider all the convex 4-gons of configuration 7.1. The convex 4-gons of configuration 7.1 are of the form U(2, 2), U(1, 3), U(0,4).

U(0,4) of configuration 7.1: ABCD is the only convex 4-gon of this form and has [I.sup.*] contained in its I region.

U(1,3) of configuration 7.1: EBDA, FDBC, ADGC, ABGC, DCEB, ABDF are the convex 4-gons of this form and these have [I.sup.*] contained in their I regions.

U(2,2) of configuration 7.1: FCDG, EACF, ABGF, BDFE, ADGF, FCBG are the convex 4-gons of this form and these have [I.sup.*] in their I regions.

Hence [I.sup.*] is feasible region where a point is added and the resultant point set that is formed is configuration 8.

Case 2 (configuration 7.2.1): Configuration 7.2.1 is a point set of (4,3) convex layer configuration without a convex 5-gon. First, we give the following characterization of configuration 7.2.1:

An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14).

Consider an O region. If an O region has 2 points then there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point. Consider an I region. If an I region has 2 points then no other I region or the adjacent O regions has any points because the 2 points in this I region along with the third point in the I region or in the adjacent O region will form an empty convex 5-gon with the side of the triangle. Thus if an I region has 2 points then the O region that is opposite has to have the other 2 points which leads to the formation of an empty convex 5-gon.

Based on the above constraints, the only possible (4,3) convex layer configurations are (I, I, O, O) (2 points each in different I regions, 2 points each in different O regions) and (I, O, O, O) (3 points each in different O regions, 1 point in a I region). By Lemma 3.3, (I, O, O, O) contains a convex 5-gon and hence will not be considered.

(I,I,O,O) (2 points each in different I regions, 2 points each in different O regions):

Let us assume that point G lies in region [X.sub.1] (see Fig. 15). The case when the point G is in [X.sub.2] can be argued in a similar fashion (see Fig. 17). We have 2 cases corresponding to EBG being a anti-clockwise turn or clockwise turn.

Type 1 (when G lies in [X.sub.1] and EBG is a anti-clockwise turn): We will show that [I.sup.*] (triangle region bounded by the CG, FA and EA) is a feasible region (see Fig. 15). Consider the convex 4-gons of this configuration. The convex 4-gons are either of the type U(2, 2), U(1, 3) or U(3,1).

U(1,3) of Type1 Configuration 7.2.1 (I,I,O,O): EACB, FABC are the 2 convex 4-gons of this type. [I.sup.*] region is in the interior of EACB and it is in the I region of FABC. Thus [I.sup.*] is feasible for these convex 4-gons.

U(2,2) of Type1 Configuration 7.2.1 (I,I,O,O): EABH, FACG, ECGB, EACH, FABG, BCFE, AHCF, EBGA and HBFC or AFBH based upon the position of H in the I region are the convex 4-gons of this type. It is easy to see that [I.sup.*] region is in the interior of EABH, EACH, BCFE, EBGA and [I.sup.*] region is in the I region of FACG, ECGB, FABG, AHCF. If FAH is an anti clockwise turn and FCH is clockwise turn, then either HBFC or AFBH is the convex 4-gon formed based upon the position of H in the I region of the triangle and both these convex 4-gons have [I.sup.*] in their I region. Thus [I.sup.*] is feasible for these convex 4-gons.

U(3,1) of Type1 Configuration 7.2.1 (I,I,O,O): EAGH, FAHG, FBHG, ECGH, EHCF, EBGF are the convex 4-gons of this type and these 4-gons have [I.sup.*] either in their I region or in their Z region. If FAH is an clockwise turn then EHAF is a convex 4-gon of this type having [I.sup.*] region inside. If FAH is an anti clockwise turn and FCH is anticlockwise turn then FCHG is the convex 4-gon is of this type and has [I.sup.*] contained in its I region. Thus [I.sup.*] is feasible for these convex 4-gons.

Any point added to [I.sup.*] results in configuration 8.

Type 2 (when G lies in [X.sub.1] and EBG is a clockwise turn): Consider the convex 4-gons of this configuration. The convex 4-gons are either of the type U(2, 2), U(1, 3) or U(3,1) (see Fig. 16).

U(3,1) of Type2 Configuration 7.2.1 (I,I,O,O): The convex 4-gons are the same as U(3,1) of Type1 Configuration 7.2.1 (I,I,O,O) except that we have EBGH instead of EBGF. EBGH has [I.sup.*] contained in its I region.

U(1,3) of Type2 Configuration 7.2.1 (I,I,O,O): This is same as U(1,3) of Type1 Configuration 7.2.1 (I,I,O,O).

U(2,2) of Type2 Configuration 7.2.1 (I,I,O,O): This is a subset of U(2,2) of Type1 Configuration 7.2.1 (I,I,O,O) (ECGB is a convex 4-gon for type1 but it is not convex 4-gon for type 2).

Lemmas 3.1, 3.2 and 3.4 show a player 2 strategy that forces the game to reach configuration 8. Since N(5) = 9 the game ends in the 9th step and player 2 wins the game.

We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the convex 5-gon game if the point set has no convex 5-gon and any point added to the point set forms an convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i - 1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 3.5 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3) and (4,2) are the only valid convex layer configurations for the convex 5-gon game. To show that a (3,3), (4,2) convex layer configurations are not bad configurations we show a feasible region where a point is added without forming an convex 5-gon.

(4,2) Convex layer configuration: Consider the line joining EF of the second convex layer (see Fig. 18(a)). This line divides the first convex layer into 2 parts. If either of the parts contains 3 points of the first convex layer then they form an empty convex 5-gon with the 2 points of the second convex layer. So the only other possible option is that both the parts contain 2 points.

Based upon the position of E, F in the diagonal triangles of the first convex layer, (4,2) convex layer configurations are divided into 3 cases.

Case 1: E, F are in opposite triangles, see Fig. 18(a).

Case 2: E, F are in same triangle, see Fig. 18(b).

Case 3: E, F are in adjacent triangles, see Fig. 18(c).

In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. 18). Thus (4,2) convex layer configurations are not bad configurations.

(3,3) Convex layer configuration: We make the following observations on the placement of the three points of the first convex layer in the I and O regions of the triangle formed by the second convex layer (see Fig. 14). If an I region has 3 points then the triangle in the second convex layer will not be contained in the triangle of the first convex layer. Hence an I region cannot have 3 points. Similarly an O region also cannot have 3 points. If an O region has 2 points then the opposite I region has to have the third point. In this case, there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point.

The only possible (3,3) point configurations are the following:

(I.I, I) (3 points in different I regions) Fig. 19.

(O, O, O) (3 points in different O regions) Fig. 20.

(I, I, O) (2 points are in different I regions and 1 point in an O region) Fig. 21.

(O, O, I) (2 points are in different O regions and 1 point in an I region) Fig. 22.

(2I, O) (2 points in an I region and 1 point in the opposite O region) Fig. 23.

In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. 19, 20, 21, 22, 23). Thus (3,3) convex layer configurations are not bad configurations.

Theorem 3.1 The convex 5-gon game always ends in the 9th step.

Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 3.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 3.5), the game will not end in the 7th step. By Lemma 3.2 the game will reach either configuration 7.1 or 7.2.1. By Lemma 3.4, the game will reach configuration 8 and finally since N(5) = 9 the game ends in the 9th step and player 2 wins the game.

4 Game for the empty convex 5-gon

In this section, we show that the second player has a winning strategy in the empty convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the empty convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, ...) and player 2 plays in the even steps (2nd, 4th, ...). In player 1's turn, we argue that any point added without forming an empty convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.11) for placing the point that results in specific configurations that are favorable for player 2.

W.l.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2:

Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1, 7.2.1 and 7.2.2 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an empty convex k-gon results in configuration 5.1 or 5.2 (5th step) and in configuration 7.1, 7.2.1 or 7.2.2 (7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a empty convex 5-gon and player 2 will always win in the 9th step.

Any empty convex 5-gon game follows a path in the game tree shown in Fig. 24.

The feasible regions of the convex 5-gon game is a subset of the feasible regions of the empty convex 5-gon game (by Definitions 2.10,2.11). Thus in the even step (player 2's turn to place the point) for configurations without a convex 5-gon (configurations 5.1, 5.2, 7.1, 7.2.1), the proof for the convex 5-gon game also applies for the empty convex 5-gon game. For configurations with a convex 5-gon (configurations 7.2.2) we give a separate proof.

We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

4.1 Proof for [H.sub.G] (5) = 9

Lemma 4.1 The game for the empty convex 5-gon will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: From Lemma 3.1 it is easy to see that the game for the empty convex 5-gon will always reach either configuration 5.1 or configuration 5.2 at the end of the 5th step.

Since the feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game, by Lemma 3.1 the game will reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Lemma 4.2 Any point added by player 1 to either configuration 6.1 or configuration 6.2 without forming an empty convex 5-gon, results in either configuration 7.1, 7.2.1 or 7.2.2.

Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2.

Case 1 (configuration 6.1): Let us consider all the empty convex 4-gons of configuration 6.1 (see Fig. 25). The convex 4-gons of configuration 6.1 that are formed by U(4,0), U(3,1) are not empty, so they are not considered. The empty convex 4-gons are of the form U(2, 2) of configuration 6.1.

U(2,2) of configuration 6.1: EFDA, EFCB, BEDF, AECF are the empty convex 4-gons of this form. Consider EFDA empty convex 4-gon. The regions that are contained in the O regions of EFDA are [O.sub.1], [O.sub.7], [O.sub.8], [O.sub.9], [O.sub.10]. Similarly the regions that are contained in the O regions of EFCB empty convex 4-gon are [O.sub.2], [O.sub.3], [O.sub.4], [O.sub.5], [O.sub.6]. The O regions of BEDF, AECF empty convex 4-gons does not contain the entire region of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 1,2, 3,4.

Thus, the only feasible regions of configuration 6.1 (the regions that are not contained in any O region of empty convex 4-gons) are portions of [R.sub.k] where k = 1,2,3,4 and Z region. From Fig. 25, we can verify that region [I.sub.1], [I.sup.*.sub.1] of [R.sub.1] and [Z.sub.1] of Z is not contained in any of the O regions of the empty convex 4-gons. Fig. 25 shows [I.sub.1], [I.sup.*.sub.1] only in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k], [I.sup.*] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2, 3,4. Any point added in [I.sub.k] or [Z.sub.k] region will result in configuration 7.2.1. Any point added in I* region will result in configuration 7.2.2.

Case 2 (configuration 6.2): Let us consider the empty convex 4-gons of configuration 6.2 (see Fig. 26). The convex 4-gons of configuration 6.2 that are formed by U(4,0), U(3,1) are not empty, so they are not considered. The empty convex 4-gons are of the form U(2, 2) of configuration 6.2 (see Fig. 26).

U(2,2) of configuration 6.2: EFCD, ABFE, AFCE, BEDF are the empty convex 4-gons of this form. Consider EFCD empty convex 4-gon. The regions that are contained in the O regions of EFCD are [O.sub.2], [O.sub.6], [O.sub.1]. Similarly the regions contained in the O regions of ABFE empty convex 4-gon are [O.sub.3], [O.sub.5], [O.sub.4]. The O-regions of AFCE, BEDF empty convex 4-gons do not contain the entire regions of Z and [R.sub.k] where k = 1,2, 3,4.

Thus, the feasible regions of configuration 6.2 (the regions that are not contained in any O region of empty convex 4-gons) is S [O.sub.4] and portions of [R.sub.k] and Z regions. From Fig. 26, we can verify that region [I.sub.1], [I.sup.*.sub.1] of [R.sub.1] is not contained in any of the O regions of these convex 4-gons. Fig. 26 shows [I.sub.1], [I.sup.*.sub.1] only in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k], [I.sup.*] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2, 3, 4.

If the point is placed in [I.sub.k], [I.sup.*] of [R.sub.k] or [Z.sub.k] of Z where k = 1,2,3,4, the resultant point set is either configuration 7.2.1 or configuration 7.2.2. If the point is placed in S \ [O.sub.4] the resultant point set is configuration 7.1.

Now we prove that given a set of 7 points in configuration 7.1, 7.2.1 or 7.2.2 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

Lemma 4.3 There exists a feasible region in configuration 7.1, 7.2.1 and 7.2.2 such that a point added by player 2 in this feasible region results in configuration 8.

Proof: The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. By Lemma 3.4, there exists a feasible region such that a point added by player 2 in this feasible region results in configuration 8.

Let us now consider configuration 7.2.2 (which has non-empty convex 5-gon). First we will give the following characterization of configuration 7.2.2. An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14).

Consider an O region. If an O region has 2 points then there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point. Consider an I region. If an I region has 2 points then no other I region or the adjacent O regions has any points because the 2 points in this I region along with the third point in the I region or in the adjacent O region will form an empty convex 5-gon with the side of the triangle. Thus if an I region has 2 points then the O region that is opposite has to have the other 2 points which leads to the formation of an empty convex 5-gon.

Based on the above constraints, the only possible (4,3) convex layer configuration is (I, O, O, O) (3 points each in different O regions, 1 point in a 1 region).

(I,O,O,O) (3 points each in different O regions, 1 point in a I region): Let us consider all the empty convex 4-gons of this configuration (see Fig. 27). The regions that are not contained in the O regions of empty convex 4-gons are precisely the regions where a point is added without forming an empty convex 5-gon. We will show that there exists a region [I.sup.*] in these feasible regions where a point is placed forming configuration 8. The convex 4-gons that are formed by U(4,0) of configuration 7.2.2 are not empty, so they are not considered. The remaining empty convex 4-gons of configuration 7.2.2 are of the form U(2, 2), U(1,3), U(3,1). It is important to note that GHE should be an anticlockwise turn and GFE a clockwise turn, otherwise we do not have a convex 4-gon in the first convex layer. U(3,1) of configuration 7.2.2 (I,O,O,O): EHAF is the empty convex 4-gon of this type and it has [I.sup.*] contained in its I region. Thus [I.sup.*] is feasible for these convex 4-gons.

U(1,3) of configuration 7.2.2 (I,O,O,O): FACB, HABC, ACGB are the empty convex 4-gons of this type. FACB, HABC have [I.sup.*] contained in there I regions and ACGB has [I.sup.*] inside. Thus [I.sup.*] is feasible for these convex 4-gons.

U(2,2) of configuration 7.2.2 (I,O,O,O): EABF, EHCA are the empty convex 4-gons of this type and these have [I.sup.*] contained in there I regions. Thus [I.sup.*] is feasible for these convex 4-gons.

Any point added to [I.sup.*] results in configuration 8.

We will now show that any point added to configuration 8 forms an empty convex 5-gon and hence the empty convex 5-gon game also ends in the 9th step. First we prove the following lemma.

Lemma 4.4 A (4,3,2) convex layer configuration has an empty convex 5-gon.

Proof: Let F, G, H, J be the 4 points of CH(P). Let A, B, C be the points in the second convex layer and D, E be the points of the inner most convex layer (see Fig. 28).

The points F, G, H, J lie in the union of beams formed by the beams DE : CB, D : AB and E : AC. Since beam DE : CB is type 2, if there exists a point in its beam region then there exists an empty convex 5-gon. Thus, one of the type 1 beams D : AB or E : AC beams has at least 2 points, which forms an empty convex 5-gon.

Lemma 4.5 A (4,4,1) convex layer configuration has an empty convex 5-gon.

Proof: Let F, G, H, J be the points of CH(P). Let A, B, C, D be the points of the second convex layer. Let K be the intersection of the diagonals of the convex 4-gon ABCD. Let E be the point inside the convex 4-gon ABCD. The union of beams E : AB, E : BC, E : CD, E : DA contain the points F, G, H, J.

Depending upon the position of point E inside the ABCD convex 4-gon the proof is divided into 4 cases.

Case 1: When e is in the triangle ABK (see Fig. 29(a)). In this case E : CD beam is contained in the union of AE : CD and EB : CD beams. Therefore any point in the E : CD beam forms an empty convex 5-gon. If e : CD beam does not have any point, one of the 3 type 1 beams E : BC, E : AB, E : DA has at least 2 points (among F, G, H, J) which forms an empty convex 5-gon.

Case 2: When e is in the triangle KCD (see Fig. 29(b)). In this case [I.sub.1], [I.sub.2], [I.sub.3], [I.sub.4], [I.sub.5], [I.sub.6] are the only feasible regions outside the ABCD convex 4-gon for the placement of F, G, H, J points. The remaining outer regions are present in the o region of some convex 4-gon and hence not feasible. The E : CD beam contains [I.sub.4], [I.sub.5], [I.sub.6] regions. Since e : cd beam is type 1 beam it can have at most 1 point. Therefore [I.sub.1], [I.sub.2], [I.sub.3] regions combined should have 3 points. From the figure we can see that the union of [I.sub.1], [I.sub.2], [I.sub.3] regions has 3 points which forms an empty convex 5-gon with the points A, B.

The case where E is in the triangle KBC is symmetrical to the case when it is in triangle ABK. The case where E is in the triangle KAD is symmetrical to the case when it is in triangle KCD.

Let E, F, G, H be the points of the first convex layer and A, B, C, D be the points of the second convex layer of configuration 8. Without loss of generality, let us assume that rays [??], [??] intersect and rays [??], [??] intersect.

Lemma 4.6 The 4 type 2 beams AB : FE, BC: GF, DC: GH, AD : HE contain the entire outer region in configuration 8.

Proof: We consider 2 cases depending on the intersections of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case1: When none of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersect each other (see Fig. 30(a)).

The regions contained by AB : FE, BC : GF, DC : GH, AD : HE beams are correspondingly [O.sub.1], [O.sub.2], [O.sub.3], [O.sub.4] beam regions which contain the entire outer region in configuration 8.

Case2: When some of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersect each other (see Fig. 30(b)).

Now we prove that atmost one of the pairs of rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can intersect in configuration 8. Assume that ([??], [??]) intersect (see Fig. 30(b)). The case ([??], [??]) intersecting is symmetrical.

Consider EA and FB, extend them inside ABCD convex 4-gon until they intersect with CD. Let the points of intersection be J, K. When GC is extended inside the ABCD convex 4-gon it has to intersect BK before it intersects AB or AD. Hence (BF, CG) do not intersect. By a similar reasoning, ray [??] intersects AJ before it intersects AB or BC. Hence ([??], [??]) do not intersect. The pair of rays ([??], [??]) do not intersect because the pair of rays ([??], [??]) do not intersect.

The regions contained by AB : FE, BC : GF, DC : GH, AD : HE beams are correspondingly [O.sub.1], [O.sub.2], [O.sub.3], [O.sub.4] beam regions (see Fig. 30(b)) which contain the entire outer region in configuration 8.

Lemma 4.7 Any point added to configuration 8 forms an empty convex 5-gon.

Proof:

We consider 2 cases depending on whether the point is added inside EFGH convex 4-gon or outside EFGH convex 4-gon (see Fig. 31).

Case1: Placing the point inside EFGH convex 4-gon:

The point added lies in I region, S region, Z region or O region of ABCD convex 4-gon. If the point is placed in the O region of ABCD convex 4-gon then there exists an empty convex 5-gon. If point is placed in the S region of ABCD convex 4-gon then it forms a (4,3,2) convex layer configuration which contains an empty convex 5-gon (Lemma 4.4). If the point is placed in the I or Z region of the ABCD convex 4-gon then it forms a (4,4,1) convex layer configuration which contains an empty convex 5-gon (Lemma 4.5).

Case2: Placing the point outside the EFGH convex 4-gon:

By Lemma 4.6, the 4 beams AB : FE, BC : GF, DC : GH, AD : HE contain the entire outer region. The added point lies in one of the 4 type 2 beams and forms an empty convex 5-gon. ?

Lemmas 4.1,4.2, 4.3 and 4.7 show a strategy for player 2 to win the game in the 9th step.

We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the empty convex 5-gon game if the point set has no empty convex 5-gon and any point added to the point set forms an empty convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i - 1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 4.8 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3), (4,2) and (5,1) are the only valid convex layer configurations for the empty convex 5-gon game.

The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. Thus by Lemma 3.5, there exists a feasible region for the (3,3), (4,2) convex layer configurations in the empty convex 5-gon game. Therefore (3,3), (4,2) convex layer configurations are not bad configurations for the empty convex 5-gon game.

To show that a (5,1) convex layer configuration is not a bad configuration we show a feasible region where a point is added without forming an empty convex 5-gon.

(5,1) Convex layer configuration: A feasible region K exists where a point can be added without forming a empty convex 5-gon (see shaded region in Fig. 32).

Theorem 4.1 The empty convex 5-gon game always ends in the 9th step.

Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 4.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 4.8), the game will not end in the 7th step. By Lemma 4.2 the game will reach either configuration 7.1, 7.2.1 or 7.2.2. By Lemma 4.3, the game will reach configuration 8 and finally from Lemma 4.7 the game ends in the 9th step and player 2 wins the game.

Conclusion

In our paper we have introduced the two player game variant of Erdos-Szekeres problem and proved that the game ends in the 9th step for the convex 5-gon and empty convex 5-gon game and player 2 wins in both the cases.

One natural question would be to analyze the game for higher values of k i.e. determine [N.sub.G](k) and [H.sub.G](k) for k > 5. Our approach will be very tedious for higher values of k as with the increase in the number of points in the point set, the number of point configurations increases exponentially.

We have shown that configuration 8 is a bad configuration for the empty convex 5-gon game. Another natural question is to determine whether there exists bad configurations for k > 5. More specifically, does there exist point configurations with the property that any point added to this configuration forms an empty convex k-gon or convex k-gon for k > 5. A negative result for the above question gives a lower bound for [N.sub.G] (k) and [H.sub.G](k).

References

[1] O. Aichholzar, T. Hackl, C. Huemer, F. Hurtado, B. Vogtenhuber. Large bichromatic point sets admit empty monochromatic 4-gons. SIAM Journal on Discrete Mathematics, 23(4):2147-2155, 2009.

[2] D. Avis, K. Hosono, M. Urabe. On the existence of a point subset with 4 or 5 interior points. In Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science, 1763:57-64, 1998.

[3] D. Avis, K. Hosono, M. Urabe. On the existence of a point subset with a specified number of interior points. Discrete Math., 241(1-3):33-TO, 2001.

[4] I. Barany, G. Karolyi. Problems and results around the Erdos-Szekeres convex polygon theorem. Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science 2098:91-105, 2001.

[5] J. Beck. Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008.

[6] M. Bednarska, T. Luczak. Biased positional games for which random strategies are nearly optimal. Combinatorica, 20(4):477-488, 2000.

[7] V. Chvatal, P. Erdos. Biased positional games. Ann. Discrete Math, 2:221-228, 1978.

[8] O. Devillers, F. Hurtado, G. Karolyi, C. Seara. Chromatic variants of the Erdos-szekeres theorem. Computational Geometry: Theory and Applications, 26:193-208, 2003.

[9] P. Erdos. Some more problems on elementary geometry. Austral. Math. Soc. Gaz, 103(1):99-108, 1978.

[10] P. Erdos, G. Szekeres. A combinatorial problem in geometry. Compositio Math, 2:463-470, 1935.

[11] T. Fevens. A note on the point subset with specified number of interior points. Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science, 2866:152-158, 2002.

[12] H. Gebauer, T. Szabo. Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms, 35:431-443, 2009.

[13] T. Gerken. On empty convex hexagons in planar point sets. Discrete Comput. Geom, 39(1-3):239-272, 2008.

[14] H. Harborth. Konvexe Funfecke in ebenen Punktmengen. Elem. Math, 33(5):116-118, 1978.

[15] D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo. Fast winning strategies in Maker-Breaker games. J. Combin. Theory Series B, 99(1):39-47, 2009.

[16] J.D. Horton. Sets with no empty convex 7-gons. Canad. Math. Bull, 26:482-484, 1983.

[17] K. Hosono. On the existence of a convex point subset containing one triangle in the plane. Discrete Mathematics, 305(1-3):201-218, 2005.

[18] D. Kleitman, L. Pachter. Finding convex sets among points in the plane. Discrete Comput. Geom, 19(3):405-410, 1998.

[19] V.A. Koshelev. On the Erdos-Szekeres type problem in combinatorial geometry. Discrete mathematics, 29:175-177, 2007.

[20] M. Krivelevich.

The critical bias for the Hamiltonicity game is (1 + o(1)) log n, Journal of the American Mathematical Society, 24:125-131, 2011.

[21] M. Krivelevich, T. Szabo. Biased positional games and small hyper graphs with large covers, Electronic Journal of Combinatorics, 15(1), R70, 2008.

[22] X. Lu. A note on biased and non-biased games, Discrete Appl. Math, 60:285-291, 1995.

[23] W. Morris, V. Soltan. The Erdos-Szekeres problem on points in convex position a survey. Bull. Amer. Math. Soc. (N.S), 37:437-458, 2000.

[24] C.M. Nicolas. The empty hexagon theorem. Discrete Comput. Geom., 38(2):389-397, 2007.

[25] M.H. Overmars. Finding set of points without empty convex 6-gons. Discrete Comput. Geom, 29:153-158, 2003.

[26] J.D. Kalbfeisch, J.G. Kalbfeisch, R.G. Stanton. A combinatorial problem on convex regions. In Proceedings of Louisiana conference on Combinatorics, Graph theory and computing, 180-188, 1970.

[27] G. Szekeres, L. Peters. Computer solution to the 17-point Erdos-Szekeres problem. The ANZIAM Journal, 48:151-164, 2006.

[28] G. Toth, P. Valtr. The Erdos-Szekeres theorem: upper bounds and related results. InCombinatorial and Computational Geometry. MSRI Publications, Cambridge University Press, 557-568, 2005.

[29] P. Valtr. Sets in Rd with no large empty convex subsets. Discrete Mathematics, 108:115-124, 1992/10/28.

[30] X. Wei, R. Ding. More on an Erdos-Szekeres-type problem for interior points. Discrete Comput. Geom, 42(4):640-653, 2009.

Parikshit Kolipaka ([dagger]) and Sathish Govindarajan ([double dagger])

Department of Computer Science & Automation, Indian Institute of Science, India

received 19th Sep. 2012, revised 23rd Mar. 2013, accepted 15th Aug. 2013.

([dagger]) Email: parikshit@csa.iisc.ernet.in.

([double dagger]) Email: gsat@csa.iisc.ernet.in

The Erdos-Szekeres Problem is defined as follows:

For any integer k, k [greater than or equal to] 3, determine the smallest positive integer N(k) such that any planar point set in general position that has at least N(k) points contains k points that are the vertices of a convex k-gon.

In 1935 Erdos and Szekeres proved the finiteness of N(k) using Ramsey theory [10]. There has been a series of improvements to bound the value of N(k) and the current best known bounds are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

see [9, 18, 28]. Erdos and Szekeres conjectured that the current lower bound is tight. This conjecture has been proved for k [less than or equal to] 6. N(4) = 5 was a geometric observation by Esther Klien. N(5) = 9 was shown by Kalbfeisch et al. [26]. N(6) = 17 has been proved by Szekeres and Peters using an combinatorial model of planar configurations [27]. See survey [23, 4] for a detailed description about the history of the problem and its variants.

Erdos asked the Empty Convex k-gon Problem which is defined as follows:

For any integer k, k [less than or equal to] 3, determine the smallest positive integer H(k) such that any planar point set in general position that has at least H(k) points contains k points that are the vertices of a an empty convex k-gon, i.e., the vertices of a convex k-gon containing no points in its interior.

It is easy to see that H(4) = 5. H(5) = 10 was proved by Harboth [14]. Gerken [13] and Nicholes [24] proved independently the existence of a empty hexagon. The current best bounds on H(6) are 30 [less than or equal to] H(6) [less than or equal to] 463 [19, 25]. Horton showed that H(k) does not exist for any k, k [greater than or equal to] 7 [16].

The Erdos-Szekeres Problem has been studied in higher dimensions [10, 9, 29]. Other related variants that are well studied are the convex k-gon with specified number of interior points [2, 3, 11, 17, 30] and the chromatic variant [8, 1].

We introduce a two player game variant of Erdos-Szekeres Problem:

Consider a two player game where each player playing in alternate turns, place points in the plane. The game ends when a convex k-gon is formed and the player who placed the last point loses the game.

The goal of both the players is to avoid losing the game. In the scenario where a player is bound to lose the game, his goal is to prolong the game as much as possible.

Since computational efficiency is not an issue in our context, we assume that both players follow an optimal strategy that achieves their goal.

Since N(k) is finite, we know that the game will end in at most N(k) number of steps. Can the game end before N(k) steps?

Define NG(k) as the minimum number of steps for the game to end when both the players follow their optimal strategy.

In this paper we focus on finding the exact value of NG(k). We denote the player who plays first as player 1 and the player who plays second as player 2.

We also consider the two player game for the empty convex k-gon and correspondingly define HG(k). It is easy to see that [N.sub.G](3) = [H.sub.G](3) = 3, [N.sub.G](4) = [H.sub.G](4) = 5.

Combinatorial two player games have been well studied in the Maker/Breaker setting which is defined as follows:

Let X be a finite set and let F [subset or equal to] [2.sup.X] be a family of subsets. In the game (X, F), two players (Maker and Breaker) take turns in claiming one previously unclaimed element of X. The objective of the Maker is to claim some f [member of] F i.e claim all the elements of f. The objective of the Breaker is to prevent the Maker from claiming any f [member of] F.

Chvatal and Erdos introduced the Maker/Breaker-type game [7] for spanning trees, Hamiltonian cycles on graphs. There are a lot of results on Maker/Breaker-type games where (X, F) denotes random graphs, non planar graphs, near-perfect matchings, k-connected spanning subgraphs. There has also been a long line of research that studies the biased version of the various Maker/Breaker-type games [15, 5, 6, 12, 20, 21].

A complimentary variant of the Maker/Breaker game is the Avoider/Enforcer game where one player wants to avoid the formation of a structure and the other player wants to force the formation of that structure [22, 5].

The two player game variant of the Erdos-Szekeres Problem that we study in this paper is different from the Maker/Breaker, Avoider/Enforcer games since in our game the objective of both the players is the same, i.e., avoiding the formation of convex k-gon.

In this paper, we focus on the Erdos-Szekeres two player game for k = 5. We show a winning strategy for player 2 and prove that [N.sub.G] (5) = 9 and [H.sub.G] (5) = 9. i.e., the game will end in the 9th step.

We consider convex layer configurations at each step and give a strategy for player 2 such that the game will reach a specific set of configurations until the 8th step and finally we argue in the 9th step that a convex 5-gon or an empty convex 5-gon is formed.

We further show that the convex 5-gon and empty convex 5-gon game always ends in the 9th step, i.e., there is no strategy for player 2 to end the game earlier.

The paper is organized as follows. Section 2 contains the preliminaries and definitions that we will be using in the rest of the paper. Section 3 describes the proof for the convex 5-gon game. Section 4 describes the proof for the empty convex 5-gon game.

2 Preliminaries and Definitions

We assume in the rest of this paper that our point set P is in general position, i.e., no 3 points of the point set are collinear. We denote the convex hull of a point set P as conv(P) and the vertices of conv(P) as CH (P).

Definition 2.1 Convex k-gon: is a convex polygon with k vertices.

Definition 2.2 Empty Convex k-gon: is a convex k-gon with no points in its interior.

Definition 2.3 Points in convex position: A point set P is said to be in convex position if CH(P) = P.

Definition 2.4 Type of a point set P: A point set P is called type ([i.sub.1], [i.sub.2], ... [i.sub.k,], [absolute value of P] - [summation] [absolute value of [i.sub.k]], if [P.sub.1] = CH (P) is of size [i.sub.1], [P.sub.2] = CH (P \ [P.sub.1]) is of size [i.sub.2] ...

The type of point set P describes the sizes of the different convex layers of P. We denote [P.sub.1] as the first convex layer and [P.sub.2] as the second convex layer.

Definition 2.5 U(i,j) of point set P: Point set having i points of the first convex layer of P and j points of the second convex layer of P.

Definition 2.6 Type 1 Beam: A : BC denotes the region of the plane formed by deleting triangle ABC from the convex region in the plane bounded by the rays [??] and [??] (see Fig. 1).

Definition 2.7 Type 2 Beam: AB : CD denotes the region of the plane formed by deleting convex 4-gon ABCD from the convex region in the plane bounded by the segment [bar.AB] and the rays [??] and [??] (see Fig. 2).

Let A, B, C, D be 4 points in convex position.

Definition 2.8 Regions of convex 4-gon: The ABCD convex 4-gon divides the plane into 4 types of regions I, O, S, Z (see Fig. 3). O region is the region such that any point in it along with ABCD forms a convex 5-gon. I and Z regions are the regions such that any point in these regions along with ABCD forms a point set of type(4,1). I region is outside the convex 4-gon and Z region is inside the convex 4-gon. S region is the region such that any point in it along with ABCD forms a point set of type(3, 2).

Definition 2.9 Regions of a configuration: A configuration divides the plane into 4 types of regions I, O, S, Z. A region is called an O region of a configuration if it is an O region with respect to some convex 4-gon. The complement of the union of all the O regions of a configuration is further divided into I, S, Z regions. A region is called an I region of a configuration if it is an I region with respect to some convex 4-gon. Similarly we define S and Z regions of the configuration.

Definition 2.10 Feasible regions of a configuration for the convex 5-gon game: A feasible region of a configuration for the convex 5-gon game is a region which is not contained in any of the O regions of the convex 4-gon 's of the configuration.

Definition 2.11 Feasible regions of a configuration for the empty convex 5-gon game: A feasible region of a configuration for the empty convex 5-gon game is a region which is not contained in any of the O regions of the empty convex 4-gon's of the configuration.

We define the following set of point configurations that will be used in our proofs (see Fig. 4 and 24).

Definition 2.12 Configuration 4: A 4 point set forming a parallelogram.

Definition 2.13 Configuration 5.1: A 5 point set of type(4,1) where the 4 points in the first convex layer form a parallelogram.

Definition 2.14 Configuration 5.2: A 5 point set of type(4,1) where the 3 points in the first convex layer with the 1 point in the interior form a parallelogram.

Definition 2.15 Configuration 6.1: A 6 point set of type(4, 2) where 4 points in the first convex layer form a parallelogram and the 2 points inside the parallelogram are symmetrically placed in opposite triangles formed by diagonals of parallelogram.

Definition 2.16 Configuration 6.2: A 6 point set of type(4, 2) where 4 points in the first convex layer form a trapezoid and the 2 points inside the trapezoid are symmetrically placed in opposite triangles formed by the diagonals.

Definition 2.17 Configuration 7.1: A 7 point set of type(3,4) where the 3 points of the first convex layer are in different I regions of the parallelogram formed by the 4 points in the second convex layer.

Definition 2.18 Configuration 7.2.1: A 7point set of type(4,3) that does not have a convex 5-gon.

Definition 2.19 Configuration 7.2.2: A 7point set of type(4,3) that has a non-empty convex 5-gon.

Definition 2.20 Configuration 8: An 8 point set of type(4,4) where the 4 points of the first convex layer are placed such that each point lies in different I region of the convex 4-gon of the second convex layer.

3 Game for the convex 5-gon

In this section, we show that the second player has a winning strategy in the convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, ...) and player 2 plays in the even steps (2nd, 4th, ...). In player 1's turn, we argue that any point added without forming an convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.10) for placing the point that results in specific configurations that are favorable for player 2.

W.1.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2:

Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1 and 7.2.1 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an convex 5-gon results in configuration 5.1 or 5.2 (in the 5th step) and in configuration 7.1 or 7.2.1 (in the 7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a convex 5-gon and player 2 will always win in the 9th step.

Any convex 5-gon game follows a path in the game tree shown in Fig. 4.

We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

3.1 Proof for [N.sub.G] (5) = 9

We make the following observations on the number of points that can be contained in type 1 and type 2 beams without forming an empty convex 5-gon. We will assume that the points in the beam are in convex position with the points that form the beam. Thus, if the point set does not contain a convex 5-gon, type 1 beam has at most 1 point and type 2 beam does not contain any point.

Lemma 3.1 A strategy for player 2 exists such that convex 5-gon game will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: A triangle is formed by the first 3 points of the game. The 4th point is placed in such a manner that the resultant point set forms a parallelogram ABCD (configuration 4). For the 5th step, we divide the regions of the parallelogram into I, O, Z regions as shown in Fig. 5. The feasible regions where a point can be placed are the I and Z regions.

If the 5th point, say E, is placed in the interior of the parallelogram i.e., Z region, the resultant point set forms configuration 5.1 (see Fig. 6). If E is placed in I region the resultant point set forms configuration 5.2 (see Fig. 7).

In the 6th step we show a feasible region in configuration 5.1 and configuration 5.2 where a point is added such that the resultant point set formed is either configuration 6.1 or configuration 6.2.

If the 5 point set formed is configuration 5.1, then let us suppose that E has been placed in [Z.sub.1] region (see Fig. 6), then the 6th point, say F is placed in [Z.sub.3] such that EF is parallel to AD and this forms configuration 6.1 (see Fig. 8). Let us call this as {[Z.sub.1], [Z.sub.3}] point placement. By symmetry {[Z.sub.2,] [Z.sub.4}] point placement is similar and they form configuration 6.1.

Now we argue for configuration 5.2. Let us suppose that E has been placed in [I.sub.i] region (see Fig. 7). The 6th point, say F, is placed in [I.sub.8] region such that EF is parallel to AD (see Fig. 9). Let us call this as {[I.sub.1,] [I.sub.8}] point placement. By symmetry {[I.sub.2,] [I.sub.3}], {[I.sub.4], [I.sub.5}], {[I.sub.6], [I.sub.7}] point placements are similar and they form configuration 6.2.

Lemma 3.2 Any point added by player 1 to configuration 6.1 or configuration 6.2 without forming an convex 5-gon, results in either configuration 7.1 or configuration 7.2.1.

Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2.

Case 1 (configuration 6.1): Let us consider all the convex 4-gons of configuration 6.1 (see Fig. 10). The convex 4-gons of configuration 6.1 are of the form U(4,0), U(3,1), U(2, 2).

U(4,0) of configuration 6.1: ABCD is the only convex 4-gon of this form. Consider ABCD convex 4-gon. The regions that are contained in the O regions of ABCD are [O.sub.i], [O.sub.2], [O.sub.4], [O.sub.6], [O.sub.7], [O.sub.9].

U(3,1) of configuration 6.1: ABCF, BCDE, CDAE, DABF are the convex 4-gons of this form. The regions that are contained in O regions of ABCF, BCDE, CDAE, DABF are [O.sub.k] where k = 1, 2, ..10. [R.sub.1] [I.sub.1] is also contained in O region of ABCF. Fig. 10 shows [I.sub.1] in [R.sub.1] region. Symmetrically, there

are [I.sub.k] in other [R.sub.k] regions. So [R.sub.k] \ [I.sub.k] where k = 2, 3, 4 are also contained in the O regions BCDE, CDAE, DABF convex 4-gons.

U(2,2) of configuration 6.1: EFDA, EFCB, BEDF, AECF are the convex 4-gons of this form and these are empty. Consider EFDA empty convex 4-gon. The regions that are contained in the O regions of EFDA are [O.sub.1], [O.sub.7], [O.sub.8], [O.sub.9], [O.sub.10]. Similarly the regions that are contained in the O regions of EFCB empty convex 4-gon are [O.sub.2], [O.sub.3], [O.sub.4], [O.sub.5], [O.sub.6]. The O regions of BEDF, AECF empty convex 4-gons does not contain the entire region of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 1,2,3,4.

Thus, the feasible regions of configuration 6.1 (the regions that are not contained in any O region of convex 4-gons) are portions of [R.sub.k] where k = 1,2, 3,4 and Z region. From Fig. 10, we can verify that region [I.sub.1] of [R.sub.1] and [Z.sub.1] of Z is not contained in any of the O regions of the convex 4-gons. Fig. 10 shows [I.sub.1] in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2,3,4. Any point added in [I.sub.k] or [Z.sub.k] region will result in configuration 7.2.1.

Case 2 (configuration 6.2): Let us consider the convex 4-gons of configuration 6.2 (see Fig. 11). The convex 4-gons of configuration 6.2 are of the form U(4,0), U(3,1), U(2, 2).

U(4,0) of configuration 6.2: ABCD is the only convex 4-gon of this form. Consider ABCD convex 4-gon. The regions that are contained in the O regions of ABCD are [O.sub.2], [O.sub.3], [O.sub.5], [O.sub.6].

U(3,1) of configuration 6.2: AFCD, BEDC, ABCE, ABFD are the convex 4-gons of this form. The regions that are contained in O regions of AFCD, BEDC, ABCE, ABFD are [O.sub.2], [O.sub.3], [O.sub.5], [O.sub.6]. [R.sub.1]\[I.sub.1] is also contained in O region of AFCD. Fig. 11 shows [I.sub.1] in [R.sub.1] region. Symmetrically, there are [I.sub.k] in other [R.sub.k] regions. So [R.sub.k] \ [I.sub.k] where k = 2,3,4 are also contained in the O regions of ABCE,BEDC, ABFD convex 4-gons.

U(2,2) of configuration 6.2: EFCD, ABFE, AFCE, BEDF are the convex 4-gons of this form and these are empty. Consider EFCD empty convex 4-gon. The regions that are contained in the O regions of EFCD are [O.sub.2], [O.sub.6], [O.sub.1]. Similarly the regions contained in the O regions of ABFE empty convex 4-gon are [O.sub.3], [O.sub.5], [O.sub.4]. The O-regions of AFCE, BEDF empty convex 4-gons do not contain the entire regions of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 2, 3, 4.

Thus, the feasible regions of configuration 6.2 (the regions that are not contained in any O region of convex 4-gons) is S \ [O.sub.4] and portions of [R.sub.k] and Z regions. From Fig. 11, we can verify that region [I.sub.1] of [R.sub.1] is not contained in any of the O regions of these convex 4-gons. Fig. 11 shows [I.sub.1] in [R.sub.1] region and [Z.sub.1] in Z region. [Z.sub.1] is the region formed by triangle EDM where M is the intersection point of [??] and [??]. Symmetrically, there are feasible regions [I.sub.k] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2,3,4.

If the point is placed in [I.sub.k] of [R.sub.k] or [Z.sub.k] of Z where k = 1,2,3,4, the resultant point set is configuration 7.2.1. If the point is placed in S \ [O.sub.4] the resultant point set is configuration 7.1.

Now we prove that given a set of 7 points in configuration 7.1 or 7.2.1 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

Lemma 3.3 A (4,3) configuration where the 4 points of the outer convex layer is of the form (I,O,O,O) (3 points each in different O regions and 1 point in a I region of the inner triangle) contains a convex 5-gon.

Proof:

Let the inner triangle be ABC and the 3 points in the O regions of the triangle be F, G, H. Let the point in the I region be E and w.l.o.g let this I region be in between the O regions which contain the points F and H (see Fig. 12). We claim that the pair of rays does not intersect.

Consider the FBCH convex 4-gon. Now G should always lie in the S region of this convex 4-gon or else the 3 points F, G, H would not be containing the triangle ABC inside. To form an S region below BC, the rays [??]B and [??] intersects below BC. Hence the pair of rays do not intersect.

Now E always lies in the O region of FBCH convex 4-gon or else the point set is not a (4,3) convex layer configuration. Thus EFBCH forms an convex 5-gon.

Lemma 3.4 There exists a feasible region in configuration 7.1 and 7.2.1 such that a point added by player 2 in this feasible region results in configuration 8.

Proof: We consider 2 cases corresponding to configuration 7.1 and configuration 7.2.1.

Case 1 (configuration 7.1): Consider the region [I.sup.*] as shown in Fig. 13. We will show that this is a feasible region, i.e., [I.sup.*] is not contained in any O region of convex 4-gons.

Let us consider all the convex 4-gons of configuration 7.1. The convex 4-gons of configuration 7.1 are of the form U(2, 2), U(1, 3), U(0,4).

U(0,4) of configuration 7.1: ABCD is the only convex 4-gon of this form and has [I.sup.*] contained in its I region.

U(1,3) of configuration 7.1: EBDA, FDBC, ADGC, ABGC, DCEB, ABDF are the convex 4-gons of this form and these have [I.sup.*] contained in their I regions.

U(2,2) of configuration 7.1: FCDG, EACF, ABGF, BDFE, ADGF, FCBG are the convex 4-gons of this form and these have [I.sup.*] in their I regions.

Hence [I.sup.*] is feasible region where a point is added and the resultant point set that is formed is configuration 8.

Case 2 (configuration 7.2.1): Configuration 7.2.1 is a point set of (4,3) convex layer configuration without a convex 5-gon. First, we give the following characterization of configuration 7.2.1:

An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14).

Consider an O region. If an O region has 2 points then there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point. Consider an I region. If an I region has 2 points then no other I region or the adjacent O regions has any points because the 2 points in this I region along with the third point in the I region or in the adjacent O region will form an empty convex 5-gon with the side of the triangle. Thus if an I region has 2 points then the O region that is opposite has to have the other 2 points which leads to the formation of an empty convex 5-gon.

Based on the above constraints, the only possible (4,3) convex layer configurations are (I, I, O, O) (2 points each in different I regions, 2 points each in different O regions) and (I, O, O, O) (3 points each in different O regions, 1 point in a I region). By Lemma 3.3, (I, O, O, O) contains a convex 5-gon and hence will not be considered.

(I,I,O,O) (2 points each in different I regions, 2 points each in different O regions):

Let us assume that point G lies in region [X.sub.1] (see Fig. 15). The case when the point G is in [X.sub.2] can be argued in a similar fashion (see Fig. 17). We have 2 cases corresponding to EBG being a anti-clockwise turn or clockwise turn.

Type 1 (when G lies in [X.sub.1] and EBG is a anti-clockwise turn): We will show that [I.sup.*] (triangle region bounded by the CG, FA and EA) is a feasible region (see Fig. 15). Consider the convex 4-gons of this configuration. The convex 4-gons are either of the type U(2, 2), U(1, 3) or U(3,1).

U(1,3) of Type1 Configuration 7.2.1 (I,I,O,O): EACB, FABC are the 2 convex 4-gons of this type. [I.sup.*] region is in the interior of EACB and it is in the I region of FABC. Thus [I.sup.*] is feasible for these convex 4-gons.

U(2,2) of Type1 Configuration 7.2.1 (I,I,O,O): EABH, FACG, ECGB, EACH, FABG, BCFE, AHCF, EBGA and HBFC or AFBH based upon the position of H in the I region are the convex 4-gons of this type. It is easy to see that [I.sup.*] region is in the interior of EABH, EACH, BCFE, EBGA and [I.sup.*] region is in the I region of FACG, ECGB, FABG, AHCF. If FAH is an anti clockwise turn and FCH is clockwise turn, then either HBFC or AFBH is the convex 4-gon formed based upon the position of H in the I region of the triangle and both these convex 4-gons have [I.sup.*] in their I region. Thus [I.sup.*] is feasible for these convex 4-gons.

U(3,1) of Type1 Configuration 7.2.1 (I,I,O,O): EAGH, FAHG, FBHG, ECGH, EHCF, EBGF are the convex 4-gons of this type and these 4-gons have [I.sup.*] either in their I region or in their Z region. If FAH is an clockwise turn then EHAF is a convex 4-gon of this type having [I.sup.*] region inside. If FAH is an anti clockwise turn and FCH is anticlockwise turn then FCHG is the convex 4-gon is of this type and has [I.sup.*] contained in its I region. Thus [I.sup.*] is feasible for these convex 4-gons.

Any point added to [I.sup.*] results in configuration 8.

Type 2 (when G lies in [X.sub.1] and EBG is a clockwise turn): Consider the convex 4-gons of this configuration. The convex 4-gons are either of the type U(2, 2), U(1, 3) or U(3,1) (see Fig. 16).

U(3,1) of Type2 Configuration 7.2.1 (I,I,O,O): The convex 4-gons are the same as U(3,1) of Type1 Configuration 7.2.1 (I,I,O,O) except that we have EBGH instead of EBGF. EBGH has [I.sup.*] contained in its I region.

U(1,3) of Type2 Configuration 7.2.1 (I,I,O,O): This is same as U(1,3) of Type1 Configuration 7.2.1 (I,I,O,O).

U(2,2) of Type2 Configuration 7.2.1 (I,I,O,O): This is a subset of U(2,2) of Type1 Configuration 7.2.1 (I,I,O,O) (ECGB is a convex 4-gon for type1 but it is not convex 4-gon for type 2).

Lemmas 3.1, 3.2 and 3.4 show a player 2 strategy that forces the game to reach configuration 8. Since N(5) = 9 the game ends in the 9th step and player 2 wins the game.

We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the convex 5-gon game if the point set has no convex 5-gon and any point added to the point set forms an convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i - 1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 3.5 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3) and (4,2) are the only valid convex layer configurations for the convex 5-gon game. To show that a (3,3), (4,2) convex layer configurations are not bad configurations we show a feasible region where a point is added without forming an convex 5-gon.

(4,2) Convex layer configuration: Consider the line joining EF of the second convex layer (see Fig. 18(a)). This line divides the first convex layer into 2 parts. If either of the parts contains 3 points of the first convex layer then they form an empty convex 5-gon with the 2 points of the second convex layer. So the only other possible option is that both the parts contain 2 points.

Based upon the position of E, F in the diagonal triangles of the first convex layer, (4,2) convex layer configurations are divided into 3 cases.

Case 1: E, F are in opposite triangles, see Fig. 18(a).

Case 2: E, F are in same triangle, see Fig. 18(b).

Case 3: E, F are in adjacent triangles, see Fig. 18(c).

In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. 18). Thus (4,2) convex layer configurations are not bad configurations.

(3,3) Convex layer configuration: We make the following observations on the placement of the three points of the first convex layer in the I and O regions of the triangle formed by the second convex layer (see Fig. 14). If an I region has 3 points then the triangle in the second convex layer will not be contained in the triangle of the first convex layer. Hence an I region cannot have 3 points. Similarly an O region also cannot have 3 points. If an O region has 2 points then the opposite I region has to have the third point. In this case, there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point.

The only possible (3,3) point configurations are the following:

(I.I, I) (3 points in different I regions) Fig. 19.

(O, O, O) (3 points in different O regions) Fig. 20.

(I, I, O) (2 points are in different I regions and 1 point in an O region) Fig. 21.

(O, O, I) (2 points are in different O regions and 1 point in an I region) Fig. 22.

(2I, O) (2 points in an I region and 1 point in the opposite O region) Fig. 23.

In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. 19, 20, 21, 22, 23). Thus (3,3) convex layer configurations are not bad configurations.

Theorem 3.1 The convex 5-gon game always ends in the 9th step.

Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 3.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 3.5), the game will not end in the 7th step. By Lemma 3.2 the game will reach either configuration 7.1 or 7.2.1. By Lemma 3.4, the game will reach configuration 8 and finally since N(5) = 9 the game ends in the 9th step and player 2 wins the game.

4 Game for the empty convex 5-gon

In this section, we show that the second player has a winning strategy in the empty convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the empty convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, ...) and player 2 plays in the even steps (2nd, 4th, ...). In player 1's turn, we argue that any point added without forming an empty convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.11) for placing the point that results in specific configurations that are favorable for player 2.

W.l.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2:

Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1, 7.2.1 and 7.2.2 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an empty convex k-gon results in configuration 5.1 or 5.2 (5th step) and in configuration 7.1, 7.2.1 or 7.2.2 (7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a empty convex 5-gon and player 2 will always win in the 9th step.

Any empty convex 5-gon game follows a path in the game tree shown in Fig. 24.

The feasible regions of the convex 5-gon game is a subset of the feasible regions of the empty convex 5-gon game (by Definitions 2.10,2.11). Thus in the even step (player 2's turn to place the point) for configurations without a convex 5-gon (configurations 5.1, 5.2, 7.1, 7.2.1), the proof for the convex 5-gon game also applies for the empty convex 5-gon game. For configurations with a convex 5-gon (configurations 7.2.2) we give a separate proof.

We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

4.1 Proof for [H.sub.G] (5) = 9

Lemma 4.1 The game for the empty convex 5-gon will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: From Lemma 3.1 it is easy to see that the game for the empty convex 5-gon will always reach either configuration 5.1 or configuration 5.2 at the end of the 5th step.

Since the feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game, by Lemma 3.1 the game will reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Lemma 4.2 Any point added by player 1 to either configuration 6.1 or configuration 6.2 without forming an empty convex 5-gon, results in either configuration 7.1, 7.2.1 or 7.2.2.

Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2.

Case 1 (configuration 6.1): Let us consider all the empty convex 4-gons of configuration 6.1 (see Fig. 25). The convex 4-gons of configuration 6.1 that are formed by U(4,0), U(3,1) are not empty, so they are not considered. The empty convex 4-gons are of the form U(2, 2) of configuration 6.1.

U(2,2) of configuration 6.1: EFDA, EFCB, BEDF, AECF are the empty convex 4-gons of this form. Consider EFDA empty convex 4-gon. The regions that are contained in the O regions of EFDA are [O.sub.1], [O.sub.7], [O.sub.8], [O.sub.9], [O.sub.10]. Similarly the regions that are contained in the O regions of EFCB empty convex 4-gon are [O.sub.2], [O.sub.3], [O.sub.4], [O.sub.5], [O.sub.6]. The O regions of BEDF, AECF empty convex 4-gons does not contain the entire region of Z (Z region of ABCD convex 4-gon) and [R.sub.k] where k = 1,2, 3,4.

Thus, the only feasible regions of configuration 6.1 (the regions that are not contained in any O region of empty convex 4-gons) are portions of [R.sub.k] where k = 1,2,3,4 and Z region. From Fig. 25, we can verify that region [I.sub.1], [I.sup.*.sub.1] of [R.sub.1] and [Z.sub.1] of Z is not contained in any of the O regions of the empty convex 4-gons. Fig. 25 shows [I.sub.1], [I.sup.*.sub.1] only in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k], [I.sup.*] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2, 3,4. Any point added in [I.sub.k] or [Z.sub.k] region will result in configuration 7.2.1. Any point added in I* region will result in configuration 7.2.2.

Case 2 (configuration 6.2): Let us consider the empty convex 4-gons of configuration 6.2 (see Fig. 26). The convex 4-gons of configuration 6.2 that are formed by U(4,0), U(3,1) are not empty, so they are not considered. The empty convex 4-gons are of the form U(2, 2) of configuration 6.2 (see Fig. 26).

U(2,2) of configuration 6.2: EFCD, ABFE, AFCE, BEDF are the empty convex 4-gons of this form. Consider EFCD empty convex 4-gon. The regions that are contained in the O regions of EFCD are [O.sub.2], [O.sub.6], [O.sub.1]. Similarly the regions contained in the O regions of ABFE empty convex 4-gon are [O.sub.3], [O.sub.5], [O.sub.4]. The O-regions of AFCE, BEDF empty convex 4-gons do not contain the entire regions of Z and [R.sub.k] where k = 1,2, 3,4.

Thus, the feasible regions of configuration 6.2 (the regions that are not contained in any O region of empty convex 4-gons) is S [O.sub.4] and portions of [R.sub.k] and Z regions. From Fig. 26, we can verify that region [I.sub.1], [I.sup.*.sub.1] of [R.sub.1] is not contained in any of the O regions of these convex 4-gons. Fig. 26 shows [I.sub.1], [I.sup.*.sub.1] only in [R.sub.1] region and [Z.sub.1] in Z region. Symmetrically, there are feasible regions [I.sub.k], [I.sup.*] in [R.sub.k] region and [Z.sub.k] in Z region where k = 2, 3, 4.

If the point is placed in [I.sub.k], [I.sup.*] of [R.sub.k] or [Z.sub.k] of Z where k = 1,2,3,4, the resultant point set is either configuration 7.2.1 or configuration 7.2.2. If the point is placed in S \ [O.sub.4] the resultant point set is configuration 7.1.

Now we prove that given a set of 7 points in configuration 7.1, 7.2.1 or 7.2.2 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

Lemma 4.3 There exists a feasible region in configuration 7.1, 7.2.1 and 7.2.2 such that a point added by player 2 in this feasible region results in configuration 8.

Proof: The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. By Lemma 3.4, there exists a feasible region such that a point added by player 2 in this feasible region results in configuration 8.

Let us now consider configuration 7.2.2 (which has non-empty convex 5-gon). First we will give the following characterization of configuration 7.2.2. An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14).

Consider an O region. If an O region has 2 points then there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point. Consider an I region. If an I region has 2 points then no other I region or the adjacent O regions has any points because the 2 points in this I region along with the third point in the I region or in the adjacent O region will form an empty convex 5-gon with the side of the triangle. Thus if an I region has 2 points then the O region that is opposite has to have the other 2 points which leads to the formation of an empty convex 5-gon.

Based on the above constraints, the only possible (4,3) convex layer configuration is (I, O, O, O) (3 points each in different O regions, 1 point in a 1 region).

(I,O,O,O) (3 points each in different O regions, 1 point in a I region): Let us consider all the empty convex 4-gons of this configuration (see Fig. 27). The regions that are not contained in the O regions of empty convex 4-gons are precisely the regions where a point is added without forming an empty convex 5-gon. We will show that there exists a region [I.sup.*] in these feasible regions where a point is placed forming configuration 8. The convex 4-gons that are formed by U(4,0) of configuration 7.2.2 are not empty, so they are not considered. The remaining empty convex 4-gons of configuration 7.2.2 are of the form U(2, 2), U(1,3), U(3,1). It is important to note that GHE should be an anticlockwise turn and GFE a clockwise turn, otherwise we do not have a convex 4-gon in the first convex layer. U(3,1) of configuration 7.2.2 (I,O,O,O): EHAF is the empty convex 4-gon of this type and it has [I.sup.*] contained in its I region. Thus [I.sup.*] is feasible for these convex 4-gons.

U(1,3) of configuration 7.2.2 (I,O,O,O): FACB, HABC, ACGB are the empty convex 4-gons of this type. FACB, HABC have [I.sup.*] contained in there I regions and ACGB has [I.sup.*] inside. Thus [I.sup.*] is feasible for these convex 4-gons.

U(2,2) of configuration 7.2.2 (I,O,O,O): EABF, EHCA are the empty convex 4-gons of this type and these have [I.sup.*] contained in there I regions. Thus [I.sup.*] is feasible for these convex 4-gons.

Any point added to [I.sup.*] results in configuration 8.

We will now show that any point added to configuration 8 forms an empty convex 5-gon and hence the empty convex 5-gon game also ends in the 9th step. First we prove the following lemma.

Lemma 4.4 A (4,3,2) convex layer configuration has an empty convex 5-gon.

Proof: Let F, G, H, J be the 4 points of CH(P). Let A, B, C be the points in the second convex layer and D, E be the points of the inner most convex layer (see Fig. 28).

The points F, G, H, J lie in the union of beams formed by the beams DE : CB, D : AB and E : AC. Since beam DE : CB is type 2, if there exists a point in its beam region then there exists an empty convex 5-gon. Thus, one of the type 1 beams D : AB or E : AC beams has at least 2 points, which forms an empty convex 5-gon.

Lemma 4.5 A (4,4,1) convex layer configuration has an empty convex 5-gon.

Proof: Let F, G, H, J be the points of CH(P). Let A, B, C, D be the points of the second convex layer. Let K be the intersection of the diagonals of the convex 4-gon ABCD. Let E be the point inside the convex 4-gon ABCD. The union of beams E : AB, E : BC, E : CD, E : DA contain the points F, G, H, J.

Depending upon the position of point E inside the ABCD convex 4-gon the proof is divided into 4 cases.

Case 1: When e is in the triangle ABK (see Fig. 29(a)). In this case E : CD beam is contained in the union of AE : CD and EB : CD beams. Therefore any point in the E : CD beam forms an empty convex 5-gon. If e : CD beam does not have any point, one of the 3 type 1 beams E : BC, E : AB, E : DA has at least 2 points (among F, G, H, J) which forms an empty convex 5-gon.

Case 2: When e is in the triangle KCD (see Fig. 29(b)). In this case [I.sub.1], [I.sub.2], [I.sub.3], [I.sub.4], [I.sub.5], [I.sub.6] are the only feasible regions outside the ABCD convex 4-gon for the placement of F, G, H, J points. The remaining outer regions are present in the o region of some convex 4-gon and hence not feasible. The E : CD beam contains [I.sub.4], [I.sub.5], [I.sub.6] regions. Since e : cd beam is type 1 beam it can have at most 1 point. Therefore [I.sub.1], [I.sub.2], [I.sub.3] regions combined should have 3 points. From the figure we can see that the union of [I.sub.1], [I.sub.2], [I.sub.3] regions has 3 points which forms an empty convex 5-gon with the points A, B.

The case where E is in the triangle KBC is symmetrical to the case when it is in triangle ABK. The case where E is in the triangle KAD is symmetrical to the case when it is in triangle KCD.

Let E, F, G, H be the points of the first convex layer and A, B, C, D be the points of the second convex layer of configuration 8. Without loss of generality, let us assume that rays [??], [??] intersect and rays [??], [??] intersect.

Lemma 4.6 The 4 type 2 beams AB : FE, BC: GF, DC: GH, AD : HE contain the entire outer region in configuration 8.

Proof: We consider 2 cases depending on the intersections of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case1: When none of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersect each other (see Fig. 30(a)).

The regions contained by AB : FE, BC : GF, DC : GH, AD : HE beams are correspondingly [O.sub.1], [O.sub.2], [O.sub.3], [O.sub.4] beam regions which contain the entire outer region in configuration 8.

Case2: When some of the rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersect each other (see Fig. 30(b)).

Now we prove that atmost one of the pairs of rays [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can intersect in configuration 8. Assume that ([??], [??]) intersect (see Fig. 30(b)). The case ([??], [??]) intersecting is symmetrical.

Consider EA and FB, extend them inside ABCD convex 4-gon until they intersect with CD. Let the points of intersection be J, K. When GC is extended inside the ABCD convex 4-gon it has to intersect BK before it intersects AB or AD. Hence (BF, CG) do not intersect. By a similar reasoning, ray [??] intersects AJ before it intersects AB or BC. Hence ([??], [??]) do not intersect. The pair of rays ([??], [??]) do not intersect because the pair of rays ([??], [??]) do not intersect.

The regions contained by AB : FE, BC : GF, DC : GH, AD : HE beams are correspondingly [O.sub.1], [O.sub.2], [O.sub.3], [O.sub.4] beam regions (see Fig. 30(b)) which contain the entire outer region in configuration 8.

Lemma 4.7 Any point added to configuration 8 forms an empty convex 5-gon.

Proof:

We consider 2 cases depending on whether the point is added inside EFGH convex 4-gon or outside EFGH convex 4-gon (see Fig. 31).

Case1: Placing the point inside EFGH convex 4-gon:

The point added lies in I region, S region, Z region or O region of ABCD convex 4-gon. If the point is placed in the O region of ABCD convex 4-gon then there exists an empty convex 5-gon. If point is placed in the S region of ABCD convex 4-gon then it forms a (4,3,2) convex layer configuration which contains an empty convex 5-gon (Lemma 4.4). If the point is placed in the I or Z region of the ABCD convex 4-gon then it forms a (4,4,1) convex layer configuration which contains an empty convex 5-gon (Lemma 4.5).

Case2: Placing the point outside the EFGH convex 4-gon:

By Lemma 4.6, the 4 beams AB : FE, BC : GF, DC : GH, AD : HE contain the entire outer region. The added point lies in one of the 4 type 2 beams and forms an empty convex 5-gon. ?

Lemmas 4.1,4.2, 4.3 and 4.7 show a strategy for player 2 to win the game in the 9th step.

We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the empty convex 5-gon game if the point set has no empty convex 5-gon and any point added to the point set forms an empty convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i - 1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 4.8 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3), (4,2) and (5,1) are the only valid convex layer configurations for the empty convex 5-gon game.

The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. Thus by Lemma 3.5, there exists a feasible region for the (3,3), (4,2) convex layer configurations in the empty convex 5-gon game. Therefore (3,3), (4,2) convex layer configurations are not bad configurations for the empty convex 5-gon game.

To show that a (5,1) convex layer configuration is not a bad configuration we show a feasible region where a point is added without forming an empty convex 5-gon.

(5,1) Convex layer configuration: A feasible region K exists where a point can be added without forming a empty convex 5-gon (see shaded region in Fig. 32).

Theorem 4.1 The empty convex 5-gon game always ends in the 9th step.

Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 4.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 4.8), the game will not end in the 7th step. By Lemma 4.2 the game will reach either configuration 7.1, 7.2.1 or 7.2.2. By Lemma 4.3, the game will reach configuration 8 and finally from Lemma 4.7 the game ends in the 9th step and player 2 wins the game.

Conclusion

In our paper we have introduced the two player game variant of Erdos-Szekeres problem and proved that the game ends in the 9th step for the convex 5-gon and empty convex 5-gon game and player 2 wins in both the cases.

One natural question would be to analyze the game for higher values of k i.e. determine [N.sub.G](k) and [H.sub.G](k) for k > 5. Our approach will be very tedious for higher values of k as with the increase in the number of points in the point set, the number of point configurations increases exponentially.

We have shown that configuration 8 is a bad configuration for the empty convex 5-gon game. Another natural question is to determine whether there exists bad configurations for k > 5. More specifically, does there exist point configurations with the property that any point added to this configuration forms an empty convex k-gon or convex k-gon for k > 5. A negative result for the above question gives a lower bound for [N.sub.G] (k) and [H.sub.G](k).

References

[1] O. Aichholzar, T. Hackl, C. Huemer, F. Hurtado, B. Vogtenhuber. Large bichromatic point sets admit empty monochromatic 4-gons. SIAM Journal on Discrete Mathematics, 23(4):2147-2155, 2009.

[2] D. Avis, K. Hosono, M. Urabe. On the existence of a point subset with 4 or 5 interior points. In Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science, 1763:57-64, 1998.

[3] D. Avis, K. Hosono, M. Urabe. On the existence of a point subset with a specified number of interior points. Discrete Math., 241(1-3):33-TO, 2001.

[4] I. Barany, G. Karolyi. Problems and results around the Erdos-Szekeres convex polygon theorem. Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science 2098:91-105, 2001.

[5] J. Beck. Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008.

[6] M. Bednarska, T. Luczak. Biased positional games for which random strategies are nearly optimal. Combinatorica, 20(4):477-488, 2000.

[7] V. Chvatal, P. Erdos. Biased positional games. Ann. Discrete Math, 2:221-228, 1978.

[8] O. Devillers, F. Hurtado, G. Karolyi, C. Seara. Chromatic variants of the Erdos-szekeres theorem. Computational Geometry: Theory and Applications, 26:193-208, 2003.

[9] P. Erdos. Some more problems on elementary geometry. Austral. Math. Soc. Gaz, 103(1):99-108, 1978.

[10] P. Erdos, G. Szekeres. A combinatorial problem in geometry. Compositio Math, 2:463-470, 1935.

[11] T. Fevens. A note on the point subset with specified number of interior points. Japanese Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science, 2866:152-158, 2002.

[12] H. Gebauer, T. Szabo. Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms, 35:431-443, 2009.

[13] T. Gerken. On empty convex hexagons in planar point sets. Discrete Comput. Geom, 39(1-3):239-272, 2008.

[14] H. Harborth. Konvexe Funfecke in ebenen Punktmengen. Elem. Math, 33(5):116-118, 1978.

[15] D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo. Fast winning strategies in Maker-Breaker games. J. Combin. Theory Series B, 99(1):39-47, 2009.

[16] J.D. Horton. Sets with no empty convex 7-gons. Canad. Math. Bull, 26:482-484, 1983.

[17] K. Hosono. On the existence of a convex point subset containing one triangle in the plane. Discrete Mathematics, 305(1-3):201-218, 2005.

[18] D. Kleitman, L. Pachter. Finding convex sets among points in the plane. Discrete Comput. Geom, 19(3):405-410, 1998.

[19] V.A. Koshelev. On the Erdos-Szekeres type problem in combinatorial geometry. Discrete mathematics, 29:175-177, 2007.

[20] M. Krivelevich.

The critical bias for the Hamiltonicity game is (1 + o(1)) log n, Journal of the American Mathematical Society, 24:125-131, 2011.

[21] M. Krivelevich, T. Szabo. Biased positional games and small hyper graphs with large covers, Electronic Journal of Combinatorics, 15(1), R70, 2008.

[22] X. Lu. A note on biased and non-biased games, Discrete Appl. Math, 60:285-291, 1995.

[23] W. Morris, V. Soltan. The Erdos-Szekeres problem on points in convex position a survey. Bull. Amer. Math. Soc. (N.S), 37:437-458, 2000.

[24] C.M. Nicolas. The empty hexagon theorem. Discrete Comput. Geom., 38(2):389-397, 2007.

[25] M.H. Overmars. Finding set of points without empty convex 6-gons. Discrete Comput. Geom, 29:153-158, 2003.

[26] J.D. Kalbfeisch, J.G. Kalbfeisch, R.G. Stanton. A combinatorial problem on convex regions. In Proceedings of Louisiana conference on Combinatorics, Graph theory and computing, 180-188, 1970.

[27] G. Szekeres, L. Peters. Computer solution to the 17-point Erdos-Szekeres problem. The ANZIAM Journal, 48:151-164, 2006.

[28] G. Toth, P. Valtr. The Erdos-Szekeres theorem: upper bounds and related results. InCombinatorial and Computational Geometry. MSRI Publications, Cambridge University Press, 557-568, 2005.

[29] P. Valtr. Sets in Rd with no large empty convex subsets. Discrete Mathematics, 108:115-124, 1992/10/28.

[30] X. Wei, R. Ding. More on an Erdos-Szekeres-type problem for interior points. Discrete Comput. Geom, 42(4):640-653, 2009.

Parikshit Kolipaka ([dagger]) and Sathish Govindarajan ([double dagger])

Department of Computer Science & Automation, Indian Institute of Science, India

received 19th Sep. 2012, revised 23rd Mar. 2013, accepted 15th Aug. 2013.

([dagger]) Email: parikshit@csa.iisc.ernet.in.

([double dagger]) Email: gsat@csa.iisc.ernet.in

Printer friendly Cite/link Email Feedback | |

Author: | Kolipaka, Parikshit; Govindarajan, Sathish |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Geographic Code: | 9INDI |

Date: | Nov 1, 2013 |

Words: | 10073 |

Previous Article: | On the connectedness and diameter of a geometric Johnson graph. |

Next Article: | The Magnus-Derek game in groups. |

Topics: |