Liczba cykli hamiltonowskich na losowych wykresach

Zakładamy, że . Zatem dobrze znany jest następujący fakt:$G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$

$$\begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\rightarrow \infty) \\ 0 & (c(n)\rightarrow - \infty) \\ e^{-e^{-c}} & (c(n)\rightarrow c) \end{cases} \end{eqnarray}$$

Chcę poznać wyniki dotyczące liczby cykli hamiltonowskich na losowych wykresach.

Pytanie 1 Ile jest oczekiwana liczba cykli hamiltonowskich na ?$G(n,p)$

Q2 Jakie jest prawdopodobieństwo dla prawdopodobieństwa krawędzi p na G ( n , p ) ?$Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$$p$$G(n,p)$

$(n-1)!p^n$$p$$P[\text{there is more than one cycle} | \text{there is at least one cycle}]>1-1/n^{\log n}$$n^2$ ways to create another cycle from it by exchanging two edges of the cycle by the two "crossing" edges (this is called a "2-flip" or something in some of the relevant literature). For any pair of edges, the chance you can do that is $p^2$. So for all of these to fail, the chance is $(1-p^2)^{n^2}$ which is roughly $e^{-(pn)^2}$, co jest dość małe.