Loading article…
極値組み合わせ論は組み合わせ論の一分野であり、組み合わせ論自体も数学の一部です。極値組み合わせ論は、有限な対象（数、グラフ、ベクトル、集合など）の集合が、特定の制約を満たす場合に、どれほど大きく、あるいはどれほど小さくなり得るかを研究します。
極値組み合わせ論の多くは集合のクラスに関するものであり、これは極値集合論と呼ばれます。例えば、n個の要素からなる集合において、互いに交差するk個の要素からなる部分集合の最大数はいくつでしょうか？また、他のどの部分集合も含まない部分集合の最大数はいくつでしょうか？後者の問いは、極値集合論の多くを生み出したスペルナーの定理によって答えられます。
別の例を挙げると、3人ごとに2人が知り合いで2人が知らないパーティーに、何人を招待できるでしょうか。ラムゼー理論によれば、そのようなパーティーには最大で5人までしか参加できません（「友人と見知らぬ人に関する定理」を参照）。あるいは、有限個の非ゼロ整数の集合が与えられ、マークされた2つの整数の合計をマークできないという制約の下で、この集合の可能な限り大きな部分集合をマークするように求められたとします。与えられた整数が実際に何であるかに関係なく、常に少なくとも3分の1をマークできることがわかります。