1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ very nice! This coloring is clearly "anti-dominating", already for only n colors. $\endgroup$ Commented Nov 13, 2016 at 18:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.