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

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

Темы

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

Фундаментальный результат в этой области, независимо доказанный Glebski et al. и по Рональд Феджин, состоит в том, что существует закон нуля или единицы для ${\displaystyle G(n,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(n,n^{-a})}$.^[1] Ключевым инструментом доказательства является Игра Эренфойхта – Фраиссе.^[3]

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

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

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

1. Берардуччи, Алессандро (2003), "Обзор Странная логика случайных графов", Математические обзоры, МИСТЕР  1847951
2. Колчин В.Ф. (январь 2007 г.), перевод Колчина А.В. Странная логика случайных графов", Теория вероятностей и ее приложения, 51 (3): 554–555, Дои:10.1137 / s0040585x97982608
3. Фрэнк, Уве, "Обзор Странная логика случайных графов", zbMATH, Zbl  0976.05001