EDIT: Sorry to switch notations in the middle of the game, but I have a better one if you want to talk about low dimensions (per domotorp's question below)! Let's let $r_x(C)$ be the number of axes (up/down, left/right, etc.) along which $x$ has a neighbor that's colored differently than $x$ is. Then let $r(C) = \max_x r_x(C)$. Clearly $r(C) \le s(C) \le 2r(C)$ for all $C$.

In fact, so asymptotically the two something even stronger than that is true: given any coloring $C$, one can create a new coloring C' that satisfies $s(C')=r(C)$, by simply "blowing up" each point $x$ into a cube of $2^d$ points, which are equivalent. But all colored the same way $r(C)$ more closely models what I know from x$ was colored in $C$. The nontriviality and sensitivity properties will clearly be preserved; all this transformation does is to eliminate the Boolean function caseproblem of a point having two differently-colored neighbors along the same axis. So without loss of generality, we can shift attention to $r(C)$.

Now let $r_d = \min_C r(C)$ over all nontrivial colorings $C$ of $Z_d$.Z^d$.

UPDATE: I created an image that shows an explicit coloring of $Z^3$ that satisfies both the nontriviality condition and $r(C)=2$. (That is, from every point, you can change color by moving along at most 2 different axes.) As explained above, this can easily be converted into a coloring with $s(C)=2$ as well.

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).

Let $C$ be a two-coloring of $Z^d$, which makes each point either red or blue. We'll assume $C$ has the following "nontriviality" property: the origin is colored red, but on each of the $d$ axes through the origin, there's a point on that axis that's colored blue.

Let the "sensitivity" of a point $x$ with respect to $C$, or $s_x(C)$, be the number of $x$'s neighbors that are colored differently from $x$. Then let $s(C) = \max_{x \in Z^d} s_x(C)$.

QUESTION: Can you give me any decent lower bound on $s(C)$ in terms of $d$? For example, that $s(C) \ge k \sqrt{d}$ for some constant $k > 0$?

REMARK 1: If you prove a lower bound of the form $k d^l$ (for constants $k,l > 0$), then you'll have solved an old open problem in the study of Boolean functions, namely the "sensitivity versus block sensitivity" problem (posed by Noam Nisan in 1991). But please don't let that discourage you! My variant feels more approachable, and maybe something is even already known about it.

(I'll be happy to supply full details of the reduction on request. But here's the basic idea: let $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ be a Boolean function such that the block sensitivity $bs(f)$ is much much larger than the sensitivity $s(f)$. Then there must be an input $x$ of $f$ that has $bs(f)$ disjoint sensitive blocks. Let $d=bs(f)$. Then we can construct a two-coloring of $Z^d$ with the properties listed above, and such that $s(C) \le 2 s(f)$ where $s(f)$ is the sensitivity of $f$. The input $x$ gets mapped to the origin of $Z^d$, while each of the $d$ sensitive blocks of $x$ gets mapped to one of the axes of $Z^d$. To map a Boolean assignment to an integer, in a way that preserves the sensitivity, we use the Gray Code. Finally, we color each point $y \in Z^d$ either red or blue, depending on whether $f(x)$ is 0 or 1 for the corresponding Boolean point $x$.)

REMARK 2: I can give an example of a coloring with $s(C) = O(\sqrt{d})$, meaning that $s(C) \ge k \sqrt{d}$ really is the best lower bound one can hope for. This coloring can be obtained by starting from "Rubinstein's function" -- a Boolean function $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ with $bs(f) = n/2$ and $s(f) = 2 \sqrt{n}$ -- and then applying the reduction sketched in Remark 1.

(For those who are interested, let me now go ahead and describe a coloring with $s(C) = O( \sqrt{d} )$ explicitly. Assume for simplicity that $d$ is a perfect square. Partition the $d$ coordinates of $x$ into $\sqrt{d}$ "blocks" of $\sqrt{d}$ coordinates each. Then we'll color $x$ blue, if and only if at least one of the blocks has a single coordinate equal to $2$ and all other coordinates equal to $0$. I'll leave it as an exercise for you to verify that $s(C) = 2 \sqrt{d}$.)

Note: I edited the above paragraph a little, to simplify the construction and insert a missing factor of 2.

REMARK 3: At the moment, I don't even have a proof that $s(C)$ has to grow with $d$ (!!). But I suspect at least $s(C) \ge k \log d$ ought to be doable.

