Strictly monotonic multidimensional sequences and stable sets in pillage games

Details Strictly monotonic multidimensional sequences and stable sets in pillage games Strictly monotonic multidimensional sequences and stable sets in pillage games

2010-04-03

arxiv.org/abs/1004.0433v1

Mathematics

Combinatorics

Scientific paper

Let $S \subset \mathbb{R}^n$ have size $|S| > \ell^{2^n-1}$. We show that there are distinct points $\{x^1,..., x^{\ell+1}\} \subset S$ such that for each $i \in [n]$, the coordinate sequence $(x^j_i)_{j=1}^{\ell+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 $\real$. 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 $\real^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 \leq 2^{n-1}$, and that this bound is best possible.

Affiliated with

Also associated with

No associations

Rating

Strictly monotonic multidimensional sequences and stable sets in pillage games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strictly monotonic multidimensional sequences and stable sets in pillage games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strictly monotonic multidimensional sequences and stable sets in pillage games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-198667