Введение
Глава 1 История и формулировки результатов 12
1.1 Основные определения и история задачи 12
1.2 Свойство В и его обобщения 13
1.3 Близкие задачи 17
1.4 Задачи с дополнительными ограничениями на класс гиперграфов 18
1.5 Задачи о раскрасках в несколько цветов 22
1.6 Задачи о подгиперграфах 23
1.6.1 Постановка задачи 23
1.6.2 Первый подход: є-свойство 24
1.6.3 Второй подход: -свойство 26
Глава 2 Доказательство нижней оценки mk(n) 28
2.1 Доказательство теоремы 2 28
2.1.1 Построение рандомизированного алгоритма раскраски . 28
2.1.2 Вероятностные основы алгоритма 29
2.1.3 Вспомогательные утверждения 31
2.1.4 Оценка вероятности события Ае 32
2.1.5 Оценка вероятности события Се 34
2.1.6 Оценка вероятности события BefjV 37
2.1.7 Оценка вероятности события Т 44
2.2 Доказательство теоремы 1 44
Глава 3 Доказательство верхней оценки т^(?г) 47
3.1 Доказательство теоремы 3 47
3.2 Доказательство леммы 3 49
Глава 4 Доказательство оценок rrik,h(n) 54
4.1 Доказательство теоремы 7 54
4.1.1 Предварительные замечания 54
4.1.2 Алгоритм раскраски вершин гиперграфа 55
4.1.3 Оценка вероятности события Ае 57
4.1.4 Оценка вероятности события Се 60
4.1.5 Оценка вероятности события Bef 67
4.1.6 Оценка вероятности события Т 70
4.2 Доказательство теоремы 6 70
4.3 Доказательство теоремы 4 73
4.4 Доказательство теоремы 5 73
Глава 5 Доказательства оценок р(п, 3) 75
5.1 Доказательство теоремы 8 75
5.2 Доказательство теоремы 10 78
5.3 Доказательство теоремы 9 82
Глава 6 є- и /-свойства 84
6.1 Доказательство теоремы 11 84
6.2 Доказательство теоремы 13 85
6.3 Доказательство теоремы 12 86
6.4 Доказательство теоремы 14 88
6.5 Задача о минимальном числе вершин 89
6.6 Доказательство теоремы 15 91
Список литературы 94