EDIT: Sorry to switch notations in the middle of the game, but I have a better one if you want to talk about low dimensions (per domotorp's question below)! Let's let $r_x(C)$ be the number of axes (up/down, left/right, etc.) along which $x$ has a neighbor that's colored differently than $x$ is. Then let $r(C) = \max_x r_x(C)$. Clearly $r(C) \le s(C) \le 2r(C)$, so asymptotically the two are equivalent. But $r(C)$ more closely models what I know from the Boolean function case.

Now let $r_d = \max_C min_C r(C)$ over all nontrivial colorings $C$ of $Z_d$.

Then here's what I know:

$r_1 = 1$

$r_2 = 2$

$r_3 = 2$

$r_4 = 2$

$r_5 \in \lbrace 2,3 \rbrace$

domotorp is right that proving $r_5=3$ could be a great start...

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).

Let $C$ be a two-coloring of $Z^d$, which makes each point either red or blue. We'll assume $C$ has the following "nontriviality" property: the origin is colored red, but on each of the $d$ axes through the origin, there's a point on that axis that's colored blue.

Let the "sensitivity" of a point $x$ with respect to $C$, or $s_x(C)$, be the number of $x$'s neighbors that are colored differently from $x$. Then let $s(C) = \max_{x \in Z^d} s_x(C)$.

QUESTION: Can you give me any decent lower bound on $s(C)$ in terms of $d$? For example, that $s(C) \ge k \sqrt{d}$ for some constant $k > 0$?

REMARK 1: If you prove a lower bound of the form $k d^l$ (for constants $k,l$), k,l > 0$), then you'll have solved an old open problem in the study of Boolean functions, namely the "sensitivity versus block sensitivity" problem (posed by Noam Nisan in 1991). But please don't let that discourage you! My variant feels more approachable, and maybe something is even already known about it.

(I'll be happy to supply full details of the reduction on request. But here's the basic idea: let $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ be a Boolean function such that the block sensitivity $bs(f)$ is much much larger than the sensitivity $s(f)$. Then there must be an input $x$ of $f$ that has $bs(f)$ disjoint sensitive blocks. Let $d=bs(f)$. Then we can construct a two-coloring of $Z^d$ with the properties listed above, and such that $s(C) \le 2 s(f)$ where $s(f)$ is the sensitivity of $f$. The input $x$ gets mapped to the origin of $Z^d$, while each of the $d$ sensitive blocks of $x$ gets mapped to one of the axes of $Z^d$. To map a Boolean assignment to an integer, in a way that preserves the sensitivity, we use the Gray Code. Finally, we color each point $y \in Z^d$ either red or blue, depending on whether $f(x)$ is 0 or 1 for the corresponding Boolean point $x$.)

REMARK 2: I can give an example of a coloring with $s(C) = O(\sqrt{d})$, meaning that $s(C) \ge k \sqrt{d}$ really is the best lower bound one can hope for. This coloring can be obtained by starting from "Rubinstein's function" -- a Boolean function $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ with $bs(f) = n/2$ and $s(f) = 2 \sqrt{n}$ -- and then applying the reduction sketched in Remark 1.

