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 → 全頂点が次の色の頂点に行ければ勝ち