Gráficos aleatorios con un camino hamiltoniano

Question

Supongamos que elegimos aleatoriamente un grafo con $n$ vértices de la siguiente manera: cada borde se incluye con probabilidad $\frac12$. Por lo tanto, cada grafo tiene la misma probabilidad de ser elegido, y hay $2^{\frac{n(n-1)}{2}}$ grafos posibles. Denotemos $H_n$ al evento de que dicho grafo contiene un camino hamiltoniano. Demuestra que $$\lim_{n \to \infty} P(H_n) = 1,$$ es decir, a medida que consideramos grafos más grandes, la proporción de grafos que contienen un camino hamiltoniano se aproxima a $1$.

Como bonificación, encuentra un algoritmo eficiente para encontrar un camino hamiltoniano en un grafo. El algoritmo también debe ser preciso, es decir, debe encontrar un camino hamiltoniano la mayor parte del tiempo. Más concretamente, estamos buscando un algoritmo con las siguientes dos propiedades:

• Su complejidad media de tiempo es polinómica con respecto al número de vértices. (Pero debes apuntar lo mejor posible.)
• Denotemos $S_n$ al evento de que el algoritmo tiene éxito si su entrada es un grafo aleatorio con $n$ vértices. Entonces, $$\lim_{n \to \infty} P(S_n) = 1.$$

Entonces, ¿qué he intentado hasta ahora? Hay una manera relativamente fácil de obtener el límite inferior de $0.25$ que se mantiene para todos los $n$. Denotemos $X_n[a]$ al evento de que existe un camino hamiltoniano que comienza en $a$, en un grafo aleatorio con $n$ vértices. Claramente, la probabilidad de que ocurra tal evento es la misma para todos los vértices, y denotaremos esta probabilidad como $x$. Podemos acotar $x = P(X_n[a])$ por debajo de la siguiente manera:

• Si hay al menos un borde hacia algún vértice $b$, podemos considerar caminos hamiltonianos que comienzan con los vértices $a, b$. La probabilidad de que exista un camino hamiltoniano es $P(X_{n-1}[b]) = x_{n-1}$.
• Si no hay borde desde $a$, no hay camino hamiltoniano que comience en $a$. La probabilidad de que esto ocurra es $\frac{1}{2^{n-1}}$.

Así obtenemos la siguiente desigualdad: $$x_n \geq (1 - \frac {1}{2^{n-1}}) \cdot x_{n-1}$$.

A partir de esto, es fácil probar que $x_n \geq \frac14$ para todos $n$. Para obtener un límite inferior mejor, podemos considerar casos adicionales basados en cuántos bordes hay desde $a$:

• Si hay $0$ vértices adyacentes, no hay esperanza.
• Si hay un vértice adyacente, podemos reducir a $x_{n-1}$.
• Si hay al menos $2$ vértices adyacentes, denótenlos como $b$ y $c$. El camino puede pasar por $b$ o por $c$. Así, por el principio de inclusión-exclusión, la probabilidad de que al menos uno de los caminos exista es $$P(X_{n-1}[b]) + P(X_{n-1}[c]) - P(X_{n-1}[b] \land X_{n-1}[c]).$$

Por lo tanto, si pudiéramos encontrar un límite superior lo suficientemente bueno para $P(X_{n-1}[b] \land X_{n-1}[c])$, el problema estaría resuelto. Sin embargo, dicho límite superior se me escapa, todo lo que puedo encontrar son límites inferiores (que no son útiles).

Formas alternativas de la expresión anterior que pueden ayudar: $$P(X_{n-1}[b])\ +\ P(X_{n-1}[c] \mid \neg X_{n-1}[b])$$

En esta forma, estamos tratando de encontrar un límite inferior para el segundo término, que corresponde a la probabilidad de que exista un camino hamiltoniano que comienza en $c$, dado que sabemos que no hay un camino hamiltoniano desde $b$.

También, puede ser mejor considerar el caso con más vértices adyacentes a $a$, como tres. Aunque con más vértices viene un problema más grande al aplicar el principio de inclusión-exclusión.

Answer 1

En contexto: un resultado de Pósa dice que un grafo aleatorio con $C n \log n$ aristas ya contiene un camino hamiltoniano con una probabilidad que tiende a $1$, y aquí tenemos un grafo aleatorio uniforme (con un promedio de $\frac{n^2}{4}$ aristas). Así que podemos ser bastante derrochadores.

En cuanto a un algoritmo, podemos tomar el algoritmo usado para probar el teorema de Dirac. Las hipótesis de ese teorema no se aplican aquí, pero el algoritmo seguirá funcionando con alta probabilidad. La estrategia es la siguiente:

