Extrémní kombinatorika - Extremal combinatorics

Extrémní kombinatorika je obor kombinatorika, který je sám součástí matematika. Extrémní kombinatorika studuje, jak velká nebo jak malá je sbírka konečných objektů (čísla, grafy, vektory, sady atd.) může být, pokud musí splňovat určitá omezení.

Hodně z extrémních kombinatorických obav třídy sad; tomu se říká teorie extrémních množin. Například v n-prvková sada, jaký je největší počet k-živel podmnožiny které se mohou párově protínat? Jaký je největší počet podmnožin, z nichž žádná neobsahuje žádnou jinou? Na druhou otázku odpovídá Spernerova věta, která dala vzniknout velké části extrémní teorie množin.

Jiný druh příkladu: Kolik lidí můžeme pozvat na večírek, kde mezi třemi lidmi jsou dva, kteří se znají, a dva, kteří se neznají? Ramseyova teorie ukazuje, že se takového večírku může zúčastnit maximálně pět osob. Nebo předpokládejme, že dostaneme konečnou množinu nenulových celých čísel a budeme požádáni, abychom označili co největší podskupinu této množiny s omezením, že součet dvou označených celých čísel nelze označit. Ukazuje se, že (nezávisle na tom, jaká jsou skutečně celá čísla!) Můžeme vždy označit alespoň jednu třetinu z nich.

Viz také

• Extrémní teorie grafů
• Sauer – Shelahovo lemma
• Erdős – Ko – Radova věta
• Věta Kruskal – Katona
• Fisherova nerovnost
• Odhady uzavřených unií

Reference

• Jukna, Stasys (2011), Extrémní kombinatorika s aplikacemi v informatice Birkhäuser Verlag, ISBN  3-540-66313-4.

• Alon, Noga; Krivelevich, Michael (2006), Extrémní a pravděpodobnostní kombinatorika (PDF).

• Frankl, Peter; Rödl, Vojtěch (1987), „Zakázané křižovatky“, Transakce Americké matematické společnosti, 300 (1): 259–286, doi:10.2307/2000598.