54 votos

La "sensibilidad" de los 2 colores de la red entera d-dimensional

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.

        (fuente)

domotorp tiene razón en que probar $r_5=3$ podría ser un gran comienzo...

10voto

domotorp Puntos 6851

Aquí muestro que la sensibilidad podría ser sólo de dos incluso en seis dimensiones. La construcción consiste en colorear todo de rojo excepto los siguientes seis subespacios afines azules: (30....),(.30...),(0.3...),(...30.),(....30),(...0.3) donde los números significan las coordenadas fijas, los puntos las libres.

En términos más generales, si suponemos que hay exactamente d subespacios afines alineados con el eje azul, entonces un simple argumento de tipo Turan muestra que d=2s^2-s es la mayor dimensión en la que la sensibilidad s es posible. Hazme saber si estás de acuerdo/necesitas más detalles/pruebas. Nos vemos en 7 dimensiones.

Actualización: Aquí está la prueba de que d es la mayor dimensión posible si tenemos d subespacios afines azules (uno por cada eje). Como los subespacios no pueden contener el origen, todos deben ser de la forma (c000...), por lo que deben tener exactamente una coordenada fija distinta de cero, como máximo s-1 ceros fijos y d-s coordenadas libres. Esto garantiza que la sensibilidad se satisface para los puntos azules, así que ahora consideremos los puntos rojos. La sensibilidad de un punto rojo es igual al número de subespacios a los que es adyacente (excepto si es adyacente a la intersección, entonces es menor). Por lo tanto, debemos asegurarnos de que como máximo s subespacios se cruzan entre sí, ya que si no se cruzan, son automáticamente lejanos (si c es al menos 3). Esto se reduce al siguiente problema combinatorio.

Supongamos que tenemos d conjuntos, $B_i$ tal que $|B_i|\le s-1$ , $i\notin B_i$ y para cualquier $I\subset [d]$ si $|I|>s$ , entonces tenemos un $i,j\in I$ tal que $i\in B_j$ . La cuestión es, como mucho, cómo de grande es $d$ puede ser. Esto está relacionado con una generalización de las familias de cruce-intersección estudiada por primera vez por Bollobas y lo sé porque acabamos de escribir un papel sobre un problema muy similar. La prueba para este caso es la siguiente.

Defina un grafo dirigido con d vértices como sigue. Dibuja una arista dirigida desde $i$ à $j$ si $i\in B_j$ . De este modo, el grado exterior de cada vértice es s-1. Ahora olvídate de las direcciones, tendremos a lo sumo d(s-1) aristas y nuestra condición dice que los conjuntos independientes tienen un tamaño a lo sumo s. Esto es exactamente el complemento del famoso problema de Turan, para minimizar el número de aristas, debemos formar s camarillas de igual tamaño, por lo que cada una tendrá un tamaño d/s. Esto da d/s-1=2s-2, por tanto d=2s^2-s.

9voto

devnul3 Puntos 560

(Nota: Soy nuevo aquí; no pretendo "responder" a la pregunta de Scott, pero por alguna razón no veo cómo dejar un comentario).

Creo que merece la pena buscar un enfoque que utilice el Lemma de Sperner (d-dimensional), ya que cualquiera que haya intentado encontrar directamente una entrada sensible a partir de una sensible al bloque sabe que es un camino difícil.

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

Un posible esbozo de "prueba" de la conjetura de sensibilidad con lagunas (después hablaré de lo que hay que arreglar):


Dejemos que $C_0$ denotan la 2-coloración de la $d$ -Supongamos, para concretar, que $C_0(0, 0, ... 0) =$ azul y $C_0(0, 0, ... k_i, ... 0) =$ rojo para cada $i \leq d$ . (eso es $k_i$ en el $i$ -ésima coordenada, 0 en el resto).

Formar un simplex topológico con vértices $(0, .., 0)$ y $\{(0, 0, ... k_i, ... 0)\}$ (para todos los ${i <= d}$ ), uniendo cada par de vértices con un paseo de celosía. Esto te da el esqueleto de un sólido d-dimensional que consiste en un montón de cubos unitarios. Triangula cada uno de estos cubos de alguna manera, sin añadiendo nuevos vértices.

