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

極值組合數學大部分都與集合有關;這就是所謂的極值集合論。例如,在一個n元素集合的子集中,可以成對相交的k元素子集的最大數量是多少?最多能選取有多少個沒有包含關係的子集?後一個問題由Sperner 定理回答,最大數量為,該定理推動了極值集合論的發展。

另一種例子:一個聚會,每三個人中有兩個認識,兩個不認識,可以邀請多少人?拉姆齊理論表明,最多有五個人可以參加這樣的聚會。或者,假設給定一個有限的非零整數集,儘可能多地標記一些整數,並滿足任意兩個整數的和不能被標記。看起來(不論給什麼整數)我們總是可以標記至少其中的三分之一。

另見

編輯
  • 極值圖論
  • 紹爾-謝拉引理
  • Erdős–Ko–Rado 定理
  • 克魯斯卡爾-卡托納定理
  • 費舍爾不等式
  • 聯合閉集猜想

參考

編輯