show/hide this revision's text 5 deleted 22 characters in body

(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 directly uses (d-dimensional) Sperner's Lemma is definitely worth looking for, since anyone who has tried directly to directly find a sensitive input from a hypothesized 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.)
show/hide this revision's text 4 edited body

(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 directly uses (d-dimensional) Sperner's Lemma is definitely worth looking for, since anyone who has tried directly to find a sensitive input from a hypothesized 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.)
show/hide this revision's text 3 added 16 characters in body

(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 directly uses (d-dimensional) Sperner's Lemma is definitely worth looking for, since anyone who has tried directly to find a sensitive input from a hypothesized 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.)
show/hide this revision's text 2 extended sketch
show/hide this revision's text 1