Топологическая комбинаторика
Топологическая комбинаторика — направление в топологии, возникшее в последней четверти XX века, занимающаяся применением методов топологии к задачам дискретной математики, топологическими обобщениями задач дискретной геометрии, а также дискретизацией топологических понятий.
Возникшая в начале XX века комбинаторная топология использует комбинаторные принципы в топологии, к 1940-м годам она оформилась в алгебраическую топологию. В 1978 году ситуация перевернулась — методы алгебраической топологии были использованы для решения задачи в комбинаторике, когда Ласло Ловас доказал гипотезу Кнезера, этот момент и считается началом формирования топологической комбинаторики.
Доказательство Ловаса использует теорему Борсука — Улама, которая играет ключевую роль в топологической комбинаторике в целом, имеет много эквивалентных версий и аналогов, и используется для изучения задач справедливого дележа. В другом приложении гомологических методов к теории графов Ловас доказал как неориентированную, так и ориентированную версии гипотезы Шаблон:Не переведено 5 — если задан -связный граф , точек , положительных чисел , сумма которых равна , существует разбиение множества такое, что , и образуют связный подграф.
В 1987 году Нога Алон решил задачу дележа ожерелья используя теорему Борсука — Улама. Теорема использовалась также для изучения вычислительной сложности линейных алгоритмов дерева решений и гипотезы Аандераа — Карпа — Розенберга. Другие области изучении — Шаблон:Не переведено 5 и порядков Брюа.
Кроме того, методы из дифференциальной топологии получили комбинаторный аналог в Шаблон:Не переведено 5.