主题
Search

迪尔沃斯引理

集合 P 的 偏序宽度 等于覆盖 P 所需的最小 链 数。等价地，如果一个包含 P 的 ab+1 个元素的集合是 偏序的，那么 P 包含一个大小为 a+1 的 链 或一个大小为 b+1 的 反链。令 N 为 P 的 基数，W 为 偏序宽度，L 为 偏序长度，则最后这个陈述表示 N<=LW。迪尔沃斯引理是 Erdős-Szekeres 定理 的推广。Ramsey 定理 推广了迪尔沃斯引理。

另请参阅

反链, 链, 组合数学, Erdős-Szekeres 定理, Ramsey 定理

使用 Wolfram|Alpha 探索

参考文献

Dilworth, R. P. "偏序集的分解定理。" 数学年刊 51, 161-166, 1950.Skiena, S. "迪尔沃斯引理。" §6.4.2 in 使用 Mathematica 实现离散数学：组合数学和图论。 Reading, MA: Addison-Wesley, pp. 241-243, 1990.

在 Wolfram|Alpha 中被引用

迪尔沃斯引理

引用为

Weisstein, Eric W. "迪尔沃斯引理。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/DilworthsLemma.html

主题分类