極值組合學

極值組合數學是組合數學的一個領域，它本身就是數學的一部分。極值組合數學研究有限對象（數字、圖形、向量、集合等）的集合在滿足某些限制的情況下可以有多大或多小。

極值組合數學大部分都與集合類有關；這就是所謂的極值集合論。例如，在一個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 .