we do not have such an example for even s at the moment.

Regarding the maximizing example, it’s non-unique. Another function that achieves s=3, bs=6 is as follows:
- Denote the variables as x_0, x_1, x_2, y_0, y_1, y_2, z_0, z_1, z_2.
- If there is an i such that x_i\neq y_i and x_{(i+1) mod 3}=y_{i+1}, let f=(y_i+y_{(i+1) mod 3}+z_i) mod 2. (If such i exists, it is unique because we either have only one i:x_i=y_i or only one i:x_i\neq y_i.)
- Otherwise, let f=(x_0+x_1+x_2) mod 2.

We do not know if there are more functions or not. The drawback of using a SAT solver is that it outputs one solution to the SAT instance, not all solutions. Madars tried several different SAT solvers. One of them gave the modified Rubinstein function, the other gave the function above.

Start at a blue point with k red points adjacent to it. There are at least d-(k+1)r coordinate axes (“tangent coordinates”) we can move along from the blue point that gets us to another blue point with at least k red points in the same “normal directions” as before. Note that this number is positive unless d is less than or equal to r(r+1), in which case the sqrt(d) bound holds, so for contradiction purposes we can assume it always positive. In fact, we can assume, say, d-(k+1)r is at least d/2, or any other constant multiple of d, by the same argument.

Moving along these directions, one of two things can happen: 1) The same tangent directions work always, and we get a plane of dimension d-(k+1)r with k constant normal directions. This is a slight generalization of a property Gowers assumes above. Or, 2) at some blue point the previous tangent direction now contains a red point. In this case, this blue point now has at least (k+1) normal directions, and applying the above result, we can continue from here along a new d-(k+2)r dimensional plane with (k+1) fixed normal directions. Repeating the above, case 2) can only happen a finite number of times, namely, until we reach a blue point with r (mutually perpendicular) normal directions, i.e. a point with maximum sensitivity. In particular, any point of maximum sensitivity must belong to a d-(r+1)r dimensional plane, where every point in the plane has maximum sensitivity, the same color, and the same normal directions.

Now build on Gowers’ idea. Consider the possible maximum-sensitivity planes reachable from each of the d blue points on coordinate axes. Note that by construction, the plane(s) associated to the ith coordinate axis have constant ith coordinate (b/c there’s a normal in that direction always). Each max-sensitivity plane has at most 2r normal directions, and each contains the normal direction from the original coordinate axis, so there must be are at least d/2r such max-sensitivity planes.

I think we might be able to push through the other side of the inequality with at least a polynomial bound but I need to go to sleep now and I’m thinking there’s a good chance some or all of the above is wrong..

To be continued..

I mention this again because I agree with previous comments that this problem has a topological/Sperner’s lemma “feel” to it, and a periodic coloring can be pushed to the d-dimensional torus, which has some significant topological differences from R^d. (Also, the periodicity comes naturally from how the coloring problem arose from the original boolean function problem.)

So I propose the torus-coloring sensitivity problem as a variant for consideration, whose results still strictly translate over to the original boolean function problem.

http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice/33399