也想过做一个复刻教材类似的Notes,上学期也干过这事,但是一则费力,再则意义不大,未若做一些有趣的探索记录。

哈斯图

哈斯图是用于描述偏序关系的图,具体地,我们需要先定义覆盖:

覆盖

设 为偏序集, ,如果 且不存在 使得 ,那就称 覆盖 。

简单来说,就是不存在元素能插入其中(

那么哈斯图,就是一个有向图,其顶点是集合元素,设若 覆盖 ,就画出自 到 的一条边。例如:

![](images/Pasted image 20260912105006.png)

哈斯图能让我们一眼看出偏序关系中的“大小”,尽管和熟知的小于等于略有差别,但是这样清晰的结构是相当好的。

在上方的则在偏序链条中相对高位,同一层的元素之间不可比。任意两个元素都不可比的偏序集中的集合被称为反链,所以一层元素就是一层反链。

设若是一个全序集,那么可想见哈斯图是一条无分支的链条。

哈斯图与立方体

我们看到 这个偏序集的哈斯图,它长得很像一个立方体。这是巧合吗?

顶点上,n 个元素的集合的幂集确实是 个。同时,对于三维,我们可以用 这个笛卡尔积来刻画每个幂集,用 表征每个元素是否出现,则这恰好同构于 ,也正对应于一个三维立方体的坐标。对任意维度实际上应该是类似的,构成一个 维的超立方体。

哈斯图与组合数,Sperner定理

例如三维,层中元素分别为1331,正是组合数。

当然,这是trivial的,幂集的生成本身就是组合。不过我们可以得知关于反链的信息,例如中间的反链是按层划分的最长的反链,我们可以猜想

最长反链大小

这是所谓 定理。但是我们并没有验证其正确性。

proof

虽然层级划分相当美丽,但是一般的反链并不好找。也许我们需要旁敲侧击,反链意味着其中元素互相不可比,那么考虑哈斯图一条自下而上的链(maximal chain),则反链中的元素至多出现一次。那么反链与 maximal chain 的交的大小的期望自然小于等于 1。

假定 是我们的全集。

一条自下而上的 maximal chain,每向上走一步就相当于加入一个新元素。

我们考虑一个 k 元素 子集被 maximal chain经过,也就是说 maximal chain 的前 k 个子集都包含于该集合。例如我们选取 作为 的子集,maximal chain 要经过哈斯图中的 这个节点,那么第一步要么 2 要么 4,下一步补上剩下那个。

总的来说,我们有 种走法,那么前 个元素被限定了,我们就有 种走法,换言之,经过的概率也就是

那么设反链 与随机的 maximal chain 的交集为 ,这个集合的元素数量小于等于 1 ,故而 。接下来想办法计算这个期望。

我们考虑指示函数, ,只有 被 经过其为1,否则为0.那么

从而

而利用前面所述,也就是

这是所谓的 不等式 。

由此,我们有

移项得到

这就完成了证明

不得不说证明有些羚羊挂角( 利用 maximal chain 与反链的交的期望,侧面得到反链大小的约束。