偏序集

偏序集（poset）是一种集合，其上定义了一种关系，该关系捕捉了一个元素先于或低于另一个元素的思想，但并不要求所有元素对都可比较。

Definition

偏序集是一个集合，其上带有一个二元关系，该关系是自反的、反对称的和传递的；在该关系下，元素可能可比较或不可比较。

Scope

本主题涵盖偏序的公理、哈斯图、链和反链、最大和最小元素、保序映射和对偶性，以及迪尔沃斯和米尔斯基的组合结构定理。它还介绍了偏序集的莫比乌斯函数，这是广义容斥原理的序理论引擎。

Core questions

• 元素之间的优先关系如何公理化和表示？
• 偏序集的元素如何划分为链或反链？
• 偏序集中最大的反链或最长的链是什么？
• 莫比乌斯函数如何推广容斥原理的计数？

Key concepts

• 偏序公理
• 哈斯图
• 链和反链
• 最大元素和最小元素
• 迪尔沃斯定理
• 莫比乌斯函数

Key theories

迪尔沃斯定理

在任何有限偏序集中，覆盖所有元素所需的最小链数等于最大反链的大小，这是一个具有许多组合学推论的基本极小-极大对偶性。

偏序集的莫比乌斯函数

每个局部有限偏序集都带有一个莫比乌斯函数，该函数可以反转序上的求和；罗塔的理论使其成为容斥原理和数论反演的统一来源。

Clinical relevance

偏序集可以建模带有依赖的任务调度、版本和继承层次结构以及偏好和包含关系，而链和反链分解则出现在调度和排序算法中。

History

迪尔沃斯1950年的链-反链定理和罗塔1964年的莫比乌斯函数基础理论将有序集的组合学研究转变为现代离散数学的核心主题。

Key figures

• Robert Dilworth
• Gian-Carlo Rota
• Richard P. Stanley

Seminal works

• davey2002
• stanley2011

Frequently asked questions

什么是哈斯图？

它是一种有限偏序集的图示，其中每个元素是一个点，放置在其所覆盖的元素之上，边仅存在于覆盖对之间，因此序关系向上读取。

什么是反链？

反链是一组元素，其中任意两个元素都不可比较，例如一组子集，其中没有一个子集包含另一个子集。