М.: Бином, 2011. — 320 с.
Данное уникальное издание посвящено применению вероятностного
подхода ко многим задачам комбинаторики, теории графов, теории
чисел, оптимального кодирования, геометрии и другим задачам
математики и её применений. В приложении к книге рассказывается об
известном математике Поле Эрдёше, с именем которого во многом
связан этот подход, перечислены наиболее интересные, по мнению
авторов книги, его работы, высказанные им гипотезы и работы о нём и
его трудах. Книга полезна не только для студентов и аспирантов
математических и математически насыщенных специальностей и
преподавателей соответствующих дисциплин, но также и для многих
иных специалистов из биологии, медицины, химии, технологии,
психологии, и т.д.
Предисловие редактора перевода
Предисловие авторов к русскому изданию
Предисловие
Благодарности Методы
Основы
Вероятностный метод
Теория графов
Комбинаторика
Комбинаторная теория чисел
Пары с пустым пересечением
Упражнения
Вероятностный взгляд: Теорема Эрдёша-Ко-Радо Линейность математического ожидания
Основы
Разбиение графов
Два быстрых результата
Балансировка векторов
Разбалансировка лампочек
Без подбрасывания монет
Упражнения
Вероятностный взгляд: Теорема Брегмана Малые вариации
Числа Рамсея
Независимые множества
Комбинаторная геометрия
Упаковка
Перекраска
Непрерывное время
Упражнения
Вероятностный взгляд: Большой обхват и большое число Второй момент
Основы
Теория чисел
Дополнительные теоретические сведения
Случайные графы
Максимальный размер клики
Различные суммы
Подход Рёдля
Упражнения
Вероятностный взгляд: Гамильтоновы пути Локальная лемма
Лемма
Свойство В и разноцветные множества действительных чисел
Нижние оценки для чисел Рамсея
Геометрический результат
Линейная древесность графов
Латинские трансвереали
Алгоритмический аспект
Упражнения
Вероятностный взгляд: Ориентированные циклы Корреляционные неравенства
Теорема о четырех функциях Альсведе и Дайкина
FКG-неравенство
Монотонные свойства
Линейные расширения частично упорядоченных множеств
Упражнения
Вероятностный взгляд: Теорема Турана Мартингалы и плотная концентрация
Определения
Большие уклонения
Хроматическое число
Два обобщения
Четыре примера
Неравенство Талаграна
Приложения неравенства Талаграна
Полиномиальная концентрация Кима-Ву
Упражнения
Вероятностный взгляд: Теорема Вейерштрасса о приближении Парадигма Пуассона
Неравенства Янcона
Доказательства
Решето Бруна
Большие уклонения
Оценка числа расширений
Число представлений
Дальнейшие обобщения
Упражнения
Вероятностный взгляд: Локальная раскраска Псевдослучайность
Турниры квадратичных вычетов
Собственные значения и расширители
Квазислучайные графы
Упражнения
Вероятностный взгляд: Случайные блуждания Приложения
Случайные графы
Подграфы
Размер максимальной клики
Хроматическое число
Ветвящиеся процессы
Гигантская компонента
Фазовый переход изнутри
Законы «нуля или единицы»
Упражнения
Вероятностный взгляд: Число подграфов Сложность схем
Предварительные замечания
Случайные ограничения и схемы ограниченной глубины
Еще о схемах ограниченной глубины
Монотонные схемы
Формулы
Упражнения
Вероятностный взгляд: Максимальные антицепи Разброс
Основы
Достаточность шести стандартных отклонений
Линейный и наследственный разброс
Нижние оценки
Теорема Бека-Фиала
Упражнения
Вероятностный взгляд: Несбалансированные матрицы Геометрия
Наибольший угол между точками в евклидовом пространстве
Пустые треугольники, определяемые точками плоскости
Геометрическая реализация ±1-матриц
е-сети и VC-размерности ранжированных пространств
Двойственная функция расщепления и разброс
Упражнения
Вероятностный взгляд: Эффективная упаковка Коды, игры и энтропия
Коды
Игра лжеца
Игра «постоянная должность»
Игра «балансировка векторов»
Неадаптивные алгоритмы
Энтропия
Упражнения
Вероятностный взгляд: Экстремальные графы Дерандомизация
Метод условных вероятностей
d-независимые случайные величины в пространствах малого размера
Упражнения
Вероятностный взгляд: Число пересечений, инцидентности, суммы и произведения Приложения Оценки для больших уклонений
Оценки для больших уклонений
Упражнения
Вероятностный взгляд: Графы, свободные от треугольников, содержат большие независимые множества Пол Эрдёш
Труды
Гипотезы
Об Эрдёше
Дядюшка Пол Литература
Предметный указатель
Именной указатель
Предисловие авторов к русскому изданию
Предисловие
Благодарности Методы
Основы
Вероятностный метод
Теория графов
Комбинаторика
Комбинаторная теория чисел
Пары с пустым пересечением
Упражнения
Вероятностный взгляд: Теорема Эрдёша-Ко-Радо Линейность математического ожидания
Основы
Разбиение графов
Два быстрых результата
Балансировка векторов
Разбалансировка лампочек
Без подбрасывания монет
Упражнения
Вероятностный взгляд: Теорема Брегмана Малые вариации
Числа Рамсея
Независимые множества
Комбинаторная геометрия
Упаковка
Перекраска
Непрерывное время
Упражнения
Вероятностный взгляд: Большой обхват и большое число Второй момент
Основы
Теория чисел
Дополнительные теоретические сведения
Случайные графы
Максимальный размер клики
Различные суммы
Подход Рёдля
Упражнения
Вероятностный взгляд: Гамильтоновы пути Локальная лемма
Лемма
Свойство В и разноцветные множества действительных чисел
Нижние оценки для чисел Рамсея
Геометрический результат
Линейная древесность графов
Латинские трансвереали
Алгоритмический аспект
Упражнения
Вероятностный взгляд: Ориентированные циклы Корреляционные неравенства
Теорема о четырех функциях Альсведе и Дайкина
FКG-неравенство
Монотонные свойства
Линейные расширения частично упорядоченных множеств
Упражнения
Вероятностный взгляд: Теорема Турана Мартингалы и плотная концентрация
Определения
Большие уклонения
Хроматическое число
Два обобщения
Четыре примера
Неравенство Талаграна
Приложения неравенства Талаграна
Полиномиальная концентрация Кима-Ву
Упражнения
Вероятностный взгляд: Теорема Вейерштрасса о приближении Парадигма Пуассона
Неравенства Янcона
Доказательства
Решето Бруна
Большие уклонения
Оценка числа расширений
Число представлений
Дальнейшие обобщения
Упражнения
Вероятностный взгляд: Локальная раскраска Псевдослучайность
Турниры квадратичных вычетов
Собственные значения и расширители
Квазислучайные графы
Упражнения
Вероятностный взгляд: Случайные блуждания Приложения
Случайные графы
Подграфы
Размер максимальной клики
Хроматическое число
Ветвящиеся процессы
Гигантская компонента
Фазовый переход изнутри
Законы «нуля или единицы»
Упражнения
Вероятностный взгляд: Число подграфов Сложность схем
Предварительные замечания
Случайные ограничения и схемы ограниченной глубины
Еще о схемах ограниченной глубины
Монотонные схемы
Формулы
Упражнения
Вероятностный взгляд: Максимальные антицепи Разброс
Основы
Достаточность шести стандартных отклонений
Линейный и наследственный разброс
Нижние оценки
Теорема Бека-Фиала
Упражнения
Вероятностный взгляд: Несбалансированные матрицы Геометрия
Наибольший угол между точками в евклидовом пространстве
Пустые треугольники, определяемые точками плоскости
Геометрическая реализация ±1-матриц
е-сети и VC-размерности ранжированных пространств
Двойственная функция расщепления и разброс
Упражнения
Вероятностный взгляд: Эффективная упаковка Коды, игры и энтропия
Коды
Игра лжеца
Игра «постоянная должность»
Игра «балансировка векторов»
Неадаптивные алгоритмы
Энтропия
Упражнения
Вероятностный взгляд: Экстремальные графы Дерандомизация
Метод условных вероятностей
d-независимые случайные величины в пространствах малого размера
Упражнения
Вероятностный взгляд: Число пересечений, инцидентности, суммы и произведения Приложения Оценки для больших уклонений
Оценки для больших уклонений
Упражнения
Вероятностный взгляд: Графы, свободные от треугольников, содержат большие независимые множества Пол Эрдёш
Труды
Гипотезы
Об Эрдёше
Дядюшка Пол Литература
Предметный указатель
Именной указатель