組合學筆記(一)偏序集概念與應用

tags: Combinatorics

寫在前面

最近看論文需要用到偏序集的有關概念, 在這裡先梳理一下, 友善以後的使用. 主要參考的書籍是Stanley的經典名著《計數組合學(第一卷)》.

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

定義

偏序集(partially-ordered set, poset)是一個集合, 連同一個記為()的二進制關系, 滿足下面的三條公理:

1. 對所有的,(自反性).
2. 如果且, 則(反對稱性).
3. 如果且, 則(傳遞性).

• 偏序集中的兩個元素可比, 如果或者, 否則稱其為不可比的.

• 偏序集同構:

  之間存在一個保持序關系的雙射使得他的逆也保持序關系. 即:

• 弱子偏序集: 偏序集的子集連同上滿足"如果在中有, 則在中"的偏序關系, 則為的弱子偏序集.
• 加細: 若是的弱子偏序集, 且作為集合有, 則稱是的加細.
• 誘導子偏序集:的子集連同上的偏序關系:“, 在中有在中有”.
• 誘導序:是的誘導子偏序集, 則具有誘導序. 有限偏序集恰好有個誘導子偏序集.
• 局部有限偏序集: 偏序集的任一區間都是有限的. (可完全由其覆寫關系所确定)
• 凸子偏序集: 若在偏序集中有且, 就有, 此時區間也是凸的.

• 覆寫: 設, 若且不存在使得. 充要條件:且.
• (有限偏序集的)Hasse圖: 頂點為中元素, 邊為覆寫關系, 并且若則繪制在"上面"的圖形.

Hasse圖的一些例子, 可以參考我的前面的部落格. 含有四個元素的偏序集有16個, Hasse圖如下圖所示

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

• 若, 那麼的上界為滿足的元素.
• 的最小上界為的上界, 使得對的每一個上界, 都有.
• 若最小上界存在, 則唯一, 記為, 同理, 最大下界記為.
• 格(lattice): 是一個偏序集, 其中每一對元素的最小上界和最大下界都存在.
• 格滿足的一些性質:

鍊(chain, 全序集,線性序集)

• 指任意兩個元素都可以比較大小的偏序集. 例如及其上的普通序關系, 記為.
• 偏序集的子集為鍊, 若 作為的子偏序集的時候是鍊.
• 偏序集中的鍊為飽和的(不可加細的), 如果不存在使得對于中某兩個元素有, 并且仍然構成鍊. (有點像上确界的定義, 沒辦法再塞進去一個元素)
• 局部有限偏序集中的鍊是飽和的, 對有覆寫.
• 有限鍊的長度.
• 有限偏序集的長度(秩)定義為.
• 偏序集的區間的長度記為.
• 秩為的分次偏序集: 若偏序集的所有極大鍊都具有相同長度. 此時存在唯一秩函數, 滿足:

1. 若是的極小元, 則;
2. 若在中有覆寫, 則.

• 如果, 稱元素具有秩.
• 偏序集的秩生成函數: 對秩為的分次偏序集, 其中有個元素的秩為, 則的秩生成函數為:
• 偏序集的可重鍊: 具有重複元素的鍊, 即基集為的某個鍊的可重集合.
• 反鍊(Sperner族, 叢集): 偏序集的子集, 其中任意兩個不同元素不可比較.

序理想

• 的序理想(半理想, 下集, 下降子集): 滿足下列條件的的子集. (有點像左開右閉區間)
• 對偶序理想(濾子): 滿足下列條件的的子集. (有點像左閉右開區間)

• 偏序集有限時, 的反鍊和序理想之間存在一一對應.

  也就是說, 為的極大元構成的集合, 而

• 偏序集的所有序理想按照包含關系排序, 構成一個偏序集, 記為.
• 生成: 若序理想和極大元所成集合之間滿足式. 若, 記為由生成的序理想.
• 主序理想: 序理想為由生成的主序理想, 記為.
• 主對偶序理想:表示由生成的主對偶序理想.

偏序集上的運算

• 直和(不交并): 即定義在上的偏序集, 記為, 指兩不相交集合上定義的偏序集, 使得在中有.

• 即在中, 或者有, 或者有.
• 若一個偏序集不是兩個非空偏序集的不交并, 這稱之為連通的.
• 和自身的次不交并記為.
• 一個元反鍊同構于.

• 有序和: 即定義在上的偏序集記為, 使得在中.

• 即在中, 或者有, 或者有, 或者有.
• 一條元鍊由給出.
• 串并聯偏序集: 在個四元偏序集中, 恰有一個是不能由偏序集通過直和運算與有序和運算構造出來.

這個偏序集為上圖中的第二行的最後一個, 顯然他不能夠通過直和以及有序和運算生成.

• 直積(笛卡爾積): 定義在集合上的偏序集, 滿足在中有.

• 即, .
• 和它自身的次直積記為.
• .
• 如果是分次的且秩生成函數為和, 則也是分次的且:

• 有序積:, 定義在上, 滿足, 若且, 或.

• 如果是分次的并且的秩為, 則對于有序積, 有

• 對偶: 記為, 是與定義在同一集合上的偏序集, 但在中.

• 自對偶:.

• 下面是所有含四個元素的偏序集中的自對偶圖
• 這裡是所有含有四個元素的偏序集中的非自對偶偏序集, 共有8個, 顯然這些偏序集的對偶都是成對出現的

格(lattice)

格是這樣一類偏序集: 其中每一對元素的最小上界和最大下界都存在的偏序集.

子集格

因子格