# Coloring a unit cube 2

Since the original question has been answered by Fedor Petrov and Robert Israel, here are more difficult questions (the terminology is preserved).

• Let $m>n$. What is the smallest number $c(m,n)$ of colors needed to color the unit cube $I^m$ so that no color is $n$-distance connected. I need a rough (but meaningful) estimate from below or from above.

• If $m=n+1$, is $c(m,n)=O(2^n/n)$ as in Fedor's answer?

• What if $m=2n$?

• Can $c(m,n)$ be bounded from above by a polynomial in $n$ for some/all $m\gg n$?

Update It looks like Fedor's proof gives the upper bound $c(m,n)\le O(2^n/n)$ for every $m > n$ (does not depend on $m$). The big question is whether it (or something similar) is also a lower bound or perhaps it is getting smaller with $m$.

-

The question turned out to be easy: $c(m,n)=2$ as soon as $m\ge 2n$. Indeed, take a vertex $v$ of the cube $I^m$ and let $v'$ be the opposite vertex (i.e. $vv'$ is a long diagonal). Let $B_n(v)$ be the ball of radius $n$ (in the $l_1$-metric) around $v$. Let us color the set $B_n(v)\setminus \{v\}\cup\{v'\}$ in red and the set $\{v\}\cup I^m\setminus B_n(v)\setminus \{v'\}$ in black. None of the 2 colors is $n$-connected.