Topologická kombinatorika - Topological combinatorics - Wikipedia

The matematický disciplína topologická kombinatorika je aplikace topologických a algebraických topologických metod při řešení problémů v kombinatorice.

Dějiny

Kázeň kombinatorická topologie použité kombinatorické koncepty v topologie a na počátku 20. století se to změnilo na pole algebraická topologie.

V roce 1978 se situace obrátila - k řešení problému v roce 2006 byly použity metody z algebraické topologie kombinatorika - když László Lovász prokázal Kneserova domněnka, čímž začíná nová studie topologická kombinatorika. Lovászův důkaz použil Borsuk – Ulamova věta a tato věta si v této nové oblasti zachovává významnou roli. Tato věta má mnoho ekvivalentních verzí a analogů a byla použita při studiu spravedlivé rozdělení problémy.

V jiné aplikaci homologický metody teorie grafů Lovász prokázal jak neřízenou, tak řízenou verzi domněnky András Frank: Vzhledem k k-připojený graf G, k bodů ${ displaystyle v_ {1}, ldots, v_ {k} ve V (G)}$, a k kladná celá čísla ${ displaystyle n_ {1}, n_ {2}, ldots, n_ {k}}$ součet až ${ displaystyle | V (G) |}$, existuje oddíl ${ displaystyle {V_ {1}, ldots, V_ {k} }}$ z ${ displaystyle V (G)}$ takhle ${ displaystyle v_ {i} ve V_ {i}}$, ${ displaystyle | V_ {i} | = n_ {i}}$, a ${ displaystyle V_ {i}}$ překlenuje připojený podgraf.

V roce 1987 problém s rozdělením náhrdelníku byl vyřešen Noga Alon pomocí věty Borsuk – Ulam. Používá se také ke studiu problémy se složitostí v algoritmy lineárního rozhodovacího stromu a Aanderaa – Karp – Rosenbergova domněnka. Mezi další oblasti patří topologie částečně uspořádaných množin a objednávky na bruhat.

Navíc metody z diferenciální topologie nyní mají kombinatorický analog v diskrétní Morseova teorie.

Viz také

• Spernerovo lemma
• Diskrétní vnější počet
• Topologická teorie grafů
• Kombinatorická topologie
• Konečný topologický prostor

Reference

• de Longueville, Mark (2004), „25 let důkaz Kneserova domněnky - nástup topologické kombinatoriky“ (PDF), Zpravodaj EMS „Southampton, Hampshire: European Mathematical Society, s. 16–19, vyvoláno 2008-07-29.

Další čtení

• Björner, Anders (1995), "Topologické metody", v Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Příručka kombinatoriky (PDF), 2, The MIT press, ISBN  978-0-262-07171-0.
• Kozlov, Dmitrij (2005), Trendy v topologické kombinatorice, arXiv:math.AT/0507390, Bibcode:Matematika 2005 ... 7390 tis.
• Kozlov, Dmitrij (2007), Kombinatorická algebraická topologieSpringer, ISBN  978-3-540-71961-8.
• Lange, Carsten (2005), Kombinatorické zakřivení, skupinové akce a obarvení: Aspekty topologické kombinatoriky (PDF), Ph.D. teze, Berlínský technologický institut.
• Matoušek, Jiří (2003), Využití věty Borsuk-Ulam: Přednášky o topologických metodách v kombinatorice a geometrii Springer, ISBN  978-3-540-00362-5.
• Barmak, Jonathan (2011), Algebraická topologie konečných topologických prostorů a aplikacíSpringer, ISBN  978-3-642-22002-9.
• de Longueville, Mark (2011), Kurz topologické kombinatorikySpringer, ISBN  978-1-4419-7909-4.