【组合数学】组合存在性定理 ( 三个组合存在性定理 | 有限偏序集分解定理 | Ramsey 定理 | 相异代表系存在定理 | Ramsey 定理内容概要 )

一、组合存在性定理

组合存在性定理 主要有三个定理 , 有限偏序集分解定理 , Ramsey 定理 , 相异代表系存在定理 ;

1. 有限偏序集分解定理 :

• 偏序集 < A , ≼ > 中 , 最大链长度是 n n n , 则该偏序集至少可以分解成 n n n 条不相交的反链 ;

• 偏序集 < A , ≼ > 中 , 最大反链长度是 n n n , 则该偏序集至少可以分解成 n n n 条不相交的链 ;

链是集合的一个子集 , 其中的元素 两两都可比 , 反链是集合的一个子集 , 其中的元素 两两不可比 ;

参考 : 【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 ) 四、链与反链定理 ,

偏序集 < A , ≼ > 中 , 最大链长度是 n n n , 每次都将当前的极大元拿走放在一个划分块中 , n n n 次之后 , 就得到了 n n n 个划分块 , 所有的元素都已分配完毕 ;

2. Ramsey 定理 : 该定理是 鸽巢原理的推广 , 该推广本质上是判定某种组合配置的存在性 ;

3. 相异代表系存在定理 : Hall 定理 ;

二部图 : 图的节点分为 X , Y X , Y X,Y 两个部分 , X X X 集合内部没有边 , Y Y Y 集合内部没有边 , 边都是从 X X X 集合连接到 Y Y Y 集合 ;

完备匹配 : 在二部图中存在一个 完备的匹配 , 在 X X X 集合中每个节点都可以找到 Y Y Y 集合中与其匹配的节点 ;

结论 : X X X 的子集对应的 Y Y Y 集合的节点个数 , 不比该 X X X 子集个数少 ;

二、Ramsey 定理内容概要

鸽巢原理 :

• 简单形式
• 一般形式

在鸽巢原理的基础上进行推广 , 得到 Ramsey 定理 ;

Ramsey 定理 :

• 简单形式
• 小 Ramsey 数
• 一般形式
• Ramsay 数已知结果