Ahora damos un nuevo colorido $Col$ : a $(d+1)$ -coloración de los vértices de este sólido:
$Col(0, 0, ... ,0) := 0$ ,

$Col(v) := 0$ para cualquier otro $v$ de color azul en $C_0$ ,

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

y... $Col(v') \in \{ 1, 2, ... ,d\}$ para otros $v'$ de alguna manera inteligente que aún no he determinado.

Ahora utilice el lema de Sperner (+) para encontrar un simplex pancromático en la triangulación. Esto, esperamos (++), es el punto sensible que estábamos buscando.


Lagunas: (+) necesitamos $Col$ para satisfacer los requisitos de consistencia sobre las caras. (ver el enunciado del lema en la wiki).

(++) una arista del simplex pancromático encontrado será una arista sensible si

(i) va de color $Col = 0$ a un color $Col = i \neq 0$ ;

(ii) es una arista real de la red.

La brecha (+) puede ser imposible de rectificar como se indica: considere el caso en el que los únicos puntos coloreados en rojo en $C_0$ son los puntos hipotéticos $(0, ... k_i, ... 0)$ . Pero en este caso la sensibilidad en los puntos rojos es alta. Para llenar (+), tendríamos que dar un argumento diciendo que WLOG los puntos rojos tienen un alto grado de conectividad. También podríamos desechar algunos de los puntos rojos e introducir más vértices azules que adquieran colores distintos en $Col$ .

Para fil (++), una situación "ideal" sería aquella en la que todas las aristas simpliciales de nuestra triangulación son de hecho aristas de la red. Entonces (i), (ii) se cumplirían en todas las aristas que salen de la $Col = 0$ vértice en el simplex pancromático, y obtendríamos la sensibilidad $d$ .

Esto es imposible (y no podemos esperar sensibilidad $d$ ); sin embargo, tal vez existan triangulaciones del d-cubo en las que todos los símbolos tengan "suficientes" aristas de celosía en cada vértice. (Creo que esto también es falso, pero aún no tengo una idea mejor).

8voto

zkent Puntos 133

Recién visto en twitter : Hao Huang en la Universidad de Emory ha dado un argumento muy breve en este preimpreso demostrando lo siguiente

Teorema 1.1. Para todo número entero $n\geq 1$ , dejemos que $H$ sea una variable arbitraria $(2^{n-1}+1)$ -subgrafo inducido por vértices de $Q^n$ entonces

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

Además, esta desigualdad es estricta cuando $n$ es un cuadrado perfecto.

lo que implica la conjetura de sensibilidad. Esto pasa por el enfoque de Gotsman y Linial mencionado en La respuesta de Noam .

(Aquí, $Q^n$ es el $n$ -de hipercubos y $\Delta(H)$ denota el grado máximo de $H$ .)

El artículo es muy legible, y el "meollo" del argumento ocupa menos de 2 páginas y no utiliza mucho más que las propiedades básicas de entrelazamiento de los valores propios.

7voto

Ayman Puntos 101

Aquí hay otro problema que es equivalente a este (ver http://www.cs.huji.ac.il/~nati/PAPERS/gotsman_equivalence.pdf ):

Consideremos una coloración 2 de los vértices del hipercubo n-dimensional. Decimos que tiene una k-estrella monocromática si existe un vértice que está coloreado con el mismo color que al menos k de sus vecinos. Dado que el hipercubo es bipartito, podemos tener una coloración sin siquiera una estrella monocromática: esta coloración será exactamente equilibrada (es decir exactamente la mitad de los vértices reciben cada color). ¿Qué pasa con las coloraciones no equilibradas? Defina s(n) como el mayor número para que cada coloración no equilibrada del hipercubo de n dimensiones contiene una estrella monocromática s(n). Resulta que s(n) es igual a la mínima sensibilidad posible de una función booleana de grado exactamente n. [La idea básica es mirar el producto de la coloración (vista como {-1,1}) con la función de paridad sobre los n bits. La no paridad se traduce en el grado completo y la estrella k se traduce en la sensibilidad k].

Un problema relacionado define r(n) como el mayor número para que cada coloración no equilibrada del hipercubo n-dimensional contenga una estrella r(n) del color mayoritario . Esto fue estudiado por Chung, Furedi, Graham y Seymour en 1988 (véase http://www.math.ucsd.edu/~ronspubs/88_01_cubierta_fraccionada.pdf ) que dan esencialmente los mismos límites conocidos para s(n). Así, se sabe que log n <= r(n) <= s(n) <= sqrt(n), y la conjetura es que ambos son al menos n^a para algún a>0.

6voto

Pete Puntos 21

ACTUALIZACIÓN: La reducción inversa nos permite traducir el límite de Kenyon y Kutin para $k$ -en una cota inferior polinómica de la sensibilidad de la red en términos de $l$ , donde $l$ es el número mínimo tal que hay un punto azul dentro de $l$ unidades del origen en cada eje. El resultado de Kenyon y Kutin es que hay como mucho un grado $k$ la brecha entre $s(f)$ y $bs_k(f)$ ( $k$ -sensibilidad de bloque es la sensibilidad de bloque donde los bloques están restringidos a una longitud máxima $k$ ), por lo que $bs_k(f) \leq c_k s(f)^k$ , donde $c_k < \frac{e}{(k-1)!}$ . Tomemos un entramado cualquiera con $d$ dimensiones y sensibilidad $s$ . Consideremos el entramado finito formado por el corte de cada eje después del primer punto azul y apliquemos la reducción siguiente, de modo que la longitud máxima del eje sea $l$ . Entonces existe una función booleana $f$ con $bs_l(f) \geq d$ ya que todos los bloques tienen una longitud máxima de $l$ y $s(f) \leq ls$ . Entonces $d \leq bs_l(f) \leq c_l(ls)^l$ y $s \geq \frac{1}{l} (\frac{d}{c_l})^{\frac{1}{l}}$ .

Lo siguiente surgió del trabajo conjunto con Scott Aaronson, y proporciona una reducción del problema de la red de vuelta al problema original de las funciones booleanas, con la sensibilidad cambiada por un cierto factor.

Para una coloración de 2 colores $C$ de un $d$ -de tamaño $|S_1| \times |S_2| \ldots \times |S_d|$ tal que los únicos puntos azules axiales son $(0,\ldots,|S_i|,\ldots,0)$ , donde $|S_i|$ es el $i$ existe una función booleana con $bs(f) \geq d$ y $s(f) \leq \max_i{|S_i|} \cdot s(C)$ .

Prueba: Definimos una función $f$ en $n=|S_1|+|S_2|+\ldots+|S_d|$ bits de la siguiente manera. Dividir los bits en bloques $b_1, b_2, \ldots, b_n$ , donde $|b_i|=|S_i|$ . Para una entrada $y=(y_1,y_2,\ldots,y_n)$ y que el número de 1's en el conjunto $b_i$ sea $z_i$ . Sea $y$ corresponden al punto $(z_1,z_2,\ldots,z_d)$ Así que $f(y)=0$ si $(z_1,z_2,\ldots,z_d)$ es rojo y $f(y)=1$ si es azul. Cada uno de los bloques $b_i$ , $1 \leq i \leq d$ , es sensible en el $n$ -bit de entrada $(0,0,\ldots,0)$ . Esto se debe a que al voltear los bits del bloque $b_i$ corresponde al punto $(0,\ldots,|S_i|,\ldots,0)$ donde $|S_i|$ es el $i$ coordenada, que es azul, y así $f(y^{b_i})=1$ ( $y$ con bits $b_i$ volteado). Así, $bs(f) \geq d$ . Además, el desplazamiento de una coordenada a lo largo del $i$ eje en el entramado corresponde a cambiar uno de los bits en $b_i$ de la entrada correspondiente. Por lo tanto, para cualquier punto $x=(x_1,x_2,\ldots,x_n)$ donde el conjunto de coordenadas $X \subseteq \{1,\ldots,d\}$ son sensibles, $|X| \leq s(C)$ por lo que la sensibilidad de $f$ en la entrada correspondiente es como máximo $\sum_{i \in X} b_i \leq s(C) \cdot \max_i b_i$ . Esto demuestra que $s(f) \leq s(C) \cdot \max_i b_i$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X