Assumimos que . Então, o seguinte fato é bem conhecido:G∈G(n,p),p=lnn+lnlnn+c(n)n
Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)
Quero saber os resultados sobre o número de ciclos hamiltonianos em gráficos aleatórios.
Q1 Quanto é o número esperado de ciclos hamiltonianos em ?G(n,p)
Q2 Qual é a probabilidade para a probabilidade de borda em ?Pr[G has a *unique* Hamiltonian cycle]pG(n,p)
Respostas:
Como Yuval disse, Q1 é fácil de responder usando linearidade de expectativa (spoiler: ). Não sei a resposta exata para o Q2, mas pode ser boa o suficiente se você souber que é muito baixo: para o intervalo de p em que há pelo menos um ciclo, é válido que P [ exista mais de um ciclo | existe pelo menos um ciclo ] > 1 - 1 / n log n ou mais. Em outras palavras, uma vez que existe um ciclo, há muitos. O motivo é que, uma vez que existe um ciclo, existem cerca de n 2( n - 1 ) ! pn p P[ existe mais de um ciclo | existe pelo menos um ciclo ] > 1 - 1 / nregistron n2 maneiras de criar outro ciclo a partir dele trocando duas arestas do ciclo pelas duas arestas "cruzadas" (isso é chamado de "2 flip" ou algo em alguma literatura relevante). Para qualquer par de arestas, a chance de fazer isso é . Portanto, para que tudo isso falhe, a chance é ( 1 - p 2 ) n 2, que é aproximadamente e - ( p n ) 2 , que é bem pequena.p2 ( 1 - p2)n2 e- ( p n )2
fonte