Considere la $d$ -de la red de números enteros, $Z^d$ . Llama a dos puntos en $Z^d$ "vecinos" si su distancia euclidiana es 1 (es decir, si difieren en 1 en exactamente una coordenada).
Dejemos que $C$ sea una bicolor de $Z^d$ que hace que cada punto sea rojo o azul. Supondremos que $C$ tiene la siguiente propiedad de "no trivialidad": el origen es de color rojo, pero en cada una de las $d$ ejes a través del origen, hay un punto en ese eje que es de color azul.
Que la "sensibilidad" de un punto $x$ con respecto a $C$ o $s_x(C)$ sea el número de $x$ que tienen un color diferente al de los vecinos de $x$ . Entonces dejemos que $s(C) = \max_{x \in Z^d} s_x(C)$ .
PREGUNTA: ¿Puede darme algún límite inferior decente en $s(C)$ en términos de $d$ ? Por ejemplo, que $s(C) \ge k \sqrt{d}$ para alguna constante $k > 0$ ?
OBSERVACIÓN 1: Si se demuestra una cota inferior de la forma $k d^l$ (para las constantes $k,l > 0$ ), entonces habrá resuelto un viejo problema abierto en el estudio de las funciones booleanas, a saber, el problema de la "sensibilidad frente a la sensibilidad en bloque" (planteado por Noam Nisan en 1991). Pero, por favor, ¡no dejes que eso te desanime! Mi variante se siente más accesible, e incluso puede que ya se sepa algo al respecto.
(Estaré encantado de facilitarle todos los detalles de la reducción si lo solicita. Pero la idea básica es la siguiente: que $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ sea una función booleana tal que la sensibilidad del bloque $bs(f)$ es mucho mayor que la sensibilidad $s(f)$ . Entonces debe haber una entrada $x$ de $f$ que tiene $bs(f)$ bloques sensibles disjuntos. Sea $d=bs(f)$ . Entonces podemos construir una bicolor de $Z^d$ con las propiedades enumeradas anteriormente, y tal que $s(C) \le 2 s(f)$ donde $s(f)$ es la sensibilidad de $f$ . La entrada $x$ se asigna al origen de $Z^d$ mientras que cada uno de los $d$ bloques sensibles de $x$ se asigna a uno de los ejes de $Z^d$ . Para mapear una asignación booleana a un número entero, de forma que se preserve la sensibilidad, utilizamos el Código Gris. Por último, coloreamos cada punto $y \in Z^d$ rojo o azul, dependiendo de si $f(x)$ es 0 o 1 para el punto booleano correspondiente $x$ .)
OBSERVACIÓN 2: Puedo dar un ejemplo de una coloración con $s(C) = O(\sqrt{d})$ lo que significa que $s(C) \ge k \sqrt{d}$ es realmente el mejor límite inferior que se puede esperar. Esta coloración se puede obtener partiendo de la "función de Rubinstein", una función booleana $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ con $bs(f) = n/2$ y $s(f) = 2 \sqrt{n}$ -- y luego aplicar la reducción esbozada en la Observación 1.
(Para los que estén interesados, permítanme ahora describir una coloración con $s(C) = O( \sqrt{d} )$ explícitamente. Supongamos, para simplificar, que $d$ es un cuadrado perfecto. Divida el $d$ coordenadas de $x$ en $\sqrt{d}$ "bloques" de $\sqrt{d}$ coordina cada uno. Luego colorearemos $x$ azul, si y sólo si al menos uno de los bloques tiene una única coordenada igual a $2$ y todas las demás coordenadas iguales a $0$ . Dejaré como ejercicio que verifiques que $s(C) = 2 \sqrt{d}$ .)
Nota: He editado un poco el párrafo anterior, para simplificar la construcción e insertar un factor de 2 que falta.
OBSERVACIÓN 3: Por el momento, ni siquiera tengo una prueba de que $s(C)$ tiene que crecer con $d$ (!!). Pero sospecho que al menos $s(C) \ge k \log d$ debería ser factible.
¡EDIT: Perdón por cambiar las anotaciones en medio del juego, pero tengo una mejor si quieres hablar de las bajas dimensiones (por la pregunta de domotorp más abajo)! Dejemos que $r_x(C)$ sea el número de ejes (arriba/abajo, izquierda/derecha, etc.) a lo largo de los cuales $x$ tiene un vecino con un color diferente al de $x$ es. Entonces dejemos que $r(C) = \max_x r_x(C)$ . Claramente $r(C) \le s(C) \le 2r(C)$ para todos $C$ .
De hecho, algo aún más fuerte que eso es cierto: dada cualquier coloración $C$ se puede crear una nueva coloración C' que satisfaga $s(C')=r(C)$ simplemente "explotando" cada punto $x$ en un cubo de $2^d$ puntos, que están todos coloreados de la misma manera $x$ fue coloreado en $C$ . Las propiedades de no trivialidad y sensibilidad se conservarán claramente; lo único que hace esta transformación es eliminar el problema de que un punto tenga dos vecinos de distinto color a lo largo del mismo eje. Por lo tanto, sin pérdida de generalidad, podemos cambiar la atención a $r(C)$ .
Ahora dejemos que $r_d = \min_C r(C)$ sobre todas las coloraciones no triviales $C$ de $Z^d$ .
Entonces esto es lo que sé:
$r_1 = 1$
$r_2 = 2$
$r_3 = 2$
$r_4 = 2$
$r_5 \in \lbrace 2,3 \rbrace$
ACTUALIZACIÓN: He creado una imagen que muestra una coloración explícita de $Z^3$ que satisface tanto la condición de no trivialidad como $r(C)=2$ . (Es decir, desde cada punto se puede cambiar de color moviéndose como máximo por 2 ejes diferentes). Como se ha explicado anteriormente, esto se puede convertir fácilmente en una coloración con $s(C)=2$ también.
domotorp tiene razón en que probar $r_5=3$ podría ser un gran comienzo...