ランダムグラフにおける$ k $ -pathの確率

G(n、p)$の$ G とする。 $ p = frac { ln n + ln ln n + c(n)} {n}
$ならば、 次の事実はよく知られています:

begin{eqnarray} Pr [Gmbox{ 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}

すなわち、ハミルトニアンサイクルを得るには確率$ p = ln n(1 + o(1))/ n $で十分です。

{1、 ldots、n } $内の与えられたパラメータ$ k に対して、グラフが$ k $
-pathを持つ可能性のあるクリティカル確率$ p $が何であるか疑問に思っています。

$ n $ノードのグラフに長さ$ k $の単純な経路が1つだけ必要なので、$ p = ln k(1 + o(1))/ k
$は高すぎるようです。

ベストアンサー

$ k $が定数である場合、長さ$ k $の経路の閾値確率は$ p sim dfrac {1} {n ^ {1 +
1/k}} $です。 $ k $のエッジを持つツリーでも同様です。一般的な結果は、部分グラフ$ H $の出現のための閾値確率は$
max_ {J | subseteq H} n ^ { – | V(J)|/E(J)|} $です。平衡グラフ$ H
$(木、完全グラフ、サイクルなど)の$ n ^ { – | V(H)|/E |(H)|} $と同じです。

$ k $が$ n
$で成長するときの状況は異なります。私は閾値が何か分かっていませんが、ハミルトニアンのパスケースを見れば、余分な$ log n
$が十分であると思います。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です