Transiciones de fase en problemas computacionales aleatorios

Presentado por Ricardo Restrepo López
Instituto de Matemáticas, Universidad de Antioquia

2-coloramiento de hipergrafos

Un hipergrafo es una generalización del concepto de grafo, en el que una arista puede conectar cualquier número de vértices:

Aparecen en geometría computacional, teoría de preferencias sociales, topología (complejos simpliciales abstractos).

Un hipergrafo es $k$ uniforme si cada arista es una $k$ -tupla de vértices (no necesariamente diferentes).

Un

$\lambda$ -coloramiento de un hipergrafo es una asignación de colores del conjunto

$\{1,\ldots, \lambda\}$ a los vértices del hipergrafo del tal manera que no hayan aristas monocromáticas.

Un hipergrafo aleatorio

$H_k(n,m)$ es un hipergrafo

$k$ -uniforme con

$n$ vértices y

$m(n)$ aristas aleatorias escogidas de manera independente e uniforme entre todas las posibles

$k$ -tuplas de vértices.

La propiedad B no puede ser aproximada por la propiedad de tener un grafo pequeño adecuado
(Entonces tiene un umbral fino!).

Localizar tal umbral. (Esto haría el problema de decisión, 'trivial')
Estudiar umbral para propiedades del tipo: "El algoritmo $\mathbf{A}$ halla un 2-coloramiento del grafo en tiempo $O(n^d)$ ".

Lovasz, Erdos (1973, 1975, 1977):

Sean $A_1, \ldots, A_t$ eventos con probabilidad acotada por $p$ .
Cada uno de ellos es independiente del álgebra de eventos generada por todos los demás excepto a lo más $d$ de ellos.
Entonces, si $ep(d + 1) < 1$ , con probabilidad positiva, ninguno de los eventos ocurre.

Desigualdad de Markov: Si $X\geq 0$ entonces $P(X\geq 1) \leq \mathbf{E}[X]$
Alon y Spencer: Si $m(n) = rn$ con $r> 2^{k-1} \ln{2} - \ln{2}/2$ , entonces $H_k(n,m)$ no es $2$ -coloreable.

Desigualdad de Paley-Zygmund: Si $X\geq 0$ entonces $P(X > 0) \geq (\mathbf{E}[X])^2 / \mathbf{E}[X^2].$
Achlioptas, Moore (2002): Si $m(n) = rn$ con $r < 2^{k-1} \log{2} - \log{2}/2 - (1 + o_k(1)) / 2$ , entonces $H_k(n,m)$ es $2$ -coloreable.

Algoritmo CR. (Chvátal, Reed):

1. Si hay aristas monocromáticas coloreadas parcialmente con $k-1$ o $k-2$ vértices:
2. Si no hay tales aristas:

Versión algorítmica del lema Local de Lovasz: Beck (91), Alon (91), Molloy, Reed (98), Czumaj, Scheideler (00), Srinivasan (08), Moser, Tardos (08, 09).
Existe $c_k$ tal que si $m(n) = c 2^k n /k^2$ con $c < c_k$ entonces $H_k(n,m)$ es $2$ -coloreable en tiempo lineal.

Eliminación (Peeling, core): Pittel, Spencer, Wormald (96). Janson (2011).
Para problemas de satisfacción: Montanari, Restrepo, Tetali (2011), Molloy, Restrepo (2012).
Si $m(n) \geq \Omega(\alpha_k 2^k / k)$ entonces el core es vacío y el proceso de eliminación siempre halla un coloramiento.

<section data-background="image.png">

<section data-background="image.png" data-background-repeat="repeat" data-background-size="100px">