Diámetro de un gráfico formado por ciclos de Hamilton

Question

Imagina un grafo no dirigido $G = (V,E)$ con $|V| = n$ nodos. Sus aristas no ponderadas $E$ son la unión de $h$ ciclos hamiltonianos aleatorios a través de todos los nodos, cada uno generado iid uniformemente al azar del conjunto de todos los ciclos hamiltonianos.

Cuál es el diámetro esperado $D$ de $G$ ?

El caso $h=1$ es trivial y no es interesante.

Claramente, $D$ crece de forma estrictamente monótona con $n$ así como con $h^{-1}$ . Sin embargo, no estoy seguro de la relación exacta de estas variables. Sospecho que hay una relación del tipo $D = O(\log(n)/h)$ .

Answer 1

Al menos para $h$ constante, tomando la unión de $h$ ciclos hamiltonianos uniformemente aleatorios es tal vez equivalente a tomar un $2h$ -regular, cuyas propiedades como $n \to\infty$ lo sabemos muy bien.

Un resultado en esta dirección es el siguiente. Sea $\mathcal G_{n,d}$ denotan el espacio de probabilidad uniforme sobre el azar $d$ -grafo regular en $n$ vértices. En resultado de Kim y Wormald tenemos:

Si $d\ge4$ es par, entonces $G \in \mathcal G_{n,d}$ a.a.s. (asintóticamente casi seguro) tiene una descomposición hamiltoniana completa.

En otras palabras, con una probabilidad que tiende a $1$ como $n \to\infty$ , una aleatoriedad uniforme $2h$ -El gráfico regular es la unión de $h$ ciclos hamiltonianos de bordes disjuntos.

Por supuesto, si sólo tomamos $h$ ciclos hamiltonianos uniformemente aleatorios, probablemente no serán disjuntos. Pero tampoco están demasiado lejos. Si $X_{ij}$ es el número de ciclos compartidos entre el $i$ -a y $j$ -ciclo hamiltoniano, entonces $X_{ij} \sim \operatorname{Poisson}(2)$ . Así que mientras $h$ es constante, el número de aristas superpuestas es $O(1)$ a.a.s., y con probabilidad constante no hay ninguno.

Otra razón para no preocuparse por los solapamientos es que estoy bastante seguro de que también es cierto un resultado diferente: si $\mathcal G_{n,d}'$ es el espacio de probabilidad correspondiente a $\mathcal G_{n,d}$ de $d$ -regular (permitiendo aristas paralelas), entonces para los $d$ , $G \in \mathcal G_{n,d}'$ a.a.s. tiene una descomposición en ciclos hamiltonianos que ya no son disjuntos. (El documento anterior menciona esto para $d=4$ pero no dice nada en un sentido o en otro acerca de la mayor $d$ Creo que los mismos métodos resolverían ese problema).

Dado que todas las uniones de $h$ Los ciclos hamiltonianos son resultados igualmente probables del muestreo de $\mathcal G_{n,2h}'$ esto nos diría a resultados verdaderos a.a.s. de $\mathcal G_{n,2h}'$ también son verdaderos a.a.s. de este modelo de grafo aleatorio. Esto es bueno, porque muchas pruebas sobre $\mathcal G_{n,d}$ de todos modos, primero revisa los multigrafos y luego tiene en cuenta la probabilidad de que el gráfico sea simple. En particular, esto es cierto para el resultado siguiente.

Un resultado de Bollobás y de la Vega obtiene los siguientes límites en el diámetro de $\mathcal G_{n,r}$ (cambiando la notación, utilizan $r$ para el grado):

Teorema 1. Dejemos que $r \ge 3$ y $\epsilon>0$ ser fijo y definir $d=d(n)$ como el menor número entero que satisface $$(r-1)^{d-1} \ge (2+\epsilon) rn \log n.$$ Entonces a.e. $r$ -El gráfico regular tiene un diámetro máximo de $d$ .

Teorema 3. El diámetro de a.e. $r$ -gráfico regular de orden $n$ es al menos $$\lfloor \log_{r-1} n\rfloor + \left\lfloor\log_{r-1} \log n - \log_{r-1}\frac{6r}{r-2} \right\rfloor + 1.$$

Establecer $r = 2h$ y eso es todo.

Answer 2

Puro heurísticamente Espero que la respuesta sea $O(\log(n)/\log(h))$ .

¿Por qué? Podemos imaginar que cada vértice tiene una arista a $2h$ otros vértices elegidos al azar. Entonces, heurísticamente, podemos imaginar que hay unos $(2h)^d$ vértices a distancia $\le d$ desde un vértice fijo $v$ (siempre y cuando $(2h)^d$ es pequeño en comparación con $n$ ). Por lo tanto, si $(2h)^d \approx n$ podemos esperar que cualquier par fijo de vértices $v,w$ están probablemente conectadas por algún camino de longitud $\le d$ . Esta ecuación se satisface cuando $d \approx \log_{2h}(n) \sim \log(n)/\log(h)$ . Cuando $d$ es un pequeño factor constante mayor que eso, podemos esperar heurísticamente que haya una probabilidad abrumadora de que cualquier par fijo de vértices $v,w$ están conectadas por un camino de longitud $\le d$ . Tomando un límite de unión sobre todos los pares de vértices, podemos esperar que haya $d=O(\log(n)/\log(h))$ tal que con una probabilidad abrumadora el diámetro será $\le d$ .

Esto no es una prueba, es sólo una estimación heurística a mano.