Strictly monotonic multidimensional sequences and stable sets in pillage games

Let S⊂Rn have size |S|>ℓn2−1. We show that there are distinct points {x1,…,xℓ+1}⊂S such that for each i∈[n], the coordinate sequence is strictly increasing, strictly decreasing, or constant, and that this bound on |S| is best possible. This is analogous to the Erdős–Szekeres theorem on monotonic sequences in R.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 {a1,b1,…,at,bt} is a set of 2t points in Rn such that the set of pairs of points not sharing a coordinate is precisely {{a1,b1},…,{at,bt}}. We show that t⩽2n−1, and that this bound is best possible.