1. Elegir un camino ávidamente: empezar en un vértice $v_1$, elegir un vértice $v_2$ adyacente a éste, luego elegir un vértice $v_3$ adyacente a $v_2$, y así sucesivamente. Repetir hasta que te atores.
2. Convertir el camino en un ciclo: si tiene extremos $v_1$ y $v_\ell$, encontrar vértices adyacentes $v_i$ y $v_{i+1}$ en el camino tal que $v_{i+1}$ sea adyacente a $v_1$ y $v_i$ sea adyacente a $v_\ell$. Entonces el ciclo es $v_1, \dots, v_i, v_\ell, \dots, v_{i+1}, v_1$.
3. Convertir el ciclo en un camino más largo: si $v_{\ell+1}$ es un vértice que no está en el ciclo, encontrar un vértice $v$ en el ciclo adyacente a $v_{\ell+1}$, y tomar el camino que comienza junto a $v$, va alrededor del ciclo, y luego va a $v_{\ell+1}$.
4. Repetir los pasos 2 y 3 hasta que el camino contenga todos los vértices.

Todos estos pasos son bastante propensos a funcionar individualmente. El problema es que para analizar cuán probable es que funcionen en conjunto, tendríamos que revisar las aristas del grafo varias veces, lo cual no preserva la independencia.

Entonces, en su lugar, escribiremos nuestro grafo aleatorio uniforme $G$ como la unión de grafos $G_0, G_1, \dots, G_{10 \log n}$, donde $G_0$ contiene cada arista de manera independiente con una probabilidad de $\frac14$, y $G_1, \dots, G_{10 \log n}$ contienen cada arista de manera independiente con una probabilidad $p$, elegida de manera que $\frac34(1-p)^{10 \log n} = \frac12$. Entonces, la unión contendrá cada arista con una probabilidad de $\frac12$, por lo que será el grafo aleatorio uniforme. Si resolvemos para $p$, obtenemos $p = O(\frac{1}{\log n})$, pero lo que realmente necesitaremos es que $p$ sea asintóticamente mayor que $\frac{1}{\sqrt n}$.

Luego afirmo que:

1. Un camino ávido elegido en $G_0$ alcanzará una longitud de $n - 5\log n$ con una probabilidad muy alta.
2. Hacer el paso 2 del algoritmo en cualquiera de los $G_1, \dots, G_{10 \log n}$ funcionará con una probabilidad muy alta.
3. Hacer el paso 3 del algoritmo en cualquiera de los $G_1, \dots, G_{10 \log n}$ funcionará con una probabilidad muy alta.

Luego simplemente podemos mirar los grafos $G_0, G_1, \dots$ secuencialmente mientras avanzamos en el algoritmo. Esto preserva la independencia, y si las aristas que necesitamos estarán en el grafo $G_i$ que estamos revisando, estarán en la unión $G$.

Para la primera afirmación: la probabilidad de que un camino ávido se atasque mientras todavía haya $5 \log n$ vértices para elegir es $(\frac34)^{5\log n} = n^{-5\log \frac43}$, por lo que la probabilidad es a lo sumo $n^{1 - 5\log \frac43} \approx n^{-0.43}$ de que alguna vez se atasque.

Para la segunda afirmación: tenemos al menos $\frac n2$ opciones para los vértices $v_i$ y $v_{i+1}$, y cada uno funciona con probabilidad $p^2$. La probabilidad de que ninguno funcione es $(1-p^2)^{n/2} \le e^{-p^2n/2}$, que se aproxima a $0$ a medida que $n\to \infty. (Aquí es donde queremos que $p \gg \frac{1}{\sqrt n}$, para que el exponente vaya a $-\infty$ a medida que $n\to\infty. A la verdad queremos un poco más que eso, porque queremos que los $O(\log n)$ de estos pasos funcionen, por lo que la probabilidad debería disminuir más rápido que $\frac{1}{\log n}$. Pero nuestro $p$ es en realidad bastante mayor que $\frac{1}{\sqrt n}$, así que tenemos margen de maniobra).

Para la tercera afirmación: tenemos al menos $\frac n2$ opciones para el vértice $v$, y cada uno funciona con probabilidad $p$. La probabilidad de que ninguno funcione es $(1-p)^{n/2} \le e^{-pn/2}$, que se aproxima a $0$ a medida que $n\to \infty$.

Answer 2

Estos son bastante conocidos.

De hecho, el umbral para que un gráfico sea hamiltoniano es $p=\frac{\log n + \log \log n}{n} \ll \frac 12$. De hecho, con alta probabilidad, un gráfico aleatorio se vuelve hamiltoniano tan pronto como su grado mínimo alcanza $2$. Puedes encontrar la prueba en cualquier libro clásico sobre gráficos aleatorios, por ejemplo aquí.

El algoritmo también es bien conocido. Puedes encontrar unas excelentes notas de conferencia sobre ello en el curso de Alistair Sinclair. Te propongo que lo descargues porque eliminará las notas de la conferencia después del semestre. Descarga la Conferencia 15. Te sugiero que también sigas todas las notas de la conferencia.