Вероятностный метод

Вероятностный 
метод

WileyInterscience Series in Discrete Mathematics and Optimization
The
Probabilistic
Method
Second Edition 
Noga Alon
Joel H. Spencer
A WileyInterscience Publication
JOHN WILEY & SONS, Inc.
New York
Chichester
Weinheim
Brisbane
Singapore
Toronto

Н. Алон, Дж. Спенсер 
Вероятностный
м е т о д
Перевод 2го английского издания
под редакцией 
А. А. Сапоженко
5е издание, электронное
Д о п у щ е н о
по прикладной математике и информатике УМО 
учебнометодическим советом
по классическому университетскому образованию 
в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся 
по специальности и направлению 
«Прикладная математика и информатика» 
и по направлению «Информационные технологии»
Москва
Лаборатория знаний
2024

УДК 519.1
ББК 22.176
А45
Алон Н.
А45
Вероятностный метод : учебное пособие / Н. Алон, Дж. Спенсер ; пер. 2-го англ. изд. — 5-е изд., электрон. — М. : Лаборатория
знаний, 2024. — 323 с. — Систем. требования: Adobe Reader XI ;
экран 10". — Загл. с титул. экрана. — Текст : электронный.
ISBN 978-5-93208-688-9
Одна из самых известных зарубежных книг в области применения
вероятностных методов в комбинаторике. В книге содержатся основные элементы методологии. Строгие обоснования и доказательства сопровождаются
ясными и неформальными обсуждениями задач, методов и их приложений.
Каждый метод иллюстрируется целым рядом точно подобранных примеров.
Для специалистов в области дискретной математики и теории случайных графов, студентов, аспирантов и преподавателей соответствующих
дисциплин.
УДК 519.1
ББК 22.176
Деривативное издание на основе печатного аналога: Вероятностный метод : учебное пособие / Н. Алон, Дж. Спенсер ; пер. 2-го англ. изд. —
М. : БИНОМ. Лаборатория знаний, 2007. — 320 с. : ил.
ISBN 978-5-94774-556-6
Первый тираж книги выпущен при финансовой поддержке РФФИ
в рамках издательского проекта №05-01-14048
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных
техническими средствами защиты авторских прав, правообладатель вправе требовать
от нарушителя возмещения убытков или выплаты компенсации
©
Copyright
2000 by John Wiley & Sons, Inc.
All Rights Reserved. This EBook is published
under license with the original publisher
John Wiley & Sons, Inc.
© Перевод, оформление, Лаборатория знаний,
2015
ISBN 978-5-93208-688-9

Оглавление
Предисловие редактора перевода
9
Предисловие авторов к русскому изданию
11
Предисловие
13
Благодарности
15
Часть I. МЕТОДЫ
Глава
1. Основы
18
1.1. Вероятностный метод
18
1.2. Теория графов
20
1.3. Комбинаторика
24
1.4. Комбинаторная теория чисел
27
1.5. Пары с пустым пересечением
28
1.6. Упражнения
29
Вероятностный взгляд: Теорема Эрдёша—Ко—Радо
31
Глава
2. Линейность математического ожидания
32
2.1. Основы
32
2.2. Разбиение графов
33
2.3. Два быстрых результата
35
2.4. Балансировка векторов
36
2.5. Разбалансировка лампочек
38
2.6. Без подбрасывания монет
39
2.7. Упражнения
40
Вероятностный взгляд: Теорема Брегмана
42
Глава
3. Малые вариации
44
3.1. Числа Рамсея
44
3.2. Независимые множества
46
3.3. Комбинаторная геометрия
47
3.4. Упаковка
48
3.5. Перекраска
49
3.6. Непрерывное время
53
3.7. Упражнения
58
Вероятностный взгляд: Большой обхват и большое хроматическое
число
59
Глава
4. Второй момент
60
4.1. Основы
60
4.2. Теория чисел
61

