存在性定理

存在性定理是一类定性描述。要把某种离散对象按某个确定的约束条件进行安排，如果这种特定的安排是否存在还不确定，就需要首先讨论这种特定安排的存在性问题。

在经典组合数学中， 霍尔定理 、 拉姆齐定理 和狄尔沃斯定理是三个主要的存在性定理。

内容

霍尔定理

霍尔定理使用于组合问题中； 二部图 G中的两部分顶点组成的集合分别为X, Y, ， ，G中有一组无公共点的边，一端恰好为组成X的点的 充分必要条件 是： X中的任意k个点至少与Y中的k(1≤k≤m)个点相邻。

霍尔定理 还有一个重要推论：二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点， 则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t-正则的二部图存在完美匹配。

本 定理 是 二分图 匹配 问题中匈牙利算法的基础。

拉姆齐定理

在组合数学上， 诺曼·拉姆齐 (Ramsey)定理是要解决以下的问题：要找这样一个最小的数 n ，使得 n 个人中必定有 k 个人相识或 l 个人互不相识。

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的 完全图 的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

狄尔沃斯定理

(Dilworth's theorem)

狄尔沃斯定理亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此 定理 的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限 全序集 的可比图为 完全图 。