一、组合存在性定理

---

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

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

• 偏序集

  <

  A

  ,

  ≼

  >

  <A , \preccurlyeq>

  <A,≼> 中 , 最大链长度是

  n

  n

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

  n

  n

  n 条不相交的反链 ;

• 偏序集

  <

  A

  ,

  ≼

  >

  <A , \preccurlyeq>

  <A,≼> 中 , 最大反链长度是

  n

  n

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

  n

  n

  n 条不相交的链 ;

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

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

偏序集

<

A

,

≼

>

<A , \preccurlyeq>

<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 数已知结果