Топологическая комбинаторика — это молодая область математики, возникшая в последней четверти 20-го века, которая занимается следующими вопросами:
Предпосылки
Комбинаторная топология использует комбинаторные принципы в топологии и в начале 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 Нога Алон решил задачу дележа ожерелья, используя теорему Борсука — Улама. Теорема использовалась также для изучения вычислительной сложности линейных алгоритмов дерева решений и гипотезы Аандераа — Карпа — Розенберга. Другие области изучении — топологии частично упорядоченных множеств и порядков Брухата.
Кроме того, методы из дифференциальной топологии теперь имеют комбинаторный аналог в дискретной теории Морса.