也想过做一个复刻教材类似的Notes,上学期也干过这事,但是一则费力,再则意义不大,未若做一些有趣的探索记录。
哈斯图
哈斯图是用于描述偏序关系的图,具体地,我们需要先定义覆盖:
覆盖
设
简单来说,就是不存在元素能插入其中(
那么哈斯图,就是一个有向图,其顶点是集合元素,设若

哈斯图能让我们一眼看出偏序关系中的“大小”,尽管和熟知的小于等于略有差别,但是这样清晰的结构是相当好的。
在上方的则在偏序链条中相对高位,同一层的元素之间不可比。任意两个元素都不可比的偏序集中的集合被称为反链,所以一层元素就是一层反链。
设若是一个全序集,那么可想见哈斯图是一条无分支的链条。
哈斯图与立方体
我们看到
顶点上,n 个元素的集合的幂集确实是
哈斯图与组合数,Sperner定理
例如三维,层中元素分别为1331,正是组合数。
当然,这是trivial的,幂集的生成本身就是组合。不过我们可以得知关于反链的信息,例如中间的反链是按层划分的最长的反链,我们可以猜想
这是所谓
proof
虽然层级划分相当美丽,但是一般的反链并不好找。也许我们需要旁敲侧击,反链意味着其中元素互相不可比,那么考虑哈斯图一条自下而上的链(maximal chain),则反链中的元素至多出现一次。那么反链与 maximal chain 的交的大小的期望自然小于等于 1。
假定
一条自下而上的 maximal chain,每向上走一步就相当于加入一个新元素。
我们考虑一个 k 元素
总的来说,我们有
那么设反链
我们考虑指示函数,
从而
而利用前面所述,也就是
这是所谓的
由此,我们有
移项得到
这就完成了证明
不得不说证明有些羚羊挂角( 利用 maximal chain 与反链的交的期望,侧面得到反链大小的约束。