Lubell–Yamamoto–Meshalkin 不等式
| 卢贝尔–山本–梅沙尔金不等式 | |
|---|---|
| 术语名称 | 卢贝尔–山本–梅沙尔金不等式 |
| 英语名称 | Lubell–Yamamoto–Meshalkin inequality |
| 别名 | LYM不等式 |
Lubell–Yamamoto–Meshalkin 不等式(Lubell–Yamamoto–Meshalkin inequality, LYM inequality)是关于幂集格中反链大小上界的不等式。
定理
对大小为 [math]\displaystyle{ n }[/math] 的集合 [math]\displaystyle{ U }[/math] ，若其子集族 [math]\displaystyle{ A }[/math] 是一个 Sperner 系， 则 [math]\displaystyle{ \sum_{S \in A} \frac{1}{\binom{n}{|S|}} \leq 1 }[/math]
等价地，记 [math]\displaystyle{ a_k = |\{S\in A\mid |S|=k\}| }[/math]，则： [math]\displaystyle{ \sum_{k=0}^n \frac{a_k}{\binom{n}{k}} \leq 1 }[/math] 。
取等号当且仅当 [math]\displaystyle{ A }[/math] 由所有大小为 [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] 或所有大小为 [math]\displaystyle{ \lceil n/2 \rceil }[/math] 的子集构成。
说明
- 可以推出 Sperner 定理