文章目录
- 一、组合存在性定理
- 二、Ramsey 定理内容概要
一、组合存在性定理
组合存在性定理 主要有三个定理 , 有限偏序集分解定理 , Ramsey 定理 , 相异代表系存在定理 ;
1. 有限偏序集分解定理 :
- 偏序集
中 , 最大链长度是
, 则该偏序集至少可以分解成
条不相交的反链 ;
- 偏序集
中 , 最大反链长度是
, 则该偏序集至少可以分解成
条不相交的链 ;
链是集合的一个子集 , 其中的元素 两两都可比 , 反链是集合的一个子集 , 其中的元素 两两不可比 ;
参考 : 【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 ) 四、链与反链定理 ,
偏序集
中 , 最大链长度是
, 每次都将当前的极大元拿走放在一个划分块中 ,
次之后 , 就得到了
个划分块 , 所有的元素都已分配完毕 ;
2. Ramsey 定理 : 该定理是 鸽巢原理的推广 , 该推广本质上是判定某种组合配置的存在性 ;
3. 相异代表系存在定理 : Hall 定理 ;
二部图 : 图的节点分为
两个部分 ,
集合内部没有边 ,
集合内部没有边 , 边都是从
集合连接到
集合 ;
完备匹配 : 在二部图中存在一个 完备的匹配 , 在
集合中每个节点都可以找到
集合中与其匹配的节点 ;
结论 :
的子集对应的
集合的节点个数 , 不比该
子集个数少 ;
二、Ramsey 定理内容概要
鸽巢原理 :
- 简单形式
- 一般形式
在鸽巢原理的基础上进行推广 , 得到 Ramsey 定理 ;
Ramsey 定理 :
- 简单形式
- 小 Ramsey 数
- 一般形式
- Ramsay 数已知结果
