Probabilidad de que una secuencia corresponda a un ciclo en un grafo

Question

Supongamos que el grafo aleatorio no dirigido $G$ se construye del siguiente modo. $G$ comienza como $n$ vértices distintos, donde $n$ es par. Independientemente para cada uno de los posibles pares de vértices, añadimos una arista no dirigida entre ellos con probabilidad $p$ .

Sea $v_1,v_2,...,v_n$ sean los vértices de $G$ .

La probabilidad de que la secuencia $[v_1,v_2,v_3,...,v_n,v_1]$ corresponde a un ciclo en el gráfico debe ser $p^n$ Corrígeme si me equivoco.

Utilizando el límite de la unión, ¿cuál es el límite superior de la probabilidad de que $G$ tiene un ciclo hamiltoniano.

Answer 1

Si quieres utilizar el límite de unión tienes que calcular el número de ciclos. Si suponemos que empezamos con $v_1$ entonces tenemos $(n-1)!$ y si tenemos en cuenta la simetría de reflexión (como sugirió @Especialmente Cal), obtenemos $$P\leq {1\over 2}\cdot p^n\cdot (n-1)!$$