Топологическая комбинаторика

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

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

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

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

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

ЛитератураПравить

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. — 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.