Strictly monotonic multidimensional sequences and stable sets in pillage games

Let $S\subset {\mathbb{R}}^n$ have size $\mathrm{\mid }S\mathrm{\mid }>{\mathrm{\ell }}^{2^n-1}$. We show that there are distinct points $\{x^1,\mathrm{.}\mathrm{.}\mathrm{.},x^{\mathrm{\ell }+1}\}\subset S$ such that for each $i\in [n]$, the coordinate sequence $(x_i^j{)}_{j=1}^{\mathrm{\ell }+1}$ is strictly increasing, strictly decreasing, or constant, and that this bound on $\mathrm{\mid }S\mathrm{\mid }$ is best possible. This is analogous to the \erdos-Szekeres theorem on monotonic sequences in $\mathrm{\Re }$. We apply these results to bound the size of a stable set in a pillage game. We also prove a theorem of independent combinatorial interest. Suppose $\{a^1,b^1,\mathrm{.}\mathrm{.}\mathrm{.},a^t,b^t\}$ is a set of $2t$ points in ${\mathrm{\Re }}^n$ such that the set of pairs of points not sharing a coordinate is precisely $\{\{a^1,b^1\},\mathrm{.}\mathrm{.}\mathrm{.},\{a^t,b^t\}\}$. We show that $t\le 2^{n-1}$, and that this bound is best possible.