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

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

История

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

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

В другом применении гомологических методов к теории графов Ловас доказал как неориентированную, так и ориентированную версии гипотезы Андраша Франка : для заданного k -связного графа G , k точек и k положительных целых чисел , которые в сумме дают , существует разбиение такое , что , и охватывает связный подграф. ${\displaystyle v_{1},\ldots ,v_{k}\in V(G)}$ ${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$ ${\displaystyle |V(G)|}$ ${\displaystyle \{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle V(G)}$ ${\displaystyle v_{i}\in V_{i}}$ ${\displaystyle |V_{i}|=n_{i}}$ ${\displaystyle V_{i}}$

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

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

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

• Лемма Шпернера
• Дискретное внешнее исчисление
• Топологическая теория графов
• Комбинаторная топология
• Конечное топологическое пространство

Ссылки

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

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

• Бьорнер, Андерс (1995), «Топологические методы», Грэм, Рональд Л .; Гретшель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике (PDF) , том. 2, Пресса Массачусетского технологического института, ISBN 978-0-262-07171-0.
• Козлов, Дмитрий (2005), Тенденции в топологической комбинаторике , arXiv : math.AT/0507390 , Bibcode :2005math......7390K.
• Козлов, Дмитрий (2007), Комбинаторная алгебраическая топология , Springer, ISBN 978-3-540-71961-8.
• Ланге, Карстен (2005), Комбинаторные кривизны, групповые действия и раскраски: аспекты топологической комбинаторики (PDF) , докторская диссертация, Берлинский технический университет.
• Матоушек, Йиржи (2003), Использование теоремы Борсука-Улама: Лекции по топологическим методам в комбинаторике и геометрии , Springer, ISBN 978-3-540-00362-5.
• Бармак, Джонатан (2011), Алгебраическая топология конечных топологических пространств и приложения , Springer, ISBN 978-3-642-22002-9.
• де Лонгвиль, Марк (2011), Курс топологической комбинаторики , Springer, ISBN 978-1-4419-7909-4.