The Local Lemma (The Probabilistic Method, Chapter 5)

  • The Local Lemma
    • イベントの dependency digraph
    • 条件ホゲを満たせば,全部の事象が起こらない,という減少がある確率ピヨ以上で起こる
    • 証明:帰納法.独立な場合と従属な場合を分けて計算するだけ.
  • Symmetric Case
    • 各イベント(発生確率 p 以下)が d 個までに依存する場合,ep(d+1) ≦ 1 なら,全部の事象が起こらない,ということがある
  • 例: Hypergraph Coloring
    • 各辺サイズ k,高々 d 辺とのみ交差,e(d+1) ≦ 2^{k-1} → 2-colorable
  • 例: Directed Cycles
    • 最小出次数δ,最大入次数Δ
    • e(Δδ+1)(1-1/k)^δ<1 → グラフは mod k で長さ 0 の閉路を含む
    • k 色で random coloring → 全頂点が次の色の頂点に行ければ勝ち