Вероятностный метод, Алон Н., Спенсер Д., 2013

Вероятностный метод, Алон Н., Спенсер Д., 2013.

  Одна из самых известных зарубежных книг в области применения вероятностных методов в комбинаторике. В книге содержатся основные элементы методологии. Строгие обоснования и доказательства сопровождаются ясными и неформальными обсуждениями задач, методов и их приложений. Каждый метод иллюстрируется целым рядом точно подобранных примеров.
Для специалистов в области дискретной математики и теории случайных графов, студентов, аспирантов и преподавателей соответствующих дисциплин.




ВЕРОЯТНОСТНЫЙ МЕТОД.
Вероятностный метод является мощным инструментом для решения многих задач дискретной математики. Грубо говоря, этот метод работает следующим образом: пытаясь доказать, что структура с некоторыми искомыми свойствами существует, мы определяем подходящее вероятностное пространство структур, а затем показываем, что искомые свойства выполняются для случайно выбранного элемента в этом пространстве с положительной вероятностью.

Метод лучше всего проиллюстрировать примерами. Ниже — один из них. Число Рамсея R(k, l) есть наименьшее целое n, такое, что при любой раскраске ребер полного n-вершинного графа в синий и красный цвета либо существует красный подграф Кk (т. е. полный подграф на к вершинах, каждое ребро которого раскрашено в красный цвет), либо существует синий подграф Kl. В 1929 г. Рамсей показал, что число R(k,l) конечно для любых k и l. Мы найдем нижнюю оценку для диагонального числа Рамсея R(k,k).

Купить .





Теги: учебник по математике :: математика :: Алон :: Спенсер