極限的組み合わせ論

極限的組合せ論は、それ自体が数学の一部である組合せ論の分野です。極限的組合せ論は、一定の制約を満たす必要がある場合に、有限オブジェクト (数値、グラフ、ベクトル、集合など) の集合がどれだけ大きく、またはどれだけ小さくなることができるかを研究します。

極限的組合せ論の多くは集合のクラスに関するもので、これは極限集合論と呼ばれます。たとえば、n要素の集合において、互いに交差できるk要素の部分集合の最大数はいくつでしょうか。どの部分集合も他の部分集合を含まない部分集合の最大数はいくつでしょうか。後者の質問は、極限集合論の多くを生み出した スペルナーの定理によって答えられます。

別の種類の例: 3 人のうち 2 人が知り合いで、2 人が知らない場合、パーティーに何人招待できますか?ラムゼー理論によれば、そのようなパーティーには最大 5 人までしか参加できません。または、非ゼロの整数の有限集合が与えられ、マークされた 2 つの整数の合計はマークできないという制約の下で、この集合のできるだけ大きなサブセットをマークするように求められたとします。(与えられた整数が実際に何であるかに関係なく) 少なくとも 3 分の 1 は常にマークできるようです。

• 極値グラフ理論
• ザウアー・シェラーの補題
• エルデシュ・コー・ラドーの定理
• クラスカル・カトーナ定理
• フィッシャーの不等式
• 和集合予想

• Jukna, Stasys (2011)、極限的組合せ論、コンピュータサイエンスへの応用、Springer Verlag、ISBN 978-3-642-17363-9。
• Alon, Noga ; Krivelevich, Michael (2006)、極限的および確率的組合せ論(PDF)。
• フランクル、ピーター;ロドル、ヴォイチェフ(1987)、「禁断の交差点」、アメリカ数学会誌、300 (1): 259–286、doi : 10.2307/2000598、JSTOR  2000598。