Оглавление......5 Предисловие редактора перевода......9 Предисловие авторов к русскому изданию......11 Предисловие......13 Благодарности......15 ЧАСТЬ I. МЕТОДЫ......17 Глава 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. Свойство B и разноцветные множества действительных чисел......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 8.7. Дальнейшие обобщения......151 8.8. Упражнения......153 Вероятностный взгляд: Локальная раскраска......154 Глава 9. Псевдослучайность......156 9.1. Турниры квадратичных вычетов......157 9.2. Собственные значения и расширители......160 9.3. Квазислучайные графы......167 9.4. Упражнения......173 Вероятностный взгляд: Случайные блуждания......174 ЧАСТЬ II. ПРИЛОЖЕНИЯ......177 Глава 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. d-независимые случайные величины в пространствах малого размера......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