极值组合学

极值组合数学是组合数学的一个领域，它本身就是数学的一部分。极值组合数学研究有限对象（数字、图形、向量、集合等）的集合在满足某些限制的情况下可以有多大或多小。

极值组合数学大部分都与集合类有关；这就是所谓的极值集合论。例如，在一个n元素集合的子集中，可以成对相交的k元素子集的最大数量是多少？最多能选取有多少个没有包含关系的子集？后一个问题由Sperner 定理回答，最大数量为${\binom {n}{\lceil {\frac {n}{2}}\rceil }}$，该定理推动了极值集合论的发展。

另一种例子：一个聚会，每三个人中有两个认识，两个不认识，可以邀请多少人？拉姆齐理论表明，最多有五个人可以参加这样的聚会。或者，假设给定一个有限的非零整数集，尽可能多地标记一些整数，并满足任意两个整数的和不能被标记。看起来（不论给什么整数）我们总是可以标记至少其中的三分之一。

另见

• 极值图论
• 绍尔-谢拉引理
• Erdős–Ko–Rado 定理
• 克鲁斯卡尔-卡托纳定理
• 费舍尔不等式
• 联合闭集猜想

参考

• Jukna, Stasys, Extremal Combinatorics, With Applications in Computer Science, Birkhäuser Verlag, 2011 [2023-04-16], ISBN 3-540-66313-4, （原始内容存档于2020-09-26） .
• Alon, Noga; Krivelevich, Michael, Extremal and Probabilistic Combinatorics (PDF), 2006 [2023-04-16], （原始内容存档 (PDF)于2011-06-09） .
• Frankl, Peter; Rödl, Vojtěch, Forbidden intersections, Transactions of the American Mathematical Society, 1987, 300 (1): 259–286, doi:10.2307/2000598 .