序理论 学习笔记
xujindong_
·
2025-01-06 09:25:20
·
个人记录
概述
序理论研究与次序相关的内容。集合 X,Y 上的一个二元关系 R 可以被 R 的图描。R 的图 G(R) 含有若干元素分别属于 X,Y 的二元组，也就是 G(R)\subseteq X\times Y（X\times Y 是 X 和 Y 的笛卡尔积，即 \{(x,y)|x\in X,y\in Y\}）。xRy 成立当且仅当 (x,y)\in G(R)。若 X=Y，称 R 是齐次二元关系。下面我们研究的都是齐次二元关系。
二元关系可能有如下的特殊性质（下面的 R 为集合 S 上二元关系，a,b,c 均为任意 S 中元素）：
自反性：aRa；
反自反性：\neg(aRa)；
对称性：aRb\Longleftrightarrow bRa；
反对称性：aRb\wedge bRa\Longrightarrow a=b；
非对称性：aRb\Longrightarrow\neg(bRa)；
传递性：(aRb\wedge bRc)\Longrightarrow aRc；
连接性：a\ne b\Longrightarrow(aRb\vee bRa)；
良基性：\exists m\in S,\forall a\in S\setminus\{m\},\neg(aRm)（即 S 中有极小元 m）；
不可比的传递性：(\neg(aRb\vee bRa)\wedge (bRc\vee cRb))\Longrightarrow (aRc\vee cRa)（若 aRb\vee bRa，称 a,b 不可比，不可比具有传递性）。
通过这些性质，我们定义一些特殊的二元关系：
二元关系
自反性
反自反性
对称性
反对称性
非对称性
传递性
连接性
良基性
不可比的传递性
等价关系
有
有
有
预序
有
有
偏序
有
有
有
全序
有
有
有
有
良序
有
有
有
有
有
严格预序
有
有
严格偏序
有
有
有
严格弱序
有
有
有
有
严格全序
有
有
有
有
偏序
OI 中我们最常研究偏序。比如实数上的小于等于 \leq、正整数上的整除 \mid、某个集合的所有子集的包含关系都是偏序。
因为偏序集有传递性，我们可以将间接偏序的关系省去，可以用 Hasse 图表示有限偏序集和偏序关系：
上图是 \{1,3,6,9,18\} 上整除的 Hasse 图。对于 S 和其上的偏序关系 \preceq，对应的严格偏序为 \prec，若 x\prec y 且 \nexists z,x\prec z\prec y，则连边 x\to y。 最后我们会画出一个 DAG，偏序 x 的所有元素就是 x 能到达的点。
Dilworth 定理
对于偏序集 S 和其上的偏序关系 \preceq，定义链为 S 的子集满足两两元素均可比，即 A\subseteq S,\forall x,y\in A,x\preceq y\vee y\preceq x；反链为 S 的子集满足两两元素均不可比，即 A\subseteq S,\forall x,y\in A,x\preceq y\vee y\preceq x。S 的链覆盖为若干链的集合，S 中每个元素出现在这些链中恰好一次。
Dilworth 定理：有限偏序集中最长反链长度等于最小链覆盖。
证明：考虑归纳。删除 S 中的某个极大元（即出度为 0 的点），设剩下的图的最小链划分为 C_1\sim C_k，有若干长 k 的反链 S_1\sim S_r，每条反链都从 C_1\sim C_k 中各选一个元素组成。设 C_i 中可能构成最长反链的最大元素为 A_i，则 A_1\sim A_k 是一条反链。因为若存在 A_i\preceq A_j(i\ne j)，因为 A_i 是可能构成反链的最大元素，在包含 A_j 的反链中从 C_i 取的元素 e 满足 e\preceq A_i\preceq A_j，矛盾。
加入极大元 c，若 c 与任意 A_i 不可比，则 A_1\sim A_k 加上 c 是一条反链，且存在链覆盖 C_1\sim C_k,\{c\}，因此最小链覆盖和最长反链长度都为 k+1；若存在 A_i\preceq c，设链 K=\{c\}\cup\{z\leq x_i|z\in C_i\}，也就是 c 接上这条链上 A_i 之前的部分。从 S 删掉 K 后原来的所有反链都没了一个元素，而 A\setminus\{A_i\} 是一条长 k-1 的反链，因此 S\setminus K 的最小链覆盖和最长反链长度是 k-1。加上链 K 后 S 的链覆盖是 k，因为加入 c 最长反链不能变短，因此最长反链长度也是 c。
我们还有一个对偶的定理：
Mirsky 定理：有限偏序集中最长链长度等于最小反链覆盖。
将 DAG 按从 0 入度点的最长路分层，显然同层的元素构成反链，而最长链最多经过所有的层一次，每层分一条反链是其中一个最小反链覆盖。
Sperner 定理
Sperner 定理：设 S 是 n 元集合，\mathcal F 是 S 的一个反链，则 |\mathcal F|\leq C_n^{\lfloor\frac n2\rfloor}。
这就是说，大小为 n 个集合最多选出 C_n^{\lfloor\frac n2\rfloor} 个互不包含的子集。
构造方案就是所有大小 \lfloor\frac n2\rfloor 的集合。证明考虑直接构造链覆盖。我们归纳地构造，要求每条链的大小关于中心对称，形如 [s,n-s]。对于每条链 S_1,S_2,\cdots,S_m，集合新加一个元素 k，把链拆成 S_1,S_2,\cdots,S_m,S_m\cup\{k\} 和 S_1\cup\{k\},S_2\cup\{k\},\cdots,S_{m-1}\cup\{k\}，新方案仍然是对称链覆盖。而每条对称链都含一个大小 \lfloor\frac n2\rfloor 的集合，最后的链数为 C_n^{\lfloor\frac n2\rfloor}。
可以推广，在 [1,p_1]\times[1,p_2]\times\cdots\times[1,p_n] 的高维空间定义偏序关系，最长反链大小是坐标和为 \lfloor\frac12\sum_{i=1}^n(p_i+1)\rfloor 的点数。证明类似，新加入 [1,k] 的一维，构造 (S_{1\sim m-x},x),(S_{m-x},x\sim k)(1\leq x\leq\min(m,k))，所有链都经过中间层。