Jumlah siklus Hamiltonian pada grafik acak

Kami berasumsi bahwa . Maka fakta berikut diketahui:$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}$$

Saya ingin tahu hasil tentang jumlah siklus Hamiltonian pada grafik acak.

Q1. Berapa jumlah siklus Hamilton yang diharapkan pada ?$G(n,p)$

Q2. Berapa probabilitas untuk probabilitas tepi p pada G ( n , p ) ?$Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$$p$$G(n,p)$

Seperti yang Yuval katakan, Q1 mudah dijawab dengan menggunakan linearitas harapan (spoiler: ). Saya tidak tahu jawaban pasti untuk Q2, tetapi mungkin cukup baik jika Anda tahu itu sangat rendah: untuk rentang p di mana setidaknya ada satu siklus, ia berpendapat bahwa P [ ada lebih dari satu siklus | setidaknya ada satu siklus ] > 1 - 1 / n log n atau lebih. Dengan kata lain, sekali ada satu siklus, ada banyak. Alasannya adalah bahwa sekali ada satu siklus, ada sekitar n $(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$cara untuk membuat siklus lain darinya dengan menukar dua sisi siklus dengan dua sisi "menyilang" (ini disebut "2-flip" atau sesuatu dalam beberapa literatur yang relevan). Untuk setiap pasangan ujung, kesempatan yang dapat Anda lakukan adalah . Jadi untuk semua ini gagal, kesempatannya adalah ( 1 - p 2 ) n 2 yang kira - kira e - ( p n ) 2 , yang cukup kecil.$p^2$$(1-p^2)^{n^2}$$e^{-(pn)^2}$