Оглавление......5Предисловие редактора перевода......9Предисловие авторов к русскому изданию......11Предисловие......13Благодарности......15ЧАСТЬ I. МЕТОДЫ......17Глава 1. Основы......181.1. Вероятностный метод......181.2. Теория графов......201.3. Комбинаторика......241.4. Комбинаторная теория чисел......271.5. Пары с пустым пересечением......281.6. Упражнения......29Вероятностный взгляд: Теорема Эрдёша-Ко-Радо......31Глава 2. Линейность математического ожидания......322.1. Основы......322.2. Разбиение графов......332.3. Два быстрых результата......352.4. Балансировка векторов......362.5. Разбалансировка лампочек......382.6. Без подбрасывания монет......392.7. Упражнения......40Вероятностный взгляд: Теорема Брегмана......42Глава 3. Малые вариации......443.1. Числа Рамсея......443.2. Независимые множества......463.3. Комбинаторная геометрия......473.4. Упаковка......483.5. Перекраска......493.6. Непрерывное время......533.7. Упражнения......58Вероятностный взгляд: Большой обхват и большое хроматическое число......59Глава 4. Второй момент......604.1. Основы......604.2. Теория чисел......614.3. Дополнительные теоретические сведения......644.4. Случайные графы......664.5. Максимальный размер клики......704.6. Различные суммы......714.7. Подход Рёдля......734.8. Упражнения......78Вероятностный взгляд: Гамильтоновы пути......80Глава 5. Локальная лемма......835.1. Лемма......835.2. Свойство B и разноцветные множества действительных чисел......865.3. Нижние оценки для чисел Рамсея......875.4. Геометрический результат......895.5. Линейная древесность графов......905.6. Латинские трансверсали......955.7. Алгоритмический аспект......965.8. Упражнения......100Вероятностный взгляд: Ориентированные циклы......101Глава 6. Корреляционные неравенства......1026.1. Теорема о четырех функциях Альсведе и Дайкина......1036.2. FKG-неравенство......1066.3. Монотонные свойства......1076.4. Линейные расширения частично упорядоченных множеств......1096.5. Упражнения......112Вероятностный взгляд: Теорема Турана......113Глава 7. Мартингалы и плотная концентрация......1157.1. Определения......1157.2. Большие уклонения......1177.3. Хроматическое число......1187.4. Два обобщения......1217.5. Четыре примера......1257.6. Неравенство Талаграна......1277.7. Приложения неравенства Талаграна......1307.8. Полиномиальная концентрация Кима-Ву......1337.9. Упражнения......135Вероятностный взгляд: Теорема Вейерштрасса о приближении......136Глава 8. Парадигма Пуассона......1378.1. Неравенства Янсона......1378.2. Доказательства......1398.3. Решето Бруна......1428.4. Большие уклонения......1458.5. Оценка числа расширений......1468.6. Число представлений......1488.7. Дальнейшие обобщения......1518.8. Упражнения......153Вероятностный взгляд: Локальная раскраска......154Глава 9. Псевдослучайность......1569.1. Турниры квадратичных вычетов......1579.2. Собственные значения и расширители......1609.3. Квазислучайные графы......1679.4. Упражнения......173Вероятностный взгляд: Случайные блуждания......174ЧАСТЬ II. ПРИЛОЖЕНИЯ......177Глава 10. Случайные графы......17810.1. Подграфы......17910.2. Размер максимальной клики......18110.3. Хроматическое число......18310.4. Ветвящиеся процессы......18410.5. Гигантская компонента......18810.6. Фазовый переход изнутри......19210.7. Законы «нуля или единицы»......19510.8. Упражнения......204Вероятностный взгляд: Число подграфов......205Глава 11. Сложность схем......20711.1. Предварительные замечания......20711.2. Случайные ограничения и схемы ограниченной глубины......20911.3. Еще о схемах ограниченной глубины......21311.4. Монотонные схемы......21611.5. Формулы......21911.6. Упражнения......221Вероятностный взгляд: Максимальные антицепи......222Глава 12. Разброс......22312.1. Основы......22312.2. Достаточность шести стандартных отклонений......22412.3. Линейный и наследственный разброс......22812.4. Нижние оценки......23112.5. Теорема Бека-Фиала......23312.6. Упражнения......235Вероятностный взгляд: Несбалансированные матрицы......237Глава 13. Геометрия......23813.1. Наибольший угол между точками в евклидовом пространстве......23913.2. Пустые треугольники
определяемые точками плоскости......24013.3. Геометрическая реализация ±1-матриц......24213.4. -сети и VC-размерности ранжированных пространств......24413.5. Двойственная функция расщепления и разброс......25013.6. Упражнения......253Вероятностный взгляд: Эффективная упаковка......254Глава 14. Коды
игры и энтропия......25614.1. Коды......25614.2. Игра лжеца......25914.3. Игра «постоянная должность»......26114.4. Игра «балансировка векторов»......26314.5. Неадаптивные алгоритмы......26514.6. Энтропия......26614.7. Упражнения......272Вероятностный взгляд: Экстремальные графы......273Глава 15. Дерандомизация......27515.1. Метод условных вероятностей......27515.2. d-независимые случайные величины в пространствах малого размера......28015.3. Упражнения......284Вероятностный взгляд: Число пересечений
инцидентности
суммы и произведения......285Приложение A. Оценки для больших уклонений......287A.1. Оценки для больших уклонений......287A.2. Упражнения......295Вероятностный взгляд: Графы
свободные от треугольников
содержат большие независимые множества......296Приложение B. Пол Эрдёш......298B.1. Труды......298B.2. Гипотезы......300B.3. Об Эрдёше......301B.4. Дядюшка Пол......302Литература......305Предметный указатель......314Именной указатель......319