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