组合学笔记(二)格与分配格

tags: Combinatorics

写在前面

前一篇总结了偏序集以及偏序集上的基本运算, 还有格的一些简单定义与例子, 这次重点讲一下​

​格​

​​的其他主要性质以及​

​分配格​

​的一些定理与在组合中的应用.

预备知识

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

• 设是一个有的有限交半格, 则是一个格(对偶地,为具有的并半格, 则为格).
• 完全格: 若的每个子集都有交和并, 完全格含有.

半模格(semimodular lattice)

设为一有限格, 则下面两条件等价:

1. 分次, 且的秩函数满足:

   对, 有.

2. 若和都覆盖, 则覆盖和.

• :

  若都覆盖, 则显然有, 并且有. 由1中结论, 整理得到:

  所以.

• :

  反证法,取长度最小的非分次区间,找使得极大链长度相同的元素覆盖区间的左端点,由条件2推出矛盾.

  下面证明不等式

  成立.

  设存在, 使得:

  选取最小, 然后让最小, 假设(根据条件2的逆否命题, 不可能有都覆盖),可以做出大致的Hasse图如下:

• 由图得到:

  所以, 代入上面两式

  整理得到:

  显然有, 并且, 令, 我们得到, 满足:

  矛盾.

• 满足上述任何一个条件(命题)的有限格称为​

  ​有限上半模格​

  ​, 或​

  ​有限半模格​

  ​.
• 在元素为6的格中(共有15个), 有限半模格有8个. 分别是:,包含菱形结构的格5个, 以及两个穿过菱形的一条对角线的格两个.
• 存在唯一一个七个元素的不是模格的半模格, 其Hasse图如下



• 若有限格的对偶为半模格, 称为​

  ​下半模格​

  ​.
• 有限格为模格是分次的, 且其秩函数满足
• 元素个数小于6的半模格均为模格.
• 有补: 若格具有和(有限格显然具有), 且对于, 均有,使得.
• 唯一有补: 若对于, 互补元唯一.
• 相对有补: 若的每一个区间自身有补.
• 原子: 覆盖的元素, 如果每一个元素都是一些原子的并, 则称是原子的(或: 点格point lattice).
• 上原子: 被覆盖的元素, 上原子格同理.

设为一个有限半模格, 下面两条件等价:

1. 相对有补;
2. 是原子的.

满足上述1或2条件的有限半模格称为​

​有限几何格​

​.

分配格(distributive Lattices)

通过分配律定义的格,

• .
• .

两者可以互相转换.

• 所有的分配格都是模格.
• 偏序集的序理想构成的格;(序理想的并和交仍为序理想)

定理: (有限分配格基本定理,FTFDL) 设是有限分配格, 则(在同构意义下)存在唯一的有限偏序集, 使得.

• 并运算不可约:,如果不能写成的形式, 其中.
• 规定不是并运算不可约的.
• 交运算不可约:,如果不能写成的形式, 其中.
• 有限偏序集中的序理想在中是并运算不可约的是的主理想;

命题2:中并运算不可约元所成集合作为的(诱导)子偏序集, 与同构, 即.

证明FTFDL:(构造双射证明)

通过上述命题, 欲证明, 只需证明是上的并运算不可约元构成的子偏序集即可.

取, 令, 显然有, 定义映射:

该映射为一保持交运算的单射, 且其逆也保序. 只需证明满射即可.

令, 只需证明.(陪集等于像集)包含关系显然成立(定义,序理想), 设, 有

上式两边取交, 即, 应用分配律, 得到

我们有, 因为并运算不可约, 存在, 使得.

由于为序理想, 所以, , .

• 有限性的分配格: 具有的局部有限分配格;因此有唯一的秩函数,其中等于任意一条从到的饱和链的长度.
• , 有个秩为的元素, ,定义秩生成函数:(可能是幂级数)

命题3: 设是一个所有主序理想都有限的偏序集, 则的所有有限序理想按照包含关系排序构成的偏序集是有限性的分配格. 反之,如果是一个有限性的分配格, 是它的并运算不可约元构成的子偏序集, 则的每一个主序理想都是有限的且有.

命题4: 如果是一个元偏序集, 那么是分次的且秩为, 进一步, 作为的序理想, 元素是秩就是的元素个数.

在非同构的元偏序集和非同构的秩为的分配格之间存在一个双射, 这个双射把映成, 逆映射把映成它的并运算不可约元构成的子偏序集.

例子:

1. ;
2. , 其中:

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

​ 称为一个秩为的布尔代数.

绘制的Hasse图的方法:

1. 找出的极小元所成集合,. 绘制.
2. 选的极小元, 在上添加一个并运算不可约元, 该元素覆盖,(为主序理想) 并且满足覆盖条件的元素的并构成一个布尔代数.绘制所有的新的必要的并元素.
3. 重复2,使得对每一个元素, 其覆盖都有并, 得到分配格.
4. 选择的极小元, 在上加上并运算不可约元, 覆盖序理想.
5. 接着绘制, 填满所有的覆盖, 得到,继续这一过程得到.

例子:

对于栅格(fences), 其Hasse图如下:

1. 先绘制极小元构成的集合的序理想构成的格. 如下图所示
2. 寻找去掉极小元之后的偏序集的极小元, 绘制并连接:
3. 同理, 分别添加, 并将有覆盖关系的边进行连接如下:





4. 最后可以得到下面的Hasse图, 即为.

从图中直接可以得到: (用颜色区分不同的秩)