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

редактировать

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

Содержание

1 История
2 См. Также
3 Ссылки
4 Дополнительная литература

История

В дисциплине комбинаторная топология используются комбинаторные концепции в топологии, а в начале 20 века это превратилось в область алгебраической топологии.

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

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

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

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

См. Также

Ссылки

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

Дополнительная литература

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