Вероятностный метод WileyInterscience Series in Discrete Mathematics and Optimization The Probabilistic Method Second Edition Noga Alon Joel H. Spencer New York Chichester Weinheim Brisbane A WileyInterscience Publication JOHN WILEY & SONS, Inc. <...> Упражнения Вероятностный взгляд: Большой обхват и большое хроматическое число Глава 4. <...> Случайные ограничения и схемы ограниченной глубины 11.3. <...> Нога Алон—член Национальной Академии наук Израиля, автор более чем трехсот работ по комбинаторике и теории сложности, обладатель премий Эрд¨ ера (1991), Пойа (2000), Бруно (2001), Ландау (2005), Г¨ еша (1989), Фейеделя (2005). <...> Применение вероятностного метода в дискретной математике было инициировано Полом Эрд¨ ешем, который сделал для его развития больше, чем кто-либо другой. <...> К первой относится изучение определенных классов комбинаторных объектов, таких как случайные графы или случайные матрицы. <...> Первая часть книги содержит описание методов, применяемых в вероятностных доказательствах, включая традиционную технику, использующую математическое ожидание и дисперсию, а также более современные методы, связанные с применением мартингалов и корреляционных неравенств. <...> Основная идея вероятностного метода может быть описана следующим образом: чтобы доказать существование комбинаторной структуры с определенными свойствами, мы конструируем соответствующее вероятностное пространство и показываем, что случайно выбранный элемент этого пространства обладает данными свойствами с положительной вероятностью. <...> Этот метод был предложен Полом Эрд¨ в его развитие столь значительный вклад, что представляется справедливым назвать его «методом Эрд¨ числе глубоких результатов, касающихся вероятностного подхода, но также во многих интересных проблемах и гипотезах, которые в значительной степени стимулировали исследования в этой области. <...> Грубо говоря, этот метод работает следующим образом: пытаясь доказать, что структура с некоторыми искомыми свойствами существует, мы определяем подходящее вероятностное пространство структур <...>
Вероятностный_метод.pdf
Н. Алон, Дж. Спенсер
Вероятностный
метод
Перевод 2го английского издания
А. А. Сапоженко
под редакцией
4е издание, электронное
Допущено
по прикладной математике и информатике УМО
учебнометодическим советом
по классическому университетскому образованию
в качестве учебного пособия для студентов
высших учебных заведений, обучающихся
по специальности и направлению
«Прикладная математика и информатика»
и по направлению «Информационные технологии»
Москва
Лаборатория знаний
2020
Стр.4
УДК 519.1
ББК 22.176
А45
Алон Н.
А45 Вероятностный метод : учебное пособие / Н. Алон, Дж. Спенсер
; пер. 2-го англ. изд. — 4-е изд., электрон. — М. : Лаборатория
знаний, 2020. — 323 с. — Систем. требования: Adobe Reader XI ;
экран 10".— Загл. с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-672-4
Одна из самых известных зарубежных книг в области применения
вероятностных методов в комбинаторике. В книге содержатся основные элементы
методологии. Строгие обоснования и доказательства сопровождаются
ясными и неформальными обсуждениями задач, методов и их приложений.
Каждый метод иллюстрируется целым рядом точно подобранных примеров.
Для специалистов в области дискретной математики и теории случайных
графов, студентов, аспирантов и преподавателей соответствующих
дисциплин.
УДК 519.1
ББК 22.176
Деривативное издание на основе печатного аналога: Вероятностный
метод : учебное пособие / Н. Алон, Дж. Спенсер ; пер. 2-го англ. изд. —
М. : БИНОМ. Лаборатория знаний, 2007. — 320 с. : ил.
ISBN 978-5-94774-556-6.
Первый тираж книги выпущен при финансовой поддержке РФФИ
в рамках издательского проекта № 05-01-14048
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных
техническими средствами защиты авторских прав, правообладатель вправе требовать
от нарушителя возмещения убытков или выплаты компенсации
Copyright ○c 2000 by John Wiley & Sons, Inc. All Rights
ISBN 978-5-00101-672-4
○c Перевод, оформление, Лаборатория знаний, 2015
Reserved. This EBook is published under license
with the original publisher
John Wiley & Sons, Ltd.
Стр.5
Оглавление
Предисловие редактора перевода
Предисловие авторов к русскому изданию
Предисловие
Благодарности
Часть I. МЕТОДЫ
Глава 1. Основы
9
11
13
15
1.1. Вероятностный метод
1.2. Теория графов
1.3. Комбинаторика
Вероятностный взгляд: Теорема Эрдёша—Ко—Радо
Глава 2. Линейность математического ожидания
1.4. Комбинаторная теория чисел
1.5. Пары с пустым пересечением
1.6. Упражнения
2.1. Основы
18
18
20
24
27
28
29
31
2.2. Разбиение графов
Вероятностный взгляд: Теорема Брегмана
2.3. Два быстрых результата
2.4. Балансировка векторов
2.5. Разбалансировка лампочек
2.6. Без подбрасывания монет
2.7. Упражнения
Глава 3. Малые вариации
3.1. Числа Рамсея
3.2. Независимые множества
3.3. Комбинаторная геометрия
3.4. Упаковка
3.5. Перекраска
Вероятностный взгляд: Большой обхват и большое хроматическое
число
3.6. Непрерывное время
3.7. Упражнения
Глава 4. Второймомент
4.1. Основы
4.2. Теория чисел
32
32
33
35
36
38
39
40
42
44
44
46
47
48
49
53
58
59
60
60
61
Стр.6
6 ОГЛАВЛЕНИЕ
4.3. Дополнительные теоретические сведения
4.4. Случайные графы
Вероятностный взгляд: Гамильтоновы пути
4.5. Максимальный размер клики
4.6. Различные суммы
4.7. Подход Рёдля
4.8. Упражнения
Глава 5. Локальная лемма
5.1. Лемма
5.2. Свойство 𝐵 и разноцветные множества действительных
чисел
Вероятностный взгляд: Ориентированные циклы
Глава 6. Корреляционные неравенства
5.3. Нижние оценки для чисел Рамсея
5.4. Геометрический результат
5.5. Линейная древесность графов
5.6. Латинские трансверсали
5.7. Алгоритмический аспект
5.8. Упражнения
6.1. Теорема о четырех функциях Альсведе и Дайкина
6.2. FKG-неравенство
6.3. Монотонные свойства
Вероятностный взгляд: Теорема Турана
Глава 7. Мартингалы и плотная концентрация
7.1. Определения
7.2. Большие уклонения
7.3. Хроматическое число
7.4. Два обобщения
7.5. Четыре примера
64
66
70
71
73
78
80
83
83
86
87
89
90
95
96
100
101
102
103
106
107
112
113
6.4. Линейные расширения частично упорядоченных множеств 109
6.5. Упражнения
7.6. Неравенство Талаграна
Вероятностный взгляд: Теорема Вейерштрасса о приближении
7.7. Приложения неравенства Талаграна
7.8. Полиномиальная концентрация Кима—Ву
7.9. Упражнения
Глава 8. Парадигма Пуассона
8.1. Неравенства Янсона
8.2. Доказательства
8.3. Решето Бруна
8.4. Большие уклонения
8.5. Оценка числа расширений
8.6. Число представлений
115
115
117
118
121
125
127
130
133
135
136
137
137
139
142
145
146
148
Стр.7
ОГЛАВЛЕНИЕ 7
Вероятностный взгляд: Локальная раскраска
8.7. Дальнейшие обобщения
8.8. Упражнения
Глава 9. Псевдослучайность
Вероятностный взгляд: Случайные блуждания
9.1. Турниры квадратичных вычетов
9.2. Собственные значения и расширители
9.3. Квазислучайные графы
9.4. Упражнения
Часть II. Приложения
Глава 10. Случайные графы
10.1. Подграфы
10.2. Размер максимальной клики
10.3. Хроматическое число
10.4. Ветвящиеся процессы
10.5. Гигантская компонента
10.6. Фазовый переход изнутри
10.7. Законы «нуля или единицы»
10.8. Упражнения
Глава 11. Сложность схем
151
153
154
156
157
160
167
173
174
Вероятностный взгляд: Число подграфов
178
179
181
183
184
188
192
195
204
205
11.1. Предварительные замечания
11.2. Случайные ограничения и схемы ограниченной глубины
11.3. Еще о схемах ограниченной глубины
11.4. Монотонные схемы
11.5. Формулы
11.6. Упражнения
Глава 12. Разброс
12.1. Основы
Вероятностный взгляд: Максимальные антицепи
12.2. Достаточность шести стандартных отклонений
12.3. Линейный и наследственный разброс
12.4. Нижние оценки
12.5. Теорема Бека—Фиала
12.6. Упражнения
Глава 13. Геометрия
Вероятностный взгляд: Несбалансированные матрицы
207
207
209
213
216
219
221
222
223
223
224
228
231
233
235
237
13.3. Геометрическая реализация ±1-матриц
238
240
13.1. Наибольший угол между точками в евклидовом пространстве 239
13.2. Пустые треугольники, определяемые точками плоскости
242
Стр.8
8 ОГЛАВЛЕНИЕ
13.4. 𝜀-сети и VC-размерности ранжированных пространств
Вероятностный взгляд: Эффективная упаковка
Глава 14. Коды, игры и энтропия
14.1. Коды
14.2. Игра лжеца
14.3. Игра «постоянная должность»
14.4. Игра «балансировка векторов»
14.5. Неадаптивные алгоритмы
14.6. Энтропия
14.7. Упражнения
Вероятностный взгляд: Экстремальные графы
Глава 15. Дерандомизация
15.3. Упражнения
15.1. Метод условных вероятностей
15.2. 𝑑-независимые случайные величины в пространствах малого
размера
Вероятностный взгляд: Число пересечений, инцидентности, суммы
и произведения
Приложение A. Оценки для больших уклонений
A.1. Оценки для больших уклонений
A.2. Упражнения
Приложение B. Пол Эрдёш
B.1. Труды
B.2. Гипотезы
B.3. Об Эрдёше
Литература
Предметный указатель
Именной указатель
B.4. Дядюшка Пол
13.5. Двойственная функция расщепления и разброс
13.6. Упражнения
244
250
253
254
256
256
259
261
263
265
266
272
273
275
275
280
284
285
287
Вероятностный взгляд: Графы, свободные от треугольников,
содержат большие независимые множества
287
295
296
298
298
300
301
302
305
314
319
Стр.9