Número de ciclos hamiltonianos em gráficos aleatórios

16

Assumimos que . Então, o seguinte fato é bem conhecido: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)

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)

Elely
fonte
8
Você provavelmente pode responder a Q1 você mesmo. Dica: Linearidade da expectativa.
Yuval Filmus

Respostas:

7

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 1)!pnpP[existe mais de um ciclo|existe pelo menos um ciclo]>1 1-1 1/nregistronn2maneiras 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 1-p2)n2e-(pn)2

alce anônimo
fonte