Читать онлайн «Линейно-алгебраический метод в комбинаторике»

А. М. Райгородский Линейно-алгебраический метод в комбинаторике Москва Издательство МЦМНО 2007 УДК 519. 1 ББК 22. 15 Р18 Райгородский А. М. Р18 Линейно-алгебраический метод в комбинаторике. — М. : МЦНМО, 2007. — 136 с. ISBN 987-5-94057-313-5 Современная комбинаторика — это весьма многогранная и актив- но развивающаяся область математики. В XX веке был разработан ряд мощных методов, позволяющих решать многие трудные задачи комбинаторики. Среди этих методов особое место занимает линейно- алгебраический метод. С его помощью удалось добиться прорыва в таких классических проблемах, как, например, проблема Борсука о разбиении множеств на части меньшего диаметра. В книге излага- ются основы метода и описываются наиболее яркие примеры его при- менения. Для понимания материала достаточно знания элементарных понятий линейной алгебры и математического анализа. Книга будет полезна студентам и аспирантам, интересующимся комбинаторным анализом, а также специалистам в области дискретной математики. ББК 22. 15 Райгородский Андрей Михайлович ЛИНЕЙНО-АЛГЕБРАИЧЕСКИЙ МЕТОД В КОМБИНАТОРИКЕ c Райгородский А. М. , 2007, ISBN 987-5-94057-313-5 c МЦНМО, 2007. Оглавление 1. Введение 5 2. Задачи о пересечениях конечных множеств 8 2. 1. Немного истории и формулировка теоремы Франкла— Уилсона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2. 2. Доказательство теоремы Франкла—Уилсона . . . . . . . . 10 2. 3. Точность теоремы Франкла—Уилсона и ее неожиданность 15 2. 4. Вокруг теоремы Франкла—Уилсона . . . . . . . . . . . . . 18 3. Задачи о скалярных произведениях векторов 26 3. 1. Постановка одной из задач и формулировка одного из результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. Доказательство теоремы 9 . . . . . . . . . . . . . . . . . . . 29 3. 3. Смысл оценки из теоремы 9 . . . . . . . . . . . . . . . . . . 32 3. 4. Точна ли теорема 9? . . . . . . . . . . . . . . . . . . . . . . 37 3. 5. Вокруг теоремы 9 . . . . . . . . . . . . . . . . . . . . . . . . 48 4. Применение полученных результатов в комбинаторной геометрии 56 4. 1. Постановки основных задач . . . . . . . . . . . . . . . . . . 56 4. 2. Задача Нельсона—Эрдёша—Хадвигера . . . . . . . . . . . . 60 4. 3. Задача Борсука . . . . . . . . . . . . . . . . . . . . . . . . . 69 4. 4. О числах Борсука и Нельсона—Эрдёша—Хадвигера . . . . 76 4. 5.