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

Математическая дисциплина топологические комбинаторики является применение топологических и алгебро-топологических методов к решению задач в комбинаторике .

История

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

В 1978 году ситуация изменилась - методы алгебраической топологии использовались для решения задачи комбинаторики, - когда Ласло Ловас доказал гипотезу Кнезера , положив начало новой области топологической комбинаторики . В доказательстве Ловаса использовалась теорема Борсука – Улама, и эта теорема сохраняет важную роль в этой новой области. Эта теорема имеет много эквивалентных версий и аналогов и использовалась при изучении проблем справедливого деления .

В другом применении гомологических методов в теорию графов , Lovász доказал как неориентированные и направленные версии гипотезы о Андраш Frank : Учитывая к -связному графу G , K точки и K положительных целых чисел , что сумма до , существует разбиение на такое, что , и охватывает связанный подграф.

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

Кроме того, методы дифференциальной топологии теперь имеют комбинаторный аналог в дискретной теории Морса .

Смотрите также

Рекомендации

  • де Лонгвиль, Марк (2004), «25 лет доказательства гипотезы Кнезера - появление топологической комбинаторики» (PDF) , Информационный бюллетень EMS , Саутгемптон, Гемпшир: Европейское математическое общество, стр. 16–19 , извлечено 29 июля 2008 г..

дальнейшее чтение