Número de ciclos hamiltonianos en gráficos aleatorios

16

Suponemos que . Entonces el siguiente hecho es bien conocido:GG(n,p),p=lnn+lnlnn+c(n)n

Pr[G has a Hamiltonian cycle]={1(c(n))0(c(n))eec(c(n)c)

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 ?G(n,p)

Q2 Cuál es la probabilidad para la probabilidad borde p en G ( n , p ) ?Pr[G has a *unique* Hamiltonian cycle]pG(n,p)

Elely
fuente
8
Probablemente puedas responder la Q1 tú mismo. Sugerencia: linealidad de la expectativa.
Yuval Filmus

Respuestas:

7

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(norte-1)!pagnortepagPAG[hay más de un cicloEl |hay al menos un ciclo]>1-1/ /norteIniciar sesiónnortenorte2formas 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-pag2)norte2mi-(pagnorte)2

alce anónimo
fuente