Strictly monotonic multidimensional sequences and stable sets in pillage games

Abstract: Let

S s u b s e t m a t h b b R^{n}

have size

| S | > e l l^{2^{n} - 1}

. We show that there are distinct points

x^{1}, ..., x^{e l l + 1} s u b s e t S

such that for each

i i n [n]

, the coordinate sequence

(x_{i}^{j})_{j = 1}^{e l l + 1}

is strictly increasing, strictly decreasing, or constant, and that this bound on

| S |

is best possible. This is analogous to the erdos-Szekeres theorem on monotonic sequences in

e a l

. 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

2 t

points in

e a l^{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 l e q 2^{n - 1}

, and that this bound is best possible.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: Strictly monotonic multidimensional sequences and stable sets in pillage games