Топологічна комбінаторика — це молода галузь математики, що виникла в останній чверті XX століття, яка розглядає такі питання:
Застосування методів топології до задач дискретної математики Топологічні узагальнення задач дискретної геометрії Дискретизація топологічних понять.
Передумови Комбінаторна топологія використовує комбінаторні принципи в топології і на початку XX століття це привело до виникнення алгебричної топології.
У 1978 ситуація змінилася — методи алгебричної топології застосували для розв'язування задачі в комбінаториці, коли Ласло Ловас довів гіпотезу Кнезера і почалося нове вивчення топологічної комбінаторики.
Завдання і методи Доведення Ловаса використовує теорему Борсука — Уляма і ця теорема утримує видатну роль у цій новій галузі. Ця теорема має багато еквівалентних версій і аналогів і використовується для вивчення задач про справедливий поділ.
В іншому застосуванні гомологічних методів до теорії графів Ловаш довів як неорієнтовану, так і орієнтовану версії гіпотези : якщо задано k-зв'язний граф G, k точок v1, …, vk ∈ 'V' (G) і k додатних чисел n1, n2, …, nk, сума яких дорівнює |V (G)|, існує розбиття {V1, …, Vk} множини V(G), таке, що vi ∈ 'V'i, |Vi| = ni і Vi утворюють зв'язний підграф.
У 1987 році Нога Алон розв'язав задачу про розрізання намиста, використовуючи теорему Борсука — Уляма. Теорему використано також для вивчення обчислювальної складності лінійних алгоритмів дерева рішень і гіпотези Аандераа — Карпа — Розенберга. Інші галузі вивчення — і порядків Брухата .
Крім того, методи з диференціальної топології тепер мають комбінаторний аналог у .
Див. також Лема Шпернера Топологічна теорія графів Комбінаторна топологія Скінченний топологічний простір
Примітки
Література