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

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

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

Передумови

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

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

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

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

В іншому застосуванні гомологічних методів до теорії графів Ловаш довів як неорієнтовану, так і орієнтовану версії гіпотези Франка: якщо задано k-зв'язний граф G, k точок v_1, …, v_k ∈ 'V' (G) і k додатних чисел n_1, n_2, …, n_k, сума яких дорівнює |V (G)|, існує розбиття {V₁, …, V_k} множини V(G), таке, що v_i ∈ 'V'_i, |V_i| = n_i і V_i утворюють зв'язний підграф.

У 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. — 1 квітня. — 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.