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

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

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го английского издания

А. А. Сапоженко

Д о п у щ е н о

по прикладной математике и информатике УМО 
учебнометодическим советом

по классическому университетскому образованию 
в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся 
по специальности и направлению 
«Прикладная математика и информатика» 
и по направлению «Информационные технологии»

Москва
Лаборатория знаний
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 ГК РФ при устранении ограничений, установленных
техническими средствами защиты авторских прав, правообладатель вправе требовать
от нарушителя возмещения убытков или выплаты компенсации

ISBN 978-5-00101-672-4

c○
Copyright
2000 by John Wiley & Sons, Inc. All Rights
Reserved. This EBook is published under license
with the original publisher
John Wiley & Sons, Ltd.

c○ Перевод, оформление, Лаборатория знаний, 2015

4

Оглавление

Предисловие редактора перевода
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 г., когда Джоэл Спенсер
подарил мне экземпляр «Вероятностного метода» и еще более окрепла, когда
я получил второе издание книги от Н. Алона. Благодаря Российскому фонду
фундаментальных исследований идея перевода книги стала реальностью.
Главная цель монографии — изложение идей вероятностного подхода к
решению задач дискретной математики. Авторы явно придерживаются известного тезиса о том, что пример учит лучше, чем теория. Подбор примеров
внутри глав отвечает самым высоким требованиям целесообразности и вкуса, а
примеры, помещенные в промежутках между главами, являются избранными
шедеврами. По существу, это — мастер-класс двух маэстро для лиц, заинтересованных в освоении вероятностных методов.
В книге делается акцент на методологии. При относительно небольшом
объеме она обладает высокой плотностью идей, приходящихся на страницу
текста. Авторы часто жертвуют законченностью результатов в пользу ясности
и краткости изложения. Строгое изложение утверждений как правило предваряется содержательным обсуждением метода. Наличие упражнений способствует более продуктивному восприятию материала и приобретению навыков
в применении методов.
Книга Н. Алона и Д. Спенсера удачно дополняет монографии отечественных авторов В. Ф. Колчина, В. Н. Сачкова, Б. А. Севастьянова, В. П. Чистякова и др. по аналогичной тематике.

Предисловие редактора перевода

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

Предисловие авторов
к русскому изданию

Написание предисловия к книге вещь всегда приятная, поскольку на самом
деле является завершением долгой работы над проектом. Нам доставляет особое удовольствие написать предисловие к русскому изданию Вероятностного
метода поскольку в данном случае большая, тщательная и профессиональная
работа по переводу выполнена А. А. Сапоженко и его аспирантами К. Омельяновым, Т. Петросяном и Ф. Воробьевым, в то время как наша задача состояла
в основном в добавлении этих коротких комментариев.
Открытие того, что детерминированные утверждения могут быть доказаны
с помощью вероятностных соображений, позволило уже в первой половине
XX в. доказать ряд замечательных утверждений из анализа, теории чисел,
комбинаторики и теории информации. Вскоре стало ясно, что метод, который
сейчас называется вероятностным, является весьма мощным инструментом
получения результатов в дискретной математике. Ранние результаты такого
сорта сочетали комбинаторные соображения с элементарной вероятностной
техникой, однако развитие метода в последние годы потребовало применения
все более изощренных инструментов теории вероятности.
Применение вероятностного метода в дискретной математике было инициировано Полом Эрд¨ешем, который сделал для его развития больше, чем
кто-либо другой. Полученные им результаты можно разбить на три группы.
К первой относится изучение определенных классов комбинаторных объектов, таких как случайные графы или случайные матрицы. Эти результаты
по существу являются теоретико-вероятностными, хотя большинство из них
мотивировано задачами из комбинаторики. Вторая группа состоит из примеров применения вероятностных соображений для доказательства существования комбинаторных структур, обладающих рядом предписанных свойств.
Доказательства существования такого типа часто приводят к экстремальным
решениям различных задач дискретной математики. Третья группа состоит
из самых поразительных примеров, фокусирующих внимание на применении
вероятностных соображений к доказательству тех утверждений, формулировка которых не дает каких-либо указаний на то, что вероятность может быть
полезна при их исследовании. Книга содержит результаты каждой из этих
трех групп.
Многие фундаментальные и наиболее важные элементы теории вероятностей были получены русскими математиками. Такие исследователи как
П. Л. Чебыш¨ев, А. А. Марков, А. Я. Хинчин и А. Н. Колмогоров заложили
основы теории вероятностей, обеспечив тем самым математические основы для
последующего развития вероятностного метода. Таким образом, русское изда

Предисловие авторов к русскому изданию

ние данной книги основано в значительной мере на достижениях российской
математики.
Нам очень приятно выразить свою признательность нашему другу и коллеге Александру Сапоженко за идею перевода нашей книги, а также всем, кто
способствовал успешному осуществлению этой идеи. Мы убеждены, что этот
перевод сделает книгу доступной для широкого круга российских исследователей.
Нога Алон
Джоэл Спенсер

Посвящается Нурит и Мэри Энн

Предисловие

В последнее время наблюдается весьма интенсивное развитие вероятностного метода. Он стал самым мощным и широко применяемым инструментом в
комбинаторике. Одной из главных причин столь быстрого развития является
важная роль случайности в теоретической информатике — области, которая
является в настоящее время источником многих интересных комбинаторных
задач.
Взаимосвязь между дискретной математикой и информатикой подразумевает алгоритмическую точку зрения при изучении вероятностного метода в
комбинаторике, и именно такой подход мы пытались проводить в этой книге.
Поэтому монография включает обсуждение алгоритмических аспектов наряду
с изучением классического метода и современных приемов, применяемых в
ней. Первая часть книги содержит описание методов, применяемых в вероятностных доказательствах, включая традиционную технику, использующую
математическое ожидание и дисперсию, а также более современные методы,
связанные с применением мартингалов и корреляционных неравенств. Вторая
часть включает изучение различных тем, в которых вероятностная техника
оказалась весьма успешной. Эта часть содержит главы, посвященные разбросу
и случайным графам, а также некоторым областям теоретической информатики: сложности логических схем, вычислительной геометрии и дерандомизации
вероятностных алгоритмов. Промежутки между главами заполнены жемчужинами под общим заголовком «Вероятностный взгляд». Они представляют
собой элегантные доказательства, относящиеся к главам, после которых они
появляются и, как правило, могут читаться отдельно.
Основная идея вероятностного метода может быть описана следующим
образом: чтобы доказать существование комбинаторной структуры с определенными свойствами, мы конструируем соответствующее вероятностное пространство и показываем, что случайно выбранный элемент этого пространства
обладает данными свойствами с положительной вероятностью. Этот метод
был предложен Полом Эрд¨ешем, который за последние пятьдесят лет внес
в его развитие столь значительный вклад, что представляется справедливым
назвать его «методом Эрд¨еша». Его вклад состоит не только в огромном
числе глубоких результатов, касающихся вероятностного подхода, но также во
многих интересных проблемах и гипотезах, которые в значительной степени
стимулировали исследования в этой области.
Написание энциклопедической книги по вероятностному методу представляется невозможным. Слишком много новых интересных результатов получено с помощью вероятностных соображений, и мы не пытаемся даже упомянуть каждый из них. В книге делается акцент на методологию. Главной

Предисловие

целью является изложение идей. Поэтому мы не всегда приводим наилучший
известный результат, если он технически слишком сложен для того, чтобы
ясно изложить его. Многие результаты являются асимптотическими. При их
изложении используются стандартные асимптотические обозначения. Пусть f
и g — две функции, мы пишем f = O(g), если f ⩽ c1g + c2 для всех значений
переменных, где c1, c2 — абсолютные константы. Мы пишем f = Ω(g), если
g = O(f), и f = Θ(g), если f = O(g) и f = O(g). Запись f = o(g) означает,
что предел отношения f/g стремится к нулю при стремлении переменных этих
функций к бесконечности. Наконец, f ∼ g означает, что f = (1 + o(1))g, т. е.
что f/g стремится к 1, когда переменные стремятся к бесконечности.
Каждая глава заканчивается упражнениями. Наиболее трудные помечены
символом
∗. Упражнения, добавленные в этом издании книги, позволяют
читателю проверить понимание материала, а также дают возможность использовать книгу как учебник.
Кроме этих упражнений второе издание содержит некоторые улучшенные
результаты и развивает различные темы, обсуждавшиеся в первом издании.
Среди добавлений упомянем следующие. В гл. 3 описан непрерывный подход
к дискретным вероятностным задачам, в гл. 7 излагаются некоторые новые
неравенства для концентрации, в гл. 13 обсуждаются отношения между
разбросом и VC-размерностью, в гл. 14 описываются некоторые приложения
функции энтропии и ее свойства. Имеются также добавления в последних двух
«Вероятностных взглядах» и новое приложение о Поле Эрд¨еше, в котором
приведены список его статей, его гипотезы и воспоминания о нем.

С особым удовольствием мы благодарим наших жен Нурит и Мэри Энн.
Их терпение, понимание и поддержка явились ключевым моментом в успехе
данного предприятия.
Нога Алон
Джоэл Спенсер