Топологическая комбинаторика — направление в топологии, возникшее в последней четверти XX века, занимающаяся применением методов топологии к задачам дискретной математики , топологическими обобщениями задач дискретной геометрии , а также дискретизацией топологических понятий.

Возникшая в начале XX века комбинаторная топология использует комбинаторные принципы в топологии , к 1940-м годам она оформилась в алгебраическую топологию . В 1978 году ситуация перевернулась — методы алгебраической топологии были использованы для решения задачи в комбинаторике , когда Ласло Ловас доказал гипотезу Кнезера , этот момент и считается началом формирования топологической комбинаторики.

Доказательство Ловаса использует теорему Борсука — Улама , которая играет ключевую роль в топологической комбинаторике в целом, имеет много эквивалентных версий и аналогов, и используется для изучения задач справедливого дележа . В другом приложении гомологических методов к теории графов Ловас доказал как неориентированную, так и ориентированную версии гипотезы — если задан ${\displaystyle k}$ -связный граф ${\displaystyle G}$ , ${\displaystyle k}$ точек ${\displaystyle v_{1},\dots ,v_{k}\in V(G)}$ , ${\displaystyle k}$ положительных чисел ${\displaystyle n_{1},\dots n_{k}}$ , сумма которых равна ${\displaystyle \left|V(G)\right|}$ , существует разбиение ${\displaystyle \{V_{1},\dots V_{k}\}}$ множества ${\displaystyle V(G)}$ такое, что ${\displaystyle v_{i}\in V_{i}}$ , ${\displaystyle \left|V_{i}\right|=n_{i}}$ и ${\displaystyle V_{i}}$ образуют связный подграф.

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

Кроме того, методы из дифференциальной топологии получили комбинаторный аналог в .

Литература

• Mark de Longueville. 25 years proof of the Kneser conjecture - The advent of topological combinatorics // . — Southampton, Hampshire: European Mathematical Society, 2004. — С. 16–19.

Литература для дальнейшего чтения

• Anders Björner. Topological Methods // / Ronald L. Graham, Martin Grötschel, László Lovász. — The MIT press, 1995. — Т. 2. — ISBN 978-0-262-07171-0 .
• Dmitry Kozlov. . — 2005. — arXiv : .
• Dmitry Kozlov. Combinatorial Algebraic Topology. — Springer, 2007. — ISBN 978-3-540-71961-8 .
• Carsten Lange. . — , 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 .