La aplicación de la asimétrica Lovasz Local Lema requiere encontrar una función peso $x$ sobre los acontecimientos negativos que satisface la propiedad en el enlace. A menudo, se utiliza una constante de peso de la función, dando lugar a simétrica LLL. Supongamos que esta falla. Es allí una manera sistemática para la búsqueda de una mejor selección de $x$?
Respuesta
¿Demasiados anuncios?
En la práctica, no es realmente a cabo de manera sistemática. Usted acaba de reconocer un patrón que hemos visto en las anteriores aplicaciones de los locales lexema, o de lo contrario ser muy inteligente. Dos patrones que sé:
- Si sólo dispone de dos tipos de eventos, tiene dos valores de $x_1$$x_2$, y que acaba de resolver un problema de optimización para averiguar los valores de darle el mejor de los límites. Ejemplo: números de Ramsey $R(3,k)$ o $R(4,k)$.
- Si tu mal eventos corresponden a algo que pasa en grupos de tamaño variable, vamos a $x(A)$ ser exponencialmente en descomposición en el tamaño del conjunto que determina el $A$. De nuevo, resolver un problema de optimización para determinar la constante de la exponencial. Ejemplo: acíclicos borde de colorear, no repetitivas para colorear.
Además, también hay un "compromiso local lema" que la asimétricas, pero no requiere que usted elija pesos. Se dice que podemos evitar malos eventos con probabilidad positiva si, para cada evento $A$, $$\sum_{B \in \Gamma(A)} \Pr[B] \le \frac14.$$ We get this by choosing $x(A) = 2 \Pr[A]$ en la habitual versión de la liga de la leche. La versión simétrica es bastante claramente un caso especial.
La entropía de compresión de enfoque para el local lexema pueden dar un poco de intuición de lo que está pasando con los pesos. Permítanme resumir la idea (puedes leer más sobre él aquí); pido disculpas por la longitud de la digresión antes de que podamos volver a responder a tu pregunta.
Decir que estamos tratando de encontrar una función de $f : X \to Y$ que cumpla con las condiciones de la forma "en un subconjunto $S \subseteq X$, $f$ no hacer esto muy específica de la cosa". Es tradicional que pensar en esto como un $Y$-para colorear de la serie $X$.
Nuestro algoritmo de la siguiente manera. Empezar con $X$ completamente incoloro. Repita el mismo paso una y otra vez:
- Selecciona el primer elemento de $X$ que no tiene un color, y el color uniformemente al azar.
- Si una restricción en algunos de $S$ es violado, uncolor todos los de $S$. (En algunos casos, se puede optimizar por sólo uncoloring la mayoría de $S$; por ejemplo, si la condición en $S$ es "no puede ser monocromática", uncolor todos, pero un vértice.)
- Escriba lo que pasó en este paso, dando suficiente detalle como para que el paso puede ser a la inversa (y el color elegido al azar en este paso reconstruido).
Después de$t$, $X$ ha sido de color, o hemos llegado a una secuencia de colores de $Y^t$ a un parcial de colorear de $X$, además de un registro de lo que sucedió en cada paso. Reversibilidad garantiza que dos diferentes insumos (elementos de $Y^t$) resultado en dos salidas diferentes.
Si el registro se puede lacónico suficiente para que su longitud crece como $C^t$$C < |Y|$, entonces no es un $t$ de manera tal que, por el principio del palomar, hay menos de $|Y|^t$ parcial posible que los colorantes más registros; en ese caso, debe ser posible para el algoritmo para terminar - por $X$ a final totalmente de color.
La entropía método de compresión es más o menos equivalente a la local lema. En lugar de elegir los valores de $x(A)$, somos la elección de los medios para codificar la descripción "nos incoloro el conjunto $S$ determinar el $A$; he aquí cómo deshacer eso". Estos corresponden a cada uno de los otros en el sentido de que si tomamos $b(A)$ bits para codificar esta descripción, entonces probablemente algo parecido a $x(A) = 2^{-b(A)}$ funcionará como un peso en el local lema.
(Intuitivamente, esto es debido a que $x(A)$ es una cota superior para la probabilidad condicional de a $A$ pasando de que ningún otro mal hechos ocurrieron; $\log_2 \frac{1}{x(A)}$ mide el contenido de la información de un evento con una probabilidad de $x(A)$, por lo que no debería ser una codificación de coincidencia.)
La codificación de la descripción de la entropía algoritmo de compresión todavía no es algo que realmente podemos encontrar de forma sistemática: es tan difícil como encontrar cualquier otra buena compresión de datos sin pérdidas esquema. Pero tienes alguna idea de cuánto puede permitirse el lujo de pasar sobre la codificación de un evento en función de lo complicado que es, por lo tanto estamos menos tropezando en la oscuridad aquí.
