Strictly monotonic multidimensional sequences and stable sets in pillage games

作者：Saxton David^*

来源：Journal of Combinatorial Theory - Series A, 2011, 118(2): 510-524.

DOI：10.1016/j.jcta.2010.07.003

• Erdos-Szekeres
• Strictly monotonic sequences
• Pillage games

Let S subset of R(n) have size vertical bar S vertical bar > l(2n-1). We show that there are distinct points {x(1),....x(l+1)} subset of S such that for each i is an element of [n], the coordinate sequence (x(i)(j))(j=1)(l+1) is strictly increasing, strictly decreasing, or constant, and that this bound on vertical bar S vertical bar is best possible. This is analogous to the Erdos-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 {a(1), b(1),...a(t), b(t)) is a set of 2t points in R(n) such that the set of pairs of points not sharing a coordinate is precisely {{a(1) ,b(1) },...,{a(t) ,b(t) }} We show that t <= 2(n-1), and that this bound is best possible.

• 出版日期2011-2