show/hide this revision's text 3 deleted 194 characters in body

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$. Since we do not have a converse reduction from this coloring problem to the boolean functions problem, however, we cannot improve the constant of the quadratic gap in the Sensitivity Conjecture.
show/hide this revision's text 2 deleted 7 characters in body; edited body

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 \emph{blue 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}}$ only if 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$. Since we do not have a converse reduction from this coloring problem to the boolean functions problem, however, we cannot improve the constant of the quadratic gap in the Sensitivity Conjecture.
show/hide this revision's text 1

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 \emph{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}}$, $p$ is adjacent to $S_{{i,j}}$ only if $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$. Since we do not have a converse reduction from this coloring problem to the boolean functions problem, however, we cannot improve the constant of the quadratic gap in the Sensitivity Conjecture.