Количество гамильтоновых циклов на случайных графах

Предположим, что . Тогда хорошо известен следующий факт:$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}$$

Я хочу узнать результаты о количестве гамильтоновых циклов на случайных графах.

Q1. Сколько ожидаемого числа гамильтоновых циклов на ?$G(n,p)$

Q2. Какова вероятность для вероятности ребра p на G ( n , p ) ?$Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$$p$$G(n,p)$

Как сказал Ювал, Q1 легко ответить, используя линейность ожидания (спойлер: ). Я не знаю точного ответа на вопрос Q2, но он может быть достаточно хорошим, если вы знаете, что он очень низкий: для диапазона p, где есть хотя бы один цикл, он считает, что P [ существует более одного цикла | существует хотя бы один цикл ] > 1 - 1 / n log 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$способы создания другого цикла из него путем замены двух ребер цикла двумя «пересекающимися» ребрами (это называется «2-переворачиванием» или что-то в некоторой соответствующей литературе). Для любой пары ребер вероятность того, что вы можете это сделать, равна . Таким образом, для того, чтобы все это потерпело неудачу, шанс равен ( 1 - p 2 ) n 2, что примерно равно e - ( p n ) 2 , что довольно мало.$p^2$$(1-p^2)^{n^2}$$e^{-(pn)^2}$