Suponemos que . Entonces el siguiente hecho es bien conocido:
Quiero saber los resultados sobre el número de ciclos hamiltonianos en gráficos aleatorios.
Q1. ¿Cuántos es el número esperado de ciclos hamiltonianos en ?
Q2 Cuál es la probabilidad para la probabilidad borde p en G ( n , p ) ?
Respuestas:
Como dijo Yuval, Q1 es fácil de responder utilizando la linealidad de la expectativa (spoiler: ). No sé la respuesta exacta a Q2, pero podría ser lo suficientemente bueno si sabes que es muy bajo: para el rango de p donde hay al menos un ciclo, sostiene que P [ hay más de un ciclo | existe al menos un ciclo de ] > 1 - 1 / n log n o así. En otras palabras, una vez que hay un ciclo, hay muchos. La razón es que una vez que hay un ciclo, hay alrededor de n 2( n - 1 ) ! pagnorte pag PAG[ hay más de un ciclo | hay al menos un ciclo ] > 1 - 1 / nIniciar sesiónnorte norte2 formas de crear otro ciclo a partir de él mediante el intercambio de dos bordes del ciclo por los dos bordes "cruzados" (esto se llama "2 vueltas" o algo en la literatura relevante). Para cualquier par de aristas, la posibilidad de que pueda hacerlo es . Entonces, para que todo esto falle, la probabilidad es ( 1 - p 2 ) n 2, que es aproximadamente e - ( p n ) 2 , que es bastante pequeña.pag2 ( 1 - p2)norte2 mi- ( p n )2
fuente