(For those who are interested, let me now go ahead and describe a coloring with $s(C) = O( \sqrt{d}$ sqrt{d} )$ explicitly. Assume for simplicity that $d$ is a perfect square. Given a point $x \in Z^d$, let $x' \in Z_4^d$ be the point obtained by reducing each of the coordinates of $x$ modulo 4. Partition the $d$ coordinates of $x'$ x$ into $\sqrt{d}$ "blocks" of $\sqrt{d}$ coordinates each. Then we'll color $x$ blue, if and only if at least one of the blocks in $x'$ has a single coordinate equal to $2$ and all other coordinates equal to $0$. I'll leave it as an exercise for you to verify that $s(C) = 2 \sqrt{d}$.)

Note: I edited the above paragraph a little, to simplify the construction and insert a missing factor of 2.

REMARK 3: At the moment, I don't even have a proof that $s(C)$ has to grow with $d$ (!!). But I suspect at least $s(C) \ge k \log d$ ought to be doable.

EDIT: Sorry to switch notations in the middle of the game, but I have a better one if you want to talk about low dimensions (per domotorp's question below)! Let's let $r_x(C)$ be the number of axes (up/down, left/right, etc.) along which $x$ has a neighbor that's colored differently than $x$ is. Then let $r(C) = \max_x r_x(C)$. Clearly $r(C) \le s(C) \le 2r(C)$, so asymptotically the two are equivalent. But $r(C)$ more closely models what I know from the Boolean function case.

Now let $r_d = \max_C r(C)$ over all colorings $C$ of $Z_d$.

Then here's what I know:

$r_1 = 1$

$r_2 = 2$

$r_3 = 2$

$r_4 = 2$

$r_5 \in \lbrace 2,3 \rbrace$

domotorp is right that proving $r_5=3$ could be a great start...

EDIT: Sorry to switch notations in the middle of the game, but I have a better one if you want to talk about low dimensions (per domotorp's question below)! Let's let $r_x(C)$ be the number of axes (up/down, left/right, etc.) along which $x$ has a neighbor that's colored differently than $x$ is. Then let $r(C) = \max_x r_x(C)$. Clearly $r(C) \le s(C) \le 2r(C)$, so asymptotically the two are equivalent. But $r(C)$ more closely models what I know from the Boolean function case.

Now let $r_d = \max_C r(C)$ over all colorings $C$ of $Z_d$.

Then here's what I know:

$r_1 = 1$

$r_2 = 2$

$r_3 = 2$

$r_4 = 2$

$r_5 \in \lbrace 2,3 \rbrace$

domotorp is right that proving $r_5=3$ could be a great start...

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).

Let $C$ be a two-coloring of $Z^d$, which makes each point either red or blue. We'll assume $C$ has the following "nontriviality" property: the origin is colored red, but on each of the $d$ axes through the origin, there's a point on that axis that's colored blue.

Let the "sensitivity" of a point $x$ with respect to $C$, or $s_x(C)$, be the number of $x$'s neighbors that are colored differently from $x$. Then let $s(C) = \max_{x \in Z^d} s_x(C)$.

QUESTION: Can you give me any decent lower bound on $s(C)$ in terms of $d$? For example, that $s(C) \ge k \sqrt{d}$ for some constant $k > 0$?

REMARK 1: If you prove a lower bound of the form $k d^l$ (for constants $k,l$), then you'll have solved an old open problem in the study of Boolean functions, namely the "sensitivity versus block sensitivity" problem (posed by Noam Nisan in 1991). But please don't let that discourage you! My variant feels more approachable, and maybe something is even already known about it.

(I'll be happy to supply full details of the reduction on request. But here's the basic idea: let $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ be a Boolean function such that the block sensitivity $bs(f)$ is much much larger than the sensitivity $s(f)$. Then there must be an input $x$ of $f$ that has $bs(f)$ disjoint sensitive blocks. Let $d=bs(f)$. Then we can construct a two-coloring of $Z^d$ with the properties listed above, and such that $s(C) \le 2 s(f)$ where $s(f)$ is the sensitivity of $f$. The input $x$ gets mapped to the origin of $Z^d$, while each of the $d$ sensitive blocks of $x$ gets mapped to one of the axes of $Z^d$. To map a Boolean assignment to an integer, in a way that preserves the sensitivity, we use the Gray Code. Finally, we color each point $y \in Z^d$ either red or blue, depending on whether $f(x)$ is 0 or 1 for the corresponding Boolean point $x$.)

REMARK 2: I can give an example of a coloring with $s(C) = O(\sqrt{d})$, meaning that $s(C) \ge k \sqrt{d}$ really is the best lower bound one can hope for. This coloring can be obtained by starting from "Rubinstein's function" -- a Boolean function $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ with $bs(f) = n/2$ and $s(f) = 2 \sqrt{n}$ -- and then applying the reduction sketched in Remark 1.

(For those who are interested, let me now go ahead and describe a coloring with $s(C) = \sqrt{d}$ explicitly. Assume for simplicity that $d$ is a perfect square. Given a point $x \in Z^d$, let $x' \in Z_4^d$ be the point obtained by reducing each of the coordinates of $x$ modulo 4. Partition the $d$ coordinates of $x'$ into $\sqrt{d}$ "blocks" of $\sqrt{d}$ coordinates each. Then we'll color $x$ blue, if and only if at least one of the blocks in $x'$ has a single coordinate equal to $2$ and all other coordinates equal to $0$. I'll leave it as an exercise for you to verify that $s(C) = \sqrt{d}$.)

REMARK 3: At the moment, I don't even have a proof that $s(C)$ has to grow with $d$ (!!). But I suspect at least $s(C) \ge k \log d$ ought to be doable.