Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/matstat/vermet-rayg.doc Дата изменения: Mon Nov 10 08:55:21 2008 Дата индексирования: Sun Apr 10 03:28:16 2016 Кодировка: koi8-r

ВЕРОЯТНОСТНЫЕ МЕТОДЫ В КОМБИНАТОРИКЕ
асс. А.М. Райгородский
1 год, 2-5 курс
Первый семестр. Методы.
0. Введение: несколько исторических замечаний; общая идея вероятностного
метода, основные примеры:
. 0.1. Числа Рамсея.
. 0.2. Случайные турниры, доминирующие множества в графах.
. 0.3. "Свойство B" гиперграфа (оценка Эрдеша числа [pic]).
. 0.4. Множества, свободные от сумм.
0'. Дополнение: несколько задач экстремальной теории гиперграфов (теорема
Эрдеша-Ко-Радо, теорема Франкла-Вилсона, теорема Алсведе-Хачатряна).
1. Методы, основанные на линейности математического ожидания. Примеры:
. 1.1. Нахождение двудольного подграфа с достаточно большим числом
ребер.
. 1.2. Балансировка векторов в пространстве.
2. Метод альтернирования. Примеры:
. 2.1. Числа Рамсея.
. 2.2. Независимые множества вершин в графе. Теорема Турана.
. 2.3. Минимальная площадь треугольника с вершинами в конечном
подмножестве квадрата. Теорема Комлоша-Пинца-Семереди.
. 2.4. Упаковки множеств в пространстве. Теоремы о плотности. Теорема
Минковского о выпуклом теле. Теорема Минковского-Главки.
. 2.5. "Свойство В" гиперграфа (оценки Бека и Радхакришнана-
Сринивазана числа [pic]). Рандомизированные алгоритмы.
3. Метод второго момента. Неравенство Чебышева. Примеры:
. 3.1. Теорема Харди-Рамануджана и Турана о распределении числа
простых делителей. Нормальное распределение.
. 3.2.Свойства случайных графов. Пороговые функции.
. 3.3.Число клик в графе.
. 3.4.Множества с различными суммами.
. 3.5.Задача о покрытии. Теоремы Рёдла, Эрдеша-Турана, Райгородского.
4. Локальная лемма Ловаса. Примеры применения:
. 4.1. "Свойство В" гиперграфов (случай регулярного гиперграфа).
Раскраска вещественной прямой в k цветов.
. 4.2. Числа Рамсея.
. 4.3. Кратные покрытия трехмерного пространства. Теорема Мани-
Левицка-Паха о разложении покрытий.
. 4.4. Покрытия регулярных графов линейными лесами.
. 4.5. Латинские трансверсали. Теорема Эрдеша-Спенсера.
5. Мартингалы и плотная концентрация.
. 5.1. Случайные графы. Мартингалы реберного и вершинного типов.
. 5.2. Неравенство Азумы. Концентрация около среднего значения.
Примеры применения:
5.2.1. Теоремы Шамира-Спенсера и Боллобаша о концентрации
хроматического числа случайного графа.
5.2.2. Распределение клик в случайном графе.
. 5.3. Неравенство Талаграна. Концентрация около медианы. Примеры
применения:
5.3.1. Длина наибольшей возрастающей подпоследовательности
случайных чисел на отрезке.
5.3.2. Распределение клик в случайном графе.
. 5.4. Неравенство Кима-Ву. Полиномиальная концентрация.
6. "Близость" к распределению Пуассона.
. 6.1. Неравенства Янсона. Примеры применения.
. 6.2. Решето Бруна. Примеры применения.
Второй семестр. Задачи.
1. Случайные графы.
. 1.1. Пороговые функции для свойств случайных графов.
. 1.2. Число клик в случайном графе.
. 1.3. Хроматическое число случайного графа. Теорема Боллобаша.
. 1.4. Фазовый переход ("двойной скачок") в случайном графе.
1.4.1. Ветвящиеся процессы. Принцип двойственности.
1.4.2. Гигантская компонента случайного графа. Дискретный принцип
двойственности.
1.4.3. Рост максимальных компонент случайного графа "внутри"
фазового перехода.
. 1.5. Законы нуля и единицы для свойств случайных графов, выражаемых
на языке первого порядка.
1.5.1. Теорема Глебского-Когана-Таланова.
1.5.2. Теорема Шелаха-Спенсера.
. 1.6. Графы с большим числом попарно неизоморфных подграфов.
2. Несколько задач комбинаторной геометрии.
. 2.1. Величины углов между векторами в Rd. Гипотеза Данцера-
Грюнбаума. Контрпример Эрдеша-Фюреди.
. 2.2. Пустые треугольники, задаваемые n точками на плоскости.
Теоремы Качальского-Меира и Барани-Фюреди.
. 2.3. Задача Патури-Саймона о реализации булевых матриц в
пространстве. Теорема Алона-Франкла-Рёдла.
. 2.4. Треугольники, задаваемые n точками на плоскости, и теорема
Вапника-Червоненкиса.
. 2.5. Проблема Борсука. Проблема освещения. Теоремы Шрамма и
Бургейна-Линденштрауса. Теорема Райгородского о (0,1)-
многогранниках и кросс-политопах.
3. Двухцветные раскраски подмножеств конечного множества и отклонения от
"равномерной" раскраски.
. 3.1. Теорема Спенсера о верхней оценке отклонения.
. 3.2. Линейное и наследственное отклонения. Верхние оценки.
. 3.3. Матрицы Адамара и нижние оценки отклонения.
. 3.4. Теорема Бека - Фиалы о верхней оценке отклонения в специальном
случае.
4. Коды, игры и энтропия.
. 4.1. Коды. Понятие энтропии. Теорема Шеннона.
. 4.2. Игра лжеца.
. 4.3. Игра в балансировку векторов.
. 4.4. Двоичная энтропия случайной величины и ее свойства. Некоторые
комбинаторные следствия.
Замечание. Все необходимые сведения из теории вероятностей вводятся в
процессе изложения.

Литература
1. Эрдеш П. и Спенсер Дж. Вероятностные методы в комбинаторике. М., Мир,
1976.
2. Alon N., Spencer J. The probabilistic method. New York, Wiley, Second
Edition, 2001.
3. Харари Ф. Теория графов М., Мир, 1973.
4. Bollobas B. Random graphs. Cambridge University Press, Second Edition,
2001.
5. Райгородский А.М. Проблема Борсука и хроматические числа некоторых
метрических пространств.// УМН 56 (2001), ? 1, с. 107-146.