查看“︁极值组合学”︁的源代码

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

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

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

== 另见 ==

* 极值图论
* [[紹爾-謝拉赫引理|绍尔-谢拉引理]]
* Erdős–Ko–Rado 定理
* 克鲁斯卡尔-卡托纳定理
* 费舍尔不等式
* 联合闭集猜想

== 参考 ==

* {{Citation|last=Jukna|first=Stasys|publisher=Birkhäuser Verlag|title=Extremal Combinatorics, With Applications in Computer Science|url=http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/preface.html|isbn=3-540-66313-4|year=2011|accessdate=2023-04-16|archive-date=2020-09-26|archive-url=https://web.archive.org/web/20200926113028/http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/preface.html|dead-url=yes}}.
* {{Citation|last=Alon|first=Noga|author1-link=Noga Alon|last2=Krivelevich|first2=Michael|author2-link=Michael Krivelevich|url=http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf|title=Extremal and Probabilistic Combinatorics|year=2006|accessdate=2023-04-16|archive-date=2011-06-09|archive-url=https://web.archive.org/web/20110609193536/http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf|dead-url=no}}.
* {{Citation|last=Frankl|first=Peter|author1-link=Péter Frankl|last2=Rödl|first2=Vojtěch|author2-link=Vojtěch Rödl|title=Forbidden intersections|journal=Transactions of the American Mathematical Society|volume=300|number=1|pages=259–286|year=1987|doi=10.2307/2000598}}.
[[Category:组合优化]]
[[Category:组合数学]]