ОГЛАВЛЕНИЕ
4.3. Дополнительные теоретические сведения
64
4.4. Случайные графы
66
4.5. Максимальный размер клики
70
4.6. Различные суммы
71
4.7. Подход Рёдля
73
4.8. Упражнения
78
Вероятностный взгляд: Гамильтоновы пути
80
Глава
5. Локальная лемма
83
5.1. Лемма
83
5.2. Свойство 𝐵и разноцветные множества действительных
чисел
86
5.3. Нижние оценки для чисел Рамсея
87
5.4. Геометрический результат
89
5.5. Линейная древесность графов
90
5.6. Латинские трансверсали
95
5.7. Алгоритмический аспект
96
5.8. Упражнения
100
Вероятностный взгляд: Ориентированные циклы
101
Глава
6. Корреляционные неравенства
102
6.1. Теорема о четырех функциях Альсведе и Дайкина
103
6.2. FKG-неравенство
106
6.3. Монотонные свойства
107
6.4. Линейные расширения частично упорядоченных множеств
109
6.5. Упражнения
112
Вероятностный взгляд: Теорема Турана
113
Глава
7. Мартингалы и плотная концентрация
115
7.1. Определения
115
7.2. Большие уклонения
117
7.3. Хроматическое число
118
7.4. Два обобщения
121
7.5. Четыре примера
125
7.6. Неравенство Талаграна
127
7.7. Приложения неравенства Талаграна
130
7.8. Полиномиальная концентрация Кима—Ву
133
7.9. Упражнения
135
Вероятностный взгляд: Теорема Вейерштрасса о приближении
136
Глава
8. Парадигма Пуассона
137
8.1. Неравенства Янсона
137
8.2. Доказательства
139
8.3. Решето Бруна
142
8.4. Большие уклонения
145
8.5. Оценка числа расширений
146
8.6. Число представлений
148

ОГЛАВЛЕНИЕ
7
8.7. Дальнейшие обобщения
151
8.8. Упражнения
153
Вероятностный взгляд: Локальная раскраска
154
Глава
9. Псевдослучайность
156
9.1. Турниры квадратичных вычетов
157
9.2. Собственные значения и расширители
160
9.3. Квазислучайные графы
167
9.4. Упражнения
173
Вероятностный взгляд: Случайные блуждания
174
Часть II. Приложения
Глава 10. Случайные графы
178
10.1. Подграфы
179
10.2. Размер максимальной клики
181
10.3. Хроматическое число
183
10.4. Ветвящиеся процессы
184
10.5. Гигантская компонента
188
10.6. Фазовый переход изнутри
192
10.7. Законы «нуля или единицы»
195
10.8. Упражнения
204
Вероятностный взгляд: Число подграфов
205
Глава 11. Сложность схем
207
11.1. Предварительные замечания
207
11.2. Случайные ограничения и схемы ограниченной глубины
209
11.3. Еще о схемах ограниченной глубины
213
11.4. Монотонные схемы
216
11.5. Формулы
219
11.6. Упражнения
221
Вероятностный взгляд: Максимальные антицепи
222
Глава 12. Разброс
223
12.1. Основы
223
12.2. Достаточность шести стандартных отклонений
224
12.3. Линейный и наследственный разброс
228
12.4. Нижние оценки
231
12.5. Теорема Бека—Фиала
233
12.6. Упражнения
235
Вероятностный взгляд: Несбалансированные матрицы
237
Глава 13. Геометрия
238
13.1. Наибольший угол между точками в евклидовом пространстве
239
13.2. Пустые треугольники, определяемые точками плоскости
240
13.3. Геометрическая реализация ±1-матриц
242

ОГЛАВЛЕНИЕ
13.4. 𝜀-сети и VC-размерности ранжированных пространств
244
13.5. Двойственная функция расщепления и разброс
250
13.6. Упражнения
253
Вероятностный взгляд: Эффективная упаковка
254
Глава 14. Коды, игры и энтропия
256
14.1. Коды
256
14.2. Игра лжеца
259
14.3. Игра «постоянная должность»
261
14.4. Игра «балансировка векторов»
263
14.5. Неадаптивные алгоритмы
265
14.6. Энтропия
266
14.7. Упражнения
272
Вероятностный взгляд: Экстремальные графы
273
Глава 15. Дерандомизация
275
15.1. Метод условных вероятностей
275
15.2. 𝑑-независимые случайные величины в пространствах малого
размера
280
15.3. Упражнения
284
Вероятностный взгляд: Число пересечений, инцидентности, суммы
и произведения
285
Приложение A. Оценки для больших уклонений
287
A.1. Оценки для больших уклонений
287
A.2. Упражнения
295
Вероятностный взгляд: Графы, свободные от треугольников,
содержат большие независимые множества
296
Приложение B. Пол Эрдёш
298
B.1. Труды
298
B.2. Гипотезы
300
B.3. Об Эрдёше
301
B.4. Дядюшка Пол
302
Литература
305
Предметный указатель
314
Именной указатель
319

