Anzahl der Hamilton-Zyklen in Zufallsgraphen

Wir nehmen an, dass . Dann ist folgende Tatsache bekannt: $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$

\begin{array}{rcl} P r [G has a Hamiltonian cycle] = {\begin{cases} 1 & (c (n) \to \infty) \\ 0 & (c (n) \to - \infty) \\ e^{- e^{- c}} & (c (n) \to c) \end{cases} \end{array}

$\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}$

Ich möchte Ergebnisse über die Anzahl der Hamilton-Zyklen in Zufallsgraphen wissen.

Q1. Wie viele Hamilton-Zyklen sind auf erwarten ? $G(n,p)$

Q2. Was ist die Wahrscheinlichkeit für die auf ? $Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$ $p$ $G(n,p)$

graph-theory co.combinatorics randomness Elely
quelle

Sie können Q1 wahrscheinlich selbst beantworten. Hinweis: Linearität der Erwartung.

Yuval Filmus

Antworten:

Wie Yuval sagte, ist Q1 einfach zu beantworten, wenn man die Linearität der Erwartung verwendet (Spoiler: ). Ich kenne die genaue Antwort auf Q2 nicht, aber es könnte gut genug sein, wenn Sie wissen, dass sie sehr niedrig ist: Für den Bereich von in dem es mindestens einen Zyklus gibt, gilt, dass oder so. Mit anderen Worten, sobald es einen Zyklus gibt, gibt es viele. Der Grund ist, dass es, sobald es einen Zyklus gibt, ungefähr Möglichkeiten gibt, einen weiteren Zyklus daraus zu erstellen, indem zwei Flanken des Zyklus durch die beiden "sich kreuzenden" Flanken ausgetauscht werden (dies wird als "2-Flip" oder so etwas bezeichnet) einschlägige Literatur). Für jedes Kantenpaar ist die Wahrscheinlichkeit, dass Sie dies tun können, $(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$ $p^2$ . Wenn all dies fehlschlägt, ist die Chance was ungefähr , was ziemlich klein ist. $(1-p^2)^{n^2}$ $e^{-(pn)^2}$

anonymer Elch
quelle