Странная логика случайных графов

Странная логика случайных графов - это книга о законах нуля или единицы для случайных графов . Он был написан Джоэлом Спенсером и опубликован в 2001 году компанией Springer-Verlag в качестве 22 тома их серии книг « Алгоритмы и комбинаторика» .

Темы [ править ]

Случайные графы книги генерируются из модели Эрдеша – Реньи – Гилберта, в которой заданы вершины и делается случайный выбор, соединять ли каждую пару вершин ребром независимо для каждой пары с вероятностью установления соединения. Закон нуля или единицы - это теорема, утверждающая, что для определенных свойств графов и для определенных вариантов вероятность создания графа с этим свойством стремится к нулю или единице в пределе, стремящемся к бесконечности. ^[1]${\ Displaystyle G (п, р)}$${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle n}$

Фундаментальный результат в этой области, независимо доказанный Glebski et al. и Рональдом Фэджином , заключается в том, что существует закон нуля или единицы для каждого свойства, которое может быть описано в логике графов первого порядка . ^[2] Более того, предельная вероятность равна единице тогда и только тогда, когда бесконечный граф Радо обладает этим свойством. Например, случайный граф в этой модели содержит треугольник с вероятностью, стремящейся к единице; он содержит универсальную вершину с вероятностью, стремящейся к нулю. Для других вариантов возможны другие результаты. Например, предельная вероятность наличия треугольника составляет от 0 до 1, когда используется константа ; он стремится к 0 для меньшего выбора${\ Displaystyle G (п, 1/2)}$${\ displaystyle p}$${\ displaystyle p = c / n}$${\ displaystyle c}$${\ displaystyle p}$и 1 для большего выбора. Функция называется порогом для свойства содержать треугольник, что означает, что она отделяет значения с предельной вероятностью 0 от значений с предельной вероятностью 1. ^[1]${\ displaystyle 1 / n}$${\ displaystyle p}$

Главный результат книги (доказанный Спенсером с Сахароном Шелахом ) состоит в том, что иррациональные степени никогда не являются пороговыми функциями. То есть, когда это иррациональное число , существует закон нуля или единицы для свойств первого порядка случайных графов . ^[1] Ключевым инструментом в доказательстве является игра Эренфойхта – Фраиссе . ^[3]${\ displaystyle n}$${\ displaystyle a> 0}$${\ Displaystyle G (п, п ^ {- а})}$

Аудитория и прием [ править ]

Хотя по сути это доказательство единственной теоремы, предназначенное для специалистов в данной области, книга написана в удобочитаемом стиле, который знакомит читателя со многими важными темами теории конечных моделей и теории случайных графов. Рецензент Валентин Колчин, сам автор другой книги о случайных графах, пишет, что книга «самодостаточна, легко читается и отличается элегантным написанием», рекомендуя ее теоретикам вероятностей и логикам . ^[2] Рецензент Алессандро Берардуччи называет книгу «красиво написанной» и ее тематику «увлекательной». ^[1]

Ссылки [ править ]