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$
    – Stasys
    Nov 13, 2016 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.