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

文章目录

• 一、组合存在性定理
• 二、Ramsey 定理内容概要

一、组合存在性定理

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

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

• 偏序集

中 , 最大链长度是

, 则该偏序集至少可以分解成

条不相交的反链 ;

• 偏序集

中 , 最大反链长度是

, 则该偏序集至少可以分解成

条不相交的链 ;

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

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

偏序集

中 , 最大链长度是

, 每次都将当前的极大元拿走放在一个划分块中 ,

次之后 , 就得到了

个划分块 , 所有的元素都已分配完毕 ;

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

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

二部图 : 图的节点分为

两个部分 ,

集合内部没有边 ,

集合内部没有边 , 边都是从

集合连接到

集合 ;

完备匹配 : 在二部图中存在一个 完备的匹配 , 在

集合中每个节点都可以找到

集合中与其匹配的节点 ;

结论 :

的子集对应的

集合的节点个数 , 不比该

子集个数少 ;

二、Ramsey 定理内容概要

鸽巢原理 :

• 简单形式
• 一般形式

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

Ramsey 定理 :

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