ランダムグラフの奇妙な論理

『ランダムグラフの奇妙な論理』は、ランダムグラフにおけるゼロイチ法則に関する書籍である。ジョエル・スペンサーによって執筆され、2001年にシュプリンガー・フェルラーク社から、同社の書籍シリーズ「アルゴリズムと組み合わせ論」の第22巻として。

この本のランダム グラフはエルデシュ・レーニ・ジルベール モデルから生成されています。${\displaystyle G(n,p)}$その中で${\displaystyle n}$頂点が与えられ、各頂点のペアごとに独立に確率で、各頂点のペアを辺で接続するかどうかがランダムに選択されます。${\displaystyle p}$接続を作る。ゼロイチ法則は、グラフの特定の特性と特定の選択に対して、${\displaystyle p}$、特性を持つグラフを生成する確率は、極限においてゼロまたは1に近づく。${\displaystyle n}$無限大に及ぶ。^{[ 1 ]}

この分野における基本的な結果であり、グレブスキーらとロナルド・ファギンによって独立に証明されたのは、ゼロイチ法則が存在するということである。${\displaystyle G(n,1/2)}$グラフの一次論理で記述できるすべてのプロパティについて。^{[ 2 ]}さらに、無限ラドグラフがそのプロパティを持つ場合に限り、極限確率は 1 になります。たとえば、このモデルのランダムグラフには、確率が 1 に近づく三角形が含まれます。確率が 0 に近づく普遍頂点が含まれます。他の選択肢については、${\displaystyle p}$他の結果も起こり得る。例えば、三角形が含まれる確率の限界は、次の場合に0から1の間となる。${\displaystyle p=c/n}$定数に対して${\displaystyle c}$; 選択肢が小さいほど 0 に近づく傾向がある${\displaystyle p}$より大きな選択肢の場合は 1 まで。${\displaystyle 1/n}$は三角形を含む性質の閾値であると言われており、つまり、 の値を分離します。${\displaystyle p}$限界確率が 1 の値から限界確率 0 の値を選択する。^{[ 1 ]}

この本の主な結果（スペンサーとサハロン・シェラによって証明された）は、${\displaystyle n}$閾値関数ではない。つまり、${\displaystyle a>0}$は無理数であり、ランダムグラフの一次特性にはゼロイチ法則が存在する。${\displaystyle G(n,n^{-a})}$[ ^{1 ]}証明の重要なツールはエーレンフォイヒト・フレッセゲーム^である。^{[ 3 ]}

本書は基本的に単一の定理の証明であり、その分野の専門家を対象としているが、有限モデル理論とランダムグラフ理論の多くの重要なトピックを読者に紹介する読みやすいスタイルで書かれている。ランダムグラフに関する別の本の著者でもある書評家のヴァレンティン・コルチンは、本書は「自己完結的で読みやすく、優雅な文章が特徴」であり、確率論者や論理学者に勧めていると述べている。^{[ 2 ]}書評家のアレッサンドロ・ベラルドゥッチは、本書を「美しく書かれている」とし、その主題を「魅力的」と評している。^{[ 1 ]}