# Infinite Ramsey theorem for strings (instead of sets)?

The infinite Ramsey theorem implies that, if we color the $n$-element subsets of $N:=\{0,1,2,\ldots\}$ in a finite number of colors, then there will exist an infinite subset $A\subseteq N$ such that all $n$-element subsets of $A$ will be of the same color.

My question is about vectors in $N^n=\{(x_1,\ldots,x_n) \colon x_i\in N\}$ instead of $n$-element subsets of $N$.

Say that a set $X\subseteq N^n$ is dominating if for every nonempty subset $S\subset \{1,\ldots,n\}$ of positions, there is a vector $x\in X$ such that $$\min_{i\in S} x_i > \sum_{i\not\in S} x_i.$$ For example, the set $X=\{0,1\}^n$ is dominating, as well as is any set $X=\{a_1,b_1\}\times \cdots\times \{a_n,b_n\}$ with $$\min\{b_1,\ldots,b_n\} > a_1+\cdots+a_n.$$

Question: If we color the vectors in $N^n$ in a finite number of colors, will then at least one dominating set $X$ be monochromatic?

The question seems so natural that it should be definitely investigated by someone. But I couldn't find any references, nor any counterexamples.

My question is motivated by a rather "pragmatic" goal: to prove that randomness cannot speed-up dynamic programming.

Color each vector $(x_i)$ in any $k$ such that $x_k=\max\limits_{1\leq i\leq n} x_i$. Then there is no dominating monochromatic set: if it had color $k$, then there is no $S$-dominating bector for $k\notin S$.

• very nice! This coloring is clearly "anti-dominating", already for only n colors. – Stasys Nov 13 '16 at 18:55