Вероятностные методы решения экстремальных задач о раскрасках равномерных гиперграфов

• Автор: Шабанов, Дмитрий Александрович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 97 с.

Общая характеристика работы

Глава 1 История и формулировки результатов

§1.1 Основные определения и история задачи

§1.2 Свойство В и его обобщения

§1.3 Близкие задачи

§1.4 Задачи с дополнительными ограничениями на класс гиперграфов

§1.5 Задачи о раскрасках в несколько цветов

§1.6 Задачи о подгиперграфах

1.6.1 Постановка задачи

1.6.2 Первый подход: е-свойство

1.6.3 Второй подход: 7-свойство

Глава 2 Доказательство нижней оценки гщ(п)
§2.1 Доказательство теоремы
2.1.1 Построение рандомизированного алгоритма раскраски
2.1.2 Вероятностные основы алгоритма
2.1.3 Вспомогательные утверждения
2.1.4 Оценка вероятности события Ае
2.1.5 Оценка вероятности события Се
2.1.6 Оценка вероятности события
2.1.7 Оценка вероятности события Т
§2.2 Доказательство теоремы
Глава 3 Доказательство верхней оценки тДп)
§3.1 Доказательство теоремы
§3.2 Доказательство леммы
Глава 4 Доказательство оценок
§4.1 Доказательство теоремы

4.1.1 Предварительные замечания
4.1.2 Алгоритм раскраски вершин гиперграфа
4.1.3 Оценка вероятности события Ае
4.1.4 Оценка вероятности события Се
4.1.5 Оценка вероятности события Ве]
4.1.6 Оценка вероятности события Т
§4.2 Доказательство теоремы
§4.3 Доказательство теоремы
§4.4 Доказательство теоремы
Глава 5 Доказательства оценок р(п, 3)
§5.1 Доказательство теоремы
§5.2 Доказательство теоремы
§5.3 Доказательство теоремы
Глава 6 е- и /-свойства
§6.1 Доказательство теоремы
§6.2 Доказательство теоремы
§6.3 Доказательство теоремы
§6.4 Доказательство теоремы
§6.5 Задача о минимальном числе вершин
§6.6 Доказательство теоремы
Список литературы

Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике. Ранние результаты такого сорта основывались на сочетании комбинаторных соображений с элементарной вероятностной техникой, однако развитие метода в последние годы потребовало применения все более изощренных инструментов теории вероятностей. Еще одной причиной столь интенсивного развития вероятностного метода стало осознание важности роли, которую играет этот метод в теории компьютерных вычислений, являющейся источником многих задач комбинаторики. В связи с этим, интересен также алгоритмический подход к изучению вероятностного метода в комбинаторике.
Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П. Эрдеш, который впоследствии внес в развитие метода очень значительный вклад. Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области. Отныне результаты, получаемые вероятностным методом, можно разделить условно на две группы. К первой группе относятся те результаты, которые связаны с изучением определенных классов комбинаторных объектов, таких, как случайные графы или случайные матрицы (см. [13], [30], [31], [32], [33] и др.). Эти результаты являются по существу теоретико-вероятностными, хотя большинство из них мотивировано задачами комбинаторики. Вторая группа состоит из тех фактов, которые формулируются в терминах существования комбинаторных структур, обладающих рядом предписанных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью. Как правило, главная тонкость здесь в выборе подходящей вероятностной меры. Доказа-

Тогда

'Vn
Следовательно, отношение Dab и 5 оценивается снизу следующим образом: Dab ^ пП{п-к + 1) (л 2n^n 1 2n
-ГГ > 2 . 1 — > —в -а»— = 7s(П
5 п! v / 2е пг 2е
Заметим, что 7s(n) —ь +оо при п —> оо.
Второй случай: г? — п>а>|^1 + v.
Для удобства обозначим = ip = ip(n) и положим | (1 + ф) — а
а(п). Оценим Dab снизу лишь одной из двух сумм:
j=0 j=о
Со слагаемыми СО поступим так же, как и в первом случае:
(ш-i > (а-п + зТ-‘ = /J _ TziV^ > -^Ii-e-ёгё >
- (п-Л! (n-j)'V « У “(«-Л!
an~i an~j *v an~j
р a—n+j р г;—2n+2j р u-2n
~(n~j) - (n-j) - (п-j)!
Последние три неравенства в этой цепочке легко получаются из условия а >

и тождества v — Стало быть, Dab ограничено снизу выражением:
п ^ fsr °ПЧ ^ ( лп-к (хГ
Dab > / 7 77 е ”~2п -> (аг;) I
В первом случае мы показали, что

(э v—2n л
;=о (п-^!
Тогда отношение Dab и S оценивается следующим образом:
^ lfo„.n-k (VYk (л I ,nn-k -кЪЦ

> |(2аТ~к (|) '* «-Л = 1<Г^ (1 + Д
1 iv (n-fcp1 , , о
> _g v~2n g 1+9 g 2 = 7g(n).

M'S