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)$ for all $C$.

In fact, 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 all colored the same way $x$ was colored in $C$. The nontriviality and sensitivity properties will clearly be preserved; all this transformation does is to eliminate the problem 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$.

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$

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.

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

7more comments