Correlation Inequalities (The Probabilistic Method, Chapter 6)

• 例 Erdos-Renyi グラフ G
• The Four Functions Theorem
  • N: {1..n}, P(N): all subsets
  • 4 つの関数があって，集合2つについてホゲ（∩, ∪）が満たされれば，冪集合２つに対してピヨ．
  • 冪集合だけじゃなく，分配速を満たす束にも拡張可
  • Corollary: 分配速を満たす束なら，|X| |Y| ≦ |X∨Y| |X∧Y|
• The FKG Inequality
  • 分配束を満たす束． log-supermodular, increasing functions
  • (Σuf)(Σug) ≦ (Σufg)(Σu)