Предисловие редактора перевода
Мне приятно представить читателю эту замечательную книгу двух выдающихся специалистов в области дискретной математики. Нога Алон — член
Национальной Академии наук Израиля, автор более чем трехсот работ по
комбинаторике и теории сложности, обладатель премий Эрд¨
еша (1989), Фейера (1991), Пойа (2000), Бруно (2001), Ландау (2005), Г¨
еделя (2005). Джоэл
Спенсер — профессор Института Куранта Нью-Йоркского университета, автор
около двухсот работ по теории случайных графов, комбинаторике и теории
сложности, соавтор Пола Ерд¨
еша по книге «Случайные графы», один из основателей и главных редакторов журнала «Случайные структуры и алгоритмы».
Авторы являются членами редакций многих математических журналов. Они
неоднократно приглашались в качестве пленарных докладчиков на международные конференции и конгрессы. Не последнее место в ряду их достижений
занимает монография «Вероятностный метод»
Первое издание книги, вышедшее в свет в 1991 г., стало одной из самых
цитируемых книг в сообществе математиков, специализирующихся в области
дискретной математики, информатики и применения вероятностных методов.
Идея перевода ее на русский язык возникла еще в 1993 г., когда Джоэл Спенсер
подарил мне экземпляр «Вероятностного метода» и еще более окрепла, когда
я получил второе издание книги от Н. Алона. Благодаря Российскому фонду
фундаментальных исследований идея перевода книги стала реальностью.
Главная цель монографии — изложение идей вероятностного подхода к
решению задач дискретной математики. Авторы явно придерживаются известного тезиса о том, что пример учит лучше, чем теория. Подбор примеров
внутри глав отвечает самым высоким требованиям целесообразности и вкуса, а
примеры, помещенные в промежутках между главами, являются избранными
шедеврами. По существу, это — мастер-класс двух маэстро для лиц, заинтересованных в освоении вероятностных методов.
В книге делается акцент на методологии. При относительно небольшом
объеме она обладает высокой плотностью идей, приходящихся на страницу
текста. Авторы часто жертвуют законченностью результатов в пользу ясности
и краткости изложения. Строгое изложение утверждений как правило предваряется содержательным обсуждением метода. Наличие упражнений способствует более продуктивному восприятию материала и приобретению навыков
в применении методов.
Книга Н. Алона и Д. Спенсера удачно дополняет монографии отечественных авторов В. Ф. Колчина, В. Н. Сачкова, Б. А. Севастьянова, В. П. Чистякова и др. по аналогичной тематике.

Предисловие редактора перевода
Книга будет полезна специалистам в области дискретной математики (комбинаторики, теории сложности, приложений теории вероятностей) как краткая
энциклопедия приемов, связанных с применением вероятностных методов.
Преподаватели вузов найдут в ней обширный материал для спецкурсов и
аспирантских экзаменов. Известно, что спецкурсы по материалам книги читаются во многих университетах мира, в том числе и российских. Книга будет
полезна студентам и аспирантам математических специальностей для первоначального ознакомления с предметом. Она доступна читателям, знакомым с
университетскими курсами математического анализа и теории вероятностей.
Специалисты в области теории вероятностей найдут много замечательных
примеров применения вероятностных методов в комбинаторике и тории чисел.
Авторы иногда используют устоявшиеся понятия без определений. Для
читателей, знакомых с университетским курсом дискретной математики, это
не доставляет каких-либо неудобств. В книгах, добавленных при переводе,
можно найти все используемые здесь понятия.
Над переводом книги работали Ф. Ю. Воробьев, К. Г. Омельянов, Т. Г. Петросян и автор этих строк. Общее редактирование осуществлялось мною.
Т. В. Андреева много сделала для улучшения стиля перевода. А. Б. Дайняк
принял участие в подготовке оригинал-макета. Весьма ценные замечания
сделаны Н. Н. Кузюриным, Д. С. Романовым и Б. С. Стечкиным. Г. А. Махина
оказала нам помощь при переводе эпиграфов к главам.
Авторы книги любезно предоставили электронный вариант рукописи и
список замечаний от читателей, что предотвратило внесение опечаток при
наборе формул и позволило исправить некоторые имеющиеся.
Редактор берет на себя ответственность за качество перевода и будет
признателен всем, кто укажет на его возможные недостатки.
А. А. Сапоженко