Топологічна комбінаторика

Топологічна комбінаторика — це молода галузь математики, що виникла в останній чверті XX століття, яка розглядає такі питання:

  1. Застосування методів топології до задач дискретної математики
  2. Топологічні узагальнення задач дискретної геометрії
  3. Дискретизація топологічних понять.

Передумови

Комбінаторна топологія використовує комбінаторні принципи в топології і на початку XX століття це привело до виникнення алгебричної топології.

У 1978 ситуація змінилася — методи алгебричної топології застосували для розв'язування задачі в комбінаториці, коли Ласло Ловас довів гіпотезу Кнезера і почалося нове вивчення топологічної комбінаторики.

Завдання і методи

Доведення Ловаса використовує теорему Борсука — Уляма і ця теорема утримує видатну роль у цій новій галузі. Ця теорема має багато еквівалентних версій і аналогів і використовується для вивчення задач про справедливий поділ.

В іншому застосуванні гомологічних методів до теорії графів Ловаш довів як неорієнтовану, так і орієнтовану версії гіпотези Франка: якщо задано k-зв'язний граф G, k точок v1, …, vk ∈ 'V' (G) і k додатних чисел n1, n2, …, nk, сума яких дорівнює |V (G)|, існує розбиття {V1, …, Vk} множини V(G), таке, що vi ∈ 'V'i, |Vi| = ni і Vi утворюють зв'язний підграф.

У 1987 році Нога Алон розв'язав задачу про розрізання намиста, використовуючи теорему Борсука — Уляма. Теорему використано також для вивчення обчислювальної складності лінійних алгоритмів дерева рішень і гіпотези Аандераа — Карпа — Розенберга. Інші галузі вивчення — топології частково упорядкованих множин і порядків Брухата .

Крім того, методи з диференціальної топології тепер мають комбінаторний аналог у дискретній теорії Морса .

Див. також

Примітки

    Література
    • Mark de Longueville. 25 years proof of the Kneser conjecture - The advent of topological combinatorics // EMS Newsletter. — Southampton, Hampshire : European Mathematical Society, 2004. — С. 16–19.
    • Anders Björner. Topological Methods // Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. — The MIT press, 1995. — Т. 2. — ISBN 978-0-262-07171-0.
    • Dmitry Kozlov. Trends in topological combinatorics. — 2005. — 17 грудня. — arXiv:math.AT/0507390.
    • Dmitry Kozlov. Combinatorial Algebraic Topology. — Springer, 2007. — ISBN 978-3-540-71961-8.
    • Carsten Lange. Combinatorial Curvatures, Group Actions, and Colourings: Aspects of Topological Combinatorics. — Berlin Institute of Technology, 2005. — (Ph.D. thesis)
    • Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. — Springer, 2003. — ISBN 978-3-540-00362-5.
    • Jonathan Barmak. Algebraic Topology of Finite Topological Spaces and Applications. — Springer, 2011. — ISBN 978-3-642-22002-9.
    • Mark de Longueville. A Course in Topological Combinatorics. — Springer, 2011. — ISBN 978-1-4419-7909-4.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.