The "sensitivity" of 2-colorings of the d-dimensional integer lattice

Question

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.

        ^(source)

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

Answer 1

Here I show that the sensitivity might be only two even in six dimensions. The construction is to color everything red except for the following six blue affine subspaces: (30....),(.30...),(0.3...),(...30.),(....30),(...0.3) where the numbers mean the fixed coordinates, the dots the free ones.

More generally, if we suppose that there are exactly d blue axis-aligned affine subspaces, then a simple Turan-type argument shows that d=2s^2-s is the biggest dimension where sensitivity s is possible. Let me know if you agree/need more details/proofs. See you in 7 dimensions.

Update: Here is the proof that d is the highest possible dimension if we have d blue affine subspaces (one through each axis). Since the subspaces cannot contain the origin, they all must be of the form (c000...), so they must have exactly one fix non-zero coordinate, at most s-1 fixed zeros and d-s free coordinates. This guarantees that the sensitivity is satisfied for the blue points, so now let us consider the red points. The sensitivity of a red point equals the number of subspaces that it is adjacent to (except if it is adjacent to the intersection, then it is less). So we have to ensure that at most s subspaces intersect each other, since if they don't intersect, they are automatically far (if c is at least 3). This boils down to the following combinatorial problem.

Suppose we have d sets, $B_i$ such that $|B_i|\le s-1$, $i\notin B_i$, and for any $I\subset [d]$ if $|I|>s$, then we have an $i,j\in I$ such that $i\in B_j$. The question is at most how big $d$ can be. This is related to a generalization of crossing-intersecting families first studied by Bollobas and I know it because we are just writing a paper on a very similar problem. The proof for this case is the following.

Define a directed graph with d vertices as follows. Draw a directed edge from $i$ to $j$ if $i\in B_j$. This way the outdegree of each vertex is s-1. Now forget about the directions, we will have at most d(s-1) edges and our condition says that independent sets have size at most s. This is exactly the complement of Turan's famous problem, to minimize the number of edges, we must form s equal sized cliques, so each will have size d/s. This gives d/s-1=2s-2, thus d=2s^2-s.

Answer 2

(Note: I'm new here; I don't mean to 'answer' Scott's question, but somehow I'm not seeing how to just leave a comment.)

I think an approach that uses (d-dimensional) Sperner's Lemma is definitely worth looking for, since anyone who has tried to directly find a sensitive input from a block-sensitive one knows it's a hard road.

http://en.wikipedia.org/wiki/Sperner%27s_lemma

A possible sketch 'proof' of sensitivity conjecture with gaps (I'll discuss what needs fixing after):

---

Let $C_0$ denote the 2-coloring of the $d$-lattice. suppose for concreteness that $C_0(0, 0, ... 0) =$ blue and $C_0(0, 0, ... k_i, ... 0) =$ red for each $i \leq d$. (that's $k_i$ in the $i$-th coordinate, 0 elsewhere).

Form a topological simplex with vertices $(0, .., 0)$ and $\{(0, 0, ... k_i, ... 0)\}$ (for all ${i <= d}$), by joining each pair of vertices with a lattice walk. This gives you the skeleton of a d-dimensional solid consisting of a bunch of unit cubes. Triangulate each of these cubes in some fashion, without adding new vertices.

Now we give a new coloring $Col$: a $(d+1)$-coloring of the vertices of this solid:
$Col(0, 0, ... ,0) := 0$,

$Col(v) := 0$ for any other $v$ colored blue in $C_0$,

$Col(0, 0, ... k_i, ... 0) := i$,

and... $Col(v') \in \{ 1, 2, ... ,d\}$ for other $v'$, in some clever way I haven't determined yet.

Now use Sperner's Lemma (+) to find a panchromatic simplex in the triangulation. This, we hope (++), is the sensitive point we were looking for.

---

Gaps: (+) we need $Col$ to be defined to satisfy the consistency requirements over faces. (see the Lemma's statement on wiki.)

(++) an edge of the panchromatic simplex found will be a sensitive edge iff:

(i) it goes from color $Col = 0$ to a color $Col = i \neq 0$;

(ii) it is an actual lattice edge.

The gap (+) may be impossible to rectify as stated: consider the case where the only points colored red in $C_0$ are the hypothesized points $(0, ... k_i, ... 0)$. But in this case the sensitivity at red points is high. To fill (+), we'd need to give an argument saying that WLOG the red points have a high degree of connectivity. We may also wish to jettison some of the red points and introduce more blue vertices which take on distinct colors in $Col$.

To fil (++), an 'ideal' situation would one in which all simplicial edges in our triangulation are in fact lattice edges. Then (i), (ii) would be satisfied on all edges issuing from the $Col = 0$ vertex in the panchromatic simplex, and we'd get sensitivity $d$.

This is impossible (and we can't hope for sensitivity $d$); however, perhaps there are triangulations of the d-cube in which all simplices have 'enough' lattice edges at each vertex. (I think this is false too, but I don't have a better idea yet.)

Answer 3

Just seen on twitter: Hao Huang at Emory University has given a very short argument in this preprint proving the following

Theorem 1.1. For every integer $n\geq 1$, let $H$ be an arbitrary $(2^{n-1}+1)$-vertex induced subgraph of $Q^n$, then

$$\Delta(H)\geq\sqrt{n}$$

Moreover this inequality is tight when $n$ is a perfect square.

which implies the sensitivity conjecture! This goes via the approach of Gotsman and Linial mentioned in Noam's answer.

(Here, $Q^n$ is the $n$-dimensional hypercube graph and $\Delta(H)$ denotes the maximum degree of $H$.)

The paper is very readable, and the "meat" of the argument takes up less than 2 pages and uses not much more than basic interlacing properties of eigenvalues!

Answer 4

Here's another problem that is equivalent to this one (see http://www.cs.huji.ac.il/~nati/PAPERS/gotsman_equivalence.pdf):

Consider a 2-coloring of the vertices of the n-dimensional hypercube. We say that it has a monochromatic k-star if there exists a vertex that is colored by the same color as at least k of its neighbors. Since the Hypercube is bipartite we can have a coloring without even a monochromatic 1-star -- this coloring will be exactly balanced (i.e. exactly half of the vertices get each color). What about non-balanced colorings? Define s(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a monochromatic s(n)-star. It turns out that s(n) is equal to the minimum possible sensitivity of a Boolean function of degree exactly n. [The basic idea is to look at the product of the coloring (viewed as {-1,1}) with the parity function on the n bits. The non-balancedness translates to full degree and the k-star translates to sensitivity k.]

A related problem defines r(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a r(n)-star of the majority color. This was studied by Chung, Furedi, Graham, and Seymour in 1988 (see http://www.math.ucsd.edu/~ronspubs/88_01_fractional_covering.pdf) who give essentially the same bounds as known for s(n). Thus it is known that log n <= r(n) <= s(n) <= sqrt(n), and the conjecture is that both are at least n^a for some a>0.

Answer 5

UPDATE: The converse reduction allows us to translate Kenyon and Kutin's bound for $k$-block sensitivity into a polynomial lower bound on the sensitivity of the lattice in terms of $l$, where $l$ is the minimum number such that there is a blue point within $l$ units of the origin on each axis. Kenyon and Kutin's result is that there is at most a degree $k$ gap between $s(f)$ and $bs_k(f)$ ($k$-block sensitivity is block sensitivity where blocks are restricted to at most length $k$), so $bs_k(f) \leq c_k s(f)^k$, where $c_k < \frac{e}{(k-1)!}$. Take any lattice with $d$ dimensions and sensitivity $s$. Consider the finite lattice formed by cutting off each axis after the first blue point and apply the reduction below, so the maximum axis length is $l$. Then there exists a boolean function $f$ with $bs_l(f) \geq d$, since all blocks have length at most $l$, and $s(f) \leq ls$. Then $d \leq bs_l(f) \leq c_l(ls)^l$, and $s \geq \frac{1}{l} (\frac{d}{c_l})^{\frac{1}{l}}$.

The following arose from joint work with Scott Aaronson, and provides a reduction of the lattice problem back to the original boolean functions problem, with the sensitivity changed by a certain factor.

For a 2-coloring $C$ of a $d$-dimensional lattice of size $|S_1| \times |S_2| \ldots \times |S_d|$ such that the only axial blue points are $(0,\ldots,|S_i|,\ldots,0)$, where $|S_i|$ is the $i$th coordinate, there exists a boolean function with $bs(f) \geq d$ and $s(f) \leq \max_i{|S_i|} \cdot s(C)$.

Proof: We define a function $f$ on $n=|S_1|+|S_2|+\ldots+|S_d|$ bits as follows. Divide the bits into blocks $b_1, b_2, \ldots, b_n$, where $|b_i|=|S_i|$. For an input $y=(y_1,y_2,\ldots,y_n)$, let the number of 1's in set $b_i$ be $z_i$. Let $y$ correspond to the point $(z_1,z_2,\ldots,z_d)$, so $f(y)=0$ if $(z_1,z_2,\ldots,z_d)$ is red and $f(y)=1$ if it is blue. Each of the blocks $b_i$, $1 \leq i \leq d$, is sensitive on the $n$-bit input $(0,0,\ldots,0)$. This is because flipping the bits in block $b_i$ corresponds to the point $(0,\ldots,|S_i|,\ldots,0)$ where $|S_i|$ is the $i$th coordinate, which is blue, and so $f(y^{b_i})=1$ ($y$ with bits $b_i$ flipped). Thus $bs(f) \geq d$. Furthermore, moving one coordinate along the $i$th axis on the lattice corresponds to changing one of the bits in $b_i$ of the corresponding input. Therefore, for any point $x=(x_1,x_2,\ldots,x_n)$ where the set of coordinates $X \subseteq \{1,\ldots,d\}$ are sensitive, $|X| \leq s(C)$ and so the sensitivity of $f$ on the corresponding input is at most $\sum_{i \in X} b_i \leq s(C) \cdot \max_i b_i$. This shows that $s(f) \leq s(C) \cdot \max_i b_i$.

Answer 6

There's been some discussion of searching for improvements to Rubinstein's example, i.e., much larger gaps between sensitivity and block sensitivity. I will argue that any such improvement would have to make a significant departure from the original example, and deviate from a natural approach one would be tempted to follow. This observation has surely been made by others who've worked on the problem. [Note: the argument I'll give can be summarized by the relation $bs_0(f) = O(s_0(f)C_1(f))$. Probably one of the early known facts (references would be appreciated...), and if so I probably read the proof at some point.]

I'll be talking about the original, Boolean-functions problem. Say we want the sensitivity to be at most $m$, and the block sensitivity to be at least $k \gg m$. (Don't worry about their relation to $n$, the input length.)

Recall that $s_0(f)$ is the maximum over all 0-inputs $x$ to $f$, of the number of sensitive coordinates of $x$. Similarly, $s_1(f)$ is max over all 1-inputs. A natural way to try to make $s(f) \leq m$ hold is to define $f$ as an OR over a collection $\mathcal{G}$ of functions $g_t$, each of which depends on at most $m$ variables. This way, we are at least ensured $s_1(f) \leq m$.
(An equivalent assumption is that $f$ is an $m$-DNF. Another equivalent rephrasing in terms of certificate complexity is that $C_1(f) \leq m$.) Rubinstein's function is easily seen to be of this type. Now I'll argue that for any $m$-DNF $f$, we have $s_0(f) = \Omega(k/m)$. If $s_1(f) = \Theta(m)$ as our approach leads us to expect, then combining we conclude that $s(f) = \Omega(\sqrt{k})$. (But note, this falls short of being a proof of this relation for all $m$-DNFs, since by a more refined approach one could hope to have $s_1(f) \ll m$.)

OK, let's prove that for $f = \bigvee_{g_t \in \mathcal{G}}g_t$ as above, $s_0(f) = \Omega(k/m)$.

Assume WLOG that the all-zeroes input $0$ satisfies $f(0) = 0$, and has $k$ disjoint, minimal sensitive blocks $B_1, \ldots, B_k$. Let $0^{(B_j)}$ denote the all-zero input with bits in $B_j$ flipped to 1, so that $f(0^{(B_j)}) = 1$.

For each block $B_j$, there is a function $g_j \in \mathcal{G}$ that equals 1 on input $0^{(B_j)}$. Let $u^j \in (0, 1, *)^n$ be the restriction of $0^{(B_j)}$ to $S_j := dom(g_j) \subset [n]$, the set of $ \leq m$ inputs on which $g_j$ depends. By minimality of $B_j$, we have $B_j \subseteq S_j$; the containment may be proper.

Say that $a, b \in (0, 1, *)$ disagree if they're both Boolean and distinct; otherwise say they agree. Say that strings $u, u' \in (0, 1, *)^n$ are compatible if there's no coordinate $i \in [n]$ for which $u_i, u'_i$ disagree.

Claim 1: There is a set $A \subseteq [k]$ of size $\Omega(k/m)$, such that $u^j, u^\ell$ are compatible for all $j, \ell \in A$.

Proof: For $i \in [n]$, let $\sharp (i)$ denote the number of pairs $j, \ell \in [k]$ such that $u^j, u^\ell$ disagree on the $i$-th coordinate.

Note that if $u^j_i = 0$, then there is at most one $\ell \in [k]$ for which $u^j, u^\ell$ disagree on the $i$-th coordinate. (This is because the sets $B_\ell$ are pairwise disjoint.) Thus, $\sum_i \sharp (i)$ is at most the number of 0's in the strings $u^1, \ldots, u^k$; this is at most $mk$. Then by averaging, there exists $j \in [k]$ such that $\sum_{i \in B_j} \sharp (i) \leq m$; again we're using disjointness of the $B_\ell$'s.

Add this index $j$ to $A$, and `delete' $j$ along with all indices $\ell \in [k]$ for which $u^j, u^\ell$ are incompatible. By our choice of $j$, there are at most $m$ indices $\ell \in [k]$ for which $u^j, u^\ell$ disagree somewhere on $B_j$. Also, our earlier observations tell us that at most one $u^\ell$ disagrees with $u^j$ on each coordinate in $S_j \setminus B_j$. Thus we only delete at most $m+m = 2m$ indices $\ell$ along with $j$.

Now repeat the same procedure on the remaining indices. Continuing in this fashion, we build up a set $A$ of at least $k/(2m+1) = \Omega(k/m)$ indices; by construction $u^j, u^\ell$ are consistent for $j, \ell \in A$, as desired. $\clubsuit$

The rest of the proof follows a familiar pattern. Initialize $x := 0^n$ (so $f(x) = 0$). Repeatedly flip bits of $\bigcup_{j \in A} B_j$ to 1, while preserving the property $f(x) = 0$. The strings $u^j$, $j \in A$ are mutually compatible, so our flips never increase the disagreement between $x$ and any $u^j$, $j \in A$. If $x$ ever becomes compatible with any $u^j$, then $f(x) = g_j(x) = 1$, so eventually our flipping process gets stuck at some value $x$; it follows that $x$ has a sensitive coordinate on $B_j$ for each $j \in A$. Thus $s_0(f) \geq |A| = \Omega(k/m)$, as we wanted to show.

Answer 7

The following is a generalization of domotorp's construction for $r_6=2$, which constructs a coloring on a $d$-dimensional lattice with $d=2s^2-s$.

We can construct the following $(2s-1)s$-dimensional certificates which we will color blue, each divided into $s$ groups of $2s-1$ coordinates each. We define the $s(2s-1)$ coordinates $x_{\{i,j\}}$, where $1 \leq i \leq s$ and $1 \leq j \leq 2s-1$. The certificate $S_{\{i,j\}}$ consists of those vectors for which $x_{\{i,j\}}=3$ and $x_{\{i,j+1\}},\ldots, x_{\{i,j+s-1\}}=0$, where addition of coordinates is modulo $2s-1$, allowing for wraparound.

We can now define a coloring where a point is colored blue if it is in a certificate $S_{\{i,j\}}$ and red otherwise. This satisfies the non-triviality condition because for any coordinate $x_{\{i,j\}}$, the certificate $S_{\{i,j\}}$ contains the point along the coordinate axis in that direction with $x_{\{i,j\}}=3$ and $x_{\{a,b\}}=0$ for all $(a,b)\neq(0,0)$.

The blue to red sensitivity of this coloring, which is the maximum sensitivity of blue points, is $s$ because for any point in a certificate $S_{\{i,j\}}$, only changing one of the $s$ coordinates $x_{\{i,j\}}, x_{\{i,j+1\}},\ldots, x_{\{i,j+s-1\}}$ yields an adjacent red point. Furthermore, the red to blue sensitivity is also $s$. For a point $p$ and a certificate $S_{\{i,j\}}$, if $p$ is adjacent to $S_{\{i,j\}}$ then $2 \leq x_{\{i,j\}} \leq 4$ and $-1 \leq x_{\{i,j+1\}},\ldots, x_{\{i,j+s-1\}} \leq 1$. So for a point $p$ and a fixed index $a$, $1 \leq a \leq s$, $p$ can be adjacent to at most one certificate of the form $S_{\{a,j\}}$ because two of these strings of $s$ coordinates cannot fit in $2s-1$ coordinates. Ranging over all $a$, a point can be adjacent to at most $s$ certificates, and so the red to blue sensitivity is at most $s$.

Therefore the coloring has sensitivity $s$, and $d=(2s-1)s=2s^2-s$.

Answer 8

The problem has an interaction between local and global that suggests pursuing an analogy with a geometric result that relates the two sorts of information. Here is a program based (perhaps quite loosely) on the generalized Gauss-Bonnet theorem. In very broad terms:

1. Define a piecewise linear manifold that surrounds a component of the red set.

2. Define an appropriate notion of curvature for piecewise linear manifolds.

3. Show that if the sensitivity at a point is below a certain threshhold, the curvature must vanish there.

4. Show that if the curvature vanishes everywhere, then the manifold has a geometric structure that is inconsistent with the nontriviality condition.

The rest of this is devoted to fleshing this out a bit.

Let $V = ({\mathbf Z}_N)^d$ for some integer $N$. (We don't work in ${\mathbf Z}^d$ because, for the time being at least, we don't want to worry about the possibility that the manifold we will construct is not compact.) Let $G = (V,E)$ be the cubical lattice, which is to say that it is the graph with vertex set $V$ whose edge set $E$ is the set of pairs $\{v,v'\}$ with $v_i \ne v'_i$ for exactly one $i$, for which we have $v'_i = v_i \pm 1$. Geometrically we will think of this as embedded in the torus $(\Re/N{\mathbf Z})^d$, which we endow with the obvious (flat) Riemannian metric.

Suppose $V = R \cup B$ where is $R$ and $B$ are nonempty and disjoint. We can assume that subgraph of $G$ induced by $R$ is connected because we can replace $R$ with one of its components. We now want to wrap $R$ in piecewise linear cellophane, which is to say that we will construct a PL hypersurface $M$ that has $R$ on one side and $B$ on the other. The vertex set $W$ of this hypersurface will have one point in each edge in $E$ whose two endpoints have different colors.

We now need to say what the simplices of positive dimension are. Let ${\mathbf e}_1, \ldots, {\mathbf e}_d$ be the ``standard unit basis''; we will think of these both as group elements and particular points. To be completely concrete, suppose that the origin is in $R$ and ${\mathbf e}_1$ is in $B$. Then $w_1 = \tfrac13 {\mathbf e}_1$ will be the point in the edge between these points where this edge intersects $M$. We need to define a neighborhood of $w_1$ in $M$. Let's first define the neighbors of $w$ in the 1-skeleton of $M$. Consider $j = 2, \ldots, d$. If ${\mathbf e}_j$ is in $B$, let $w_j = \tfrac13 {\mathbf e}_j$. If ${\mathbf e}_j$ is in $R$ and ${\mathbf e}_1 + {\mathbf e}_j$ is in $B$, let $w_j = \tfrac13 {\mathbf e}_1 + {\mathbf e}_j$. If ${\mathbf e}_j$ and ${\mathbf e}_1 + {\mathbf e}_j$ are in $R$, let $w_j = {\mathbf e}_1 + \tfrac23 {\mathbf e}_j$.

Let $w_{-j}$ be what we get from this construction with ${\mathbf e}_j$ replaced by $-{\mathbf e}_j$. We would like to define $M$ to be the union over all such $w_1$ of the union the $(d-1)$-simplices obtained by taking the convex hull of $w_1, w_{i_2}, \ldots, w_{i_d}$ where each $i_j \in \{j,-j\}$. Of course we should verify that $M$ so defined is in fact a manifold, but I want to leave this aside and move on to the question of curvature. (If this construction doesn't work, maybe it can be fixed, or something similar does work.) There are of course many notions of curvature in differential geometry. For many of these it should be possible to define some analogue in the piecewise linear case, but any such project is likely to be tedious, and we would like to find some simpler way.

For a surface in three space, the Gaussian curvature can be thought of as the determinant of the Jacobean of the map taking each point in the surface to the unit normal vector in the two sphere. If this curvature vanishes everywhere in some open set, then in this set the surface is locally isometric to flat two space. (This is a special case of Gauss' theorema egregium.) This suggests that we define the $dimension\; of\; flatness$ at $w_1$ to be the dimension of the largest linear subspace (I know we are inside a torus, but you know what I mean) $L$ such that near $w_1$, $M$ agrees with the sum of $L$ and a manifold $N$, and the sum of the dimensions of $L$ and $N$ is $d-1$.

We would now like to study the relationship between the dimension of flatness at $w_1$ and the sensitivities at the origin and ${\mathbf e}_1$. Also, the dimension of flatness of the $M$ derived from the Rubinstein example may be a very useful guide to how to proceed. The general idea is that low sensitivity implies a high dimension of flatness, which in turn will have the implication that $M$ is the cartesian product (or a sum, algebraicly) of an $n$-manifold $N$ and a $(d - n - 1)$-dimensional torus. And of course there might be various other ideas to pursue in this general direction.

Answer 9

Here is a videotaped lecture by Miks Saks describing another approach to the conjecture. https://youtu.be/hYfeRtdj7cw?t=7m32s

Answer 10

The following is an elaboration of ideas I posted on the philomath page, but written a lot more cleanly and nicely typeset. It builds on ideas of several previous contributors:

First, note that if the $O(\sqrt{d})$ bound fails, then for arbitrarily large $k>0$ there's a $Z^d$ with coloring $C$ such that $r(C)+1 < \sqrt{d/k}$, i.e. wlog we can fix a $k>0$ and assume that $d > k(r+1)^2$. I'm going to just choose $k=1$ here and assume $d > (r+1)^2$.

Consider a blue point $p\in Z^d$. Let $N_p=\{e_i : p+e_i \text{ is red or } p-e_i \text{ is red}\}$, and let $n=|N_p|$. I'll call $N_p$ the set of normal directions at $p$. Also define $T_p=\{e_j:p\pm e_j \text{ are both blue and } N_p\subset N_{p+e_j}\cap N_{p-e_j}\}$ and $t=|T_p|$. I'll call these the tangent directions at $p$. (Informally: the axes we can move along from $p$ to keep our color and previous normal directions intact. Note that there are often going to be coordinate directions that are neither normal nor tangent at $p$). By eliminating the directions of sensitivity around $p$ and around $n$ adjacent red points in the normal directions, we see that $t\geq d-r(n+1)$. Since $n\leq r$ by definition, and $d > r(r+1)$ by the previous paragraph, we know that $d-r(n+1)>0$ and so $t>0$ at every $p$.

Let $P$ be the plane at $p$ spanned by $T_p$. One of two cases must hold:

1) Every point $q\in P$ is blue with $N_p=N_q$ (e.g. we get a monochromatic plane of dimension $\geq d-r(n+1)$ with exactly the same original normal directions), or,

2) There exists a $p'\in P$ with $N_p\subsetneq N_{p'}$.

However, since $n\leq r$ for all points, and case 2 gives a new point with strictly larger $n$, induction gives the following:

Let $p$ be a blue point, let $P'$ be the plane at $p$ spanned by the $e_i\notin N_p$. Then there exists an affine plane $P''\subset P'$ with dimension at least $d-r(r+1)$ such that for every $q\in P''$, $q$ is blue and $N_q=N_{P''}$, where $N_p\subset N_{P''}$.

[In particular, if $p$ is a point of maximum sensitivity, it automatically belongs to a plane of dimension $d-r(r+1)>0$ whose points are all the same color, and all of maximum sensitivity.]

At this point my first idea is to extend/mimic the example Gowers posted in the philomath thread as follows: At each coordinate axis $e_i$ there is a first blue point $p_i$ with $e_i \in N_{p_i}$. Applying the above gives affine planes $P_i''$ with constant normal directions $N_i$, $e_i\in N_i$. Since any particular $P_i''$ has at most $r$ normal directions, there must be at least $m=d/r$ distinct $P_i''$ planes. If we could argue that $m\leq r$, or something similar, we'd be done. But we can't directly copy Gowers' argument here because the eventual $P_i''$ planes we wind up with aren't necessarily homogeneous with respect to the non-$e_i$ coordinates..

Unfortunately nothing so far used the fact that the blue points are on the coordinate axes, which will have to get used to avoid the INDEX LOOKUP counterexample. Of course, replicating the Gowers argument may be entirely unnecessary, since we already assumed at the start that the $O(\sqrt{d})$ bound failed in order to guarantee positive dimension tangent planes, which may already be enough (along with the coordinate axis blue points) to force some contradiction.

One idea I haven't thought through but may work is to find a way to argue that $P_i''$ must be homogeneous in all but ~$r$ coordinates and derive some bound like $m\leq r^c$ for some $c$ out of this, which gives a polynomial bound overall when combined with the inequality we already have. It might be useful in this approach to modify the original assumption $r+1<\sqrt{d}$, to something like $r+1 < d^{1/3}$, which would guarantee $r(r+1) < \frac{d}{r+1}$, so $d-r(r+1) > d(1-\frac{1}{r+1})$, which gives larger dimension planes to work with and force intersections between, while maintaining the potential for a polynomial bound result.