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

16

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

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

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

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

Elely
источник
8
Вы, вероятно, можете ответить на вопрос 1 самостоятельно. Подсказка: линейность ожидания.
Юваль Фильмус

Ответы:

7

Как сказал Ювал, Q1 легко ответить, используя линейность ожидания (спойлер: ). Я не знаю точного ответа на вопрос Q2, но он может быть достаточно хорошим, если вы знаете, что он очень низкий: для диапазона p, где есть хотя бы один цикл, он считает, что P [ существует более одного цикла | существует хотя бы один цикл ] > 1 - 1 / n log n или около того. Другими словами, если есть один цикл, их много. Причина заключается в том, что раз есть один цикл, существует около п 2(n1)!pnpP[there is more than one cycle|there is at least one cycle]>11/nlognn2способы создания другого цикла из него путем замены двух ребер цикла двумя «пересекающимися» ребрами (это называется «2-переворачиванием» или что-то в некоторой соответствующей литературе). Для любой пары ребер вероятность того, что вы можете это сделать, равна . Таким образом, для того, чтобы все это потерпело неудачу, шанс равен ( 1 - p 2 ) n 2, что примерно равно e - ( p n ) 2 , что довольно мало.p2(1p2)n2e(pn)2

анонимный лось
источник