Странная логика случайных графов - Википедия - The Strange Logic of Random Graphs

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

Темы

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

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

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

Аудитория и прием

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

Рекомендации