Correlation Inequalities (The Probabilistic Method, Chapter 6)

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