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

Топологическая комбинаторика — это молодая область математики, возникшая в последней четверти 20-го века, которая занимается следующими вопросами:

  1. Применение методов топологии к задачам дискретной математики
  2. Топологические обобщения задач дискретной геометрии
  3. Дискретизация топологических понятий

Предпосылки

Комбинаторная топология использует комбинаторные принципы в топологии и в начале 20-го века превратилась в область алгебраической топологии.

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

Задачи и методы

Доказательство Ловаша использует теорему Борсука — Улама и эта теорема удерживает выдающуюся роль в этой новой области. Эта теорема имеет много эквивалентных версий и аналогов и используется для изучения задач справедливого дележа.

В другом приложении гомологических методов к теории графов Ловаш доказал как неориентированную, так и ориентированную версии гипотезы Франка — Если задан k-связный граф G, k точек v1,...,vk∈ V(G) и k положительных чисел n1,n2,...,nk, сумма которых равна |V(G)|, существует разбиение {V1,...,Vk} множества V(G), такое, что vi ∈ Vi, |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. — 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.