tags: Combinatorics

写在前面

最近看论文需要用到偏序集的有关概念, 在这里先梳理一下, 方便以后的使用. 主要参考的书籍是Stanley的经典名著《计数组合学(第一卷)》.

下面若不特别指明, 均用代表偏序集.

定义

偏序集(partially-ordered set, poset)是一个集合, 连同一个记为()的二元关系, 满足下面的三条公理:

1. 对所有的,(自反性).
2. 如果且, 则(反对称性).
3. 如果且, 则(传递性).

• 偏序集中的两个元素可比, 如果或者, 否则称其为不可比的.
• 偏序集同构:
  之间存在一个保持序关系的双射使得他的逆也保持序关系. 即:
  

• 弱子偏序集: 偏序集的子集连同上满足"如果在中有, 则在中"的偏序关系, 则为的弱子偏序集.
• 加细: 若是的弱子偏序集, 且作为集合有, 则称是的加细.
• 诱导子偏序集:的子集连同上的偏序关系:“, 在中有在中有”.
• 诱导序:是的诱导子偏序集, 则具有诱导序. 有限偏序集恰好有个诱导子偏序集.
• 局部有限偏序集: 偏序集的任一区间都是有限的. (可完全由其覆盖关系所确定)
• 凸子偏序集: 若在偏序集中有且, 就有, 此时区间也是凸的.

• 覆盖: 设, 若且不存在使得. 充要条件:且.
• (有限偏序集的)Hasse图: 顶点为中元素, 边为覆盖关系, 并且若则绘制在"上面"的图形.

Hasse图的一些例子, 可以参考我的前面的博客. 含有四个元素的偏序集有16个, Hasse图如下图所示

• 偏序集具有: 若存在某个元素使得对所有的都有.
• 偏序集具有: 若存在某个元素使得对所有的都有.
• : 表示在中加入得到的偏序集(不管本身是否含有和).

• 若, 那么的上界为满足的元素.
• 的最小上界为的上界, 使得对的每一个上界, 都有.
• 若最小上界存在, 则唯一, 记为, 同理, 最大下界记为.
• 格(lattice): 是一个偏序集, 其中每一对元素的最小上界和最大下界都存在.
• 格满足的一些性质:
  

链(chain, 全序集,线性序集)

• 指任意两个元素都可以比较大小的偏序集. 例如及其上的普通序关系, 记为.
• 偏序集的子集为链, 若 作为的子偏序集的时候是链.
• 偏序集中的链为饱和的(不可加细的), 如果不存在使得对于中某两个元素有, 并且仍然构成链. (有点像上确界的定义, 没办法再塞进去一个元素)
• 局部有限偏序集中的链是饱和的, 对有覆盖.
• 有限链的长度.
• 有限偏序集的长度(秩)定义为.
• 偏序集的区间的长度记为.
• 秩为的分次偏序集: 若偏序集的所有极大链都具有相同长度. 此时存在唯一秩函数, 满足:

1. 若是的极小元, 则;
2. 若在中有覆盖, 则.

• 如果, 称元素具有秩.
• 偏序集的秩生成函数: 对秩为的分次偏序集, 其中有个元素的秩为, 则的秩生成函数为:
  
• 偏序集的可重链: 具有重复元素的链, 即基集为的某个链的可重集合.
• 反链(Sperner族, 集群): 偏序集的子集, 其中任意两个不同元素不可比较.

序理想

• 的序理想(半理想, 下集, 下降子集): 满足下列条件的的子集. (有点像左开右闭区间)
  
• 对偶序理想(滤子): 满足下列条件的的子集. (有点像左闭右开区间)
  
• 偏序集有限时, 的反链和序理想之间存在一一对应.
  也就是说, 为的极大元构成的集合, 而
  
• 偏序集的所有序理想按照包含关系排序, 构成一个偏序集, 记为.
• 生成: 若序理想和极大元所成集合之间满足式. 若, 记为由生成的序理想.
• 主序理想: 序理想为由生成的主序理想, 记为.
• 主对偶序理想:表示由生成的主对偶序理想.

偏序集上的运算

• 直和(不交并): 即定义在上的偏序集, 记为, 指两不相交集合上定义的偏序集, 使得在中有.

• 即在中, 或者有, 或者有.
• 若一个偏序集不是两个非空偏序集的不交并, 这称之为连通的.
• 和自身的次不交并记为.
• 一个元反链同构于.

• 有序和: 即定义在上的偏序集记为, 使得在中.

• 即在中, 或者有, 或者有, 或者有.
• 一条元链由给出.
• 串并联偏序集: 在个四元偏序集中, 恰有一个是不能由偏序集通过直和运算与有序和运算构造出来.

这个偏序集为上图中的第二行的最后一个, 显然他不能够通过直和以及有序和运算生成.

• 直积(笛卡尔积): 定义在集合上的偏序集, 满足在中有.

• 即, .
• 和它自身的次直积记为.
• .
• 如果是分次的且秩生成函数为和, 则也是分次的且:
  

• 有序积:, 定义在上, 满足, 若且, 或.

• 如果是分次的并且的秩为, 则对于有序积, 有
  

• 对偶: 记为, 是与定义在同一集合上的偏序集, 但在中.

• 自对偶:.

• 下面是所有含四个元素的偏序集中的自对偶图
• 这里是所有含有四个元素的偏序集中的非自对偶偏序集, 共有8个, 显然这些偏序集的对偶都是成对出现的

格(lattice)

格是这样一类偏序集: 其中每一对元素的最小上界和最大下界都存在的偏序集.

子集格

, 的所有子集的集合构成偏序集, 称为子集格.

因子格

,(为正整数) 定义, 若可以被整除, 记为, 的所有正整数因子以"自然的"方式成为一个偏序集.