Читать онлайн «Гипотеза Кнезера и топологический метод в комбинаторике»

Летняя школа «Современная математика» Дубна, июль  А. М. Райгородский Гипотеза Кнезера и топологический метод в комбинаторике Москва Издательство МЦНМО  УДК .  ББК .  Р Р Райгородский А. М. Гипотеза Кнезера и топологический метод в комбина- торике. –– М. : МЦНМО, . ––  с. ISBN ---- На примере гипотезы Кнезера автор рассказывает о топологиче- ских методах современной комбинаторики. Книга основана на лекци- ях, которые автор читал в  г. в Дубне на школе «Современная ма- тематика». Книга будет интересна всем, кто интересуется современной комбинаторикой и ее приложениями. ББК .  © Райгородский А. М. , . ISBN ---- © МЦНМО, .  . Введение Комбинаторика –– это один из самых увлекательных разделов со- временной математики. И один из самых бурно развивающихся. Если еще каких-то  лет назад можно было сказать, что комбинаторика –– это набор красивых, но разрозненных утверждений о перечислении объектов того или иного вида, то сейчас комбинаторика –– это пол- ноценная дисциплина, которая постепенно вырабатывает свой соб- ственный язык и систему методов, позволяющих собирать воедино всё то многообразие задач, которые совсем недавно казались никак не связанными между собой. Когда говорят о комбинаторных методах, обычно вспоминают только метод производящих функций, который действительно играет огромную роль при решении перечислительных задач. Однако не менее значимы в комбинаторике и задачи экстремальные, т. е. задачи отыскания наибольших (наименьших) в том или ином смысле систем объектов. И здесь, конечно, производящие функции ни к чему. На смену им приходят инструменты, которые появились буквально в по- следние десятилетия. Среди них вероятностный метод (см. [, ]), активно разрабатываемый с середины ХХ века (во многом благода- ря классику венгерской и мировой комбинаторики Полу Эрдёшу), линейно-алгебраический метод (см. []), возникший и вовсе около тридцати лет назад, и топологический метод –– метод столь же мо- лодой и в то же время столь же перспективный. В этой книге мы хотим рассказать об исторически первой задаче, которая была решена с помощью топологической технологии. Это так называемая гипотеза Кнезера, сформулированная Мартином Кнезе- ром в  году и доказанная Ласло Ловасом в  году. Пафос в том, что постановка задачи исключительно проста и доступна школьни- ку, а решение ее выходит далеко за рамки школьной программы. Тем не менее мы построим книгу так, что практически всё в ней при желании сможет понять заинтересованный старшеклассник. На- ша цель –– на примере одной конкретной задачи продемонстрировать силу и красоту топологического метода: рассуждение, которое мы в конечном счете проведем, –– это поистине жемчужина (ср. []) ком- бинаторики, одно из самых элегантных рассуждений в математике, которые известны автору.