24 ноября (вторник), 1600, аудитория 307 ИППИ РАН
Свойства первого порядка случайного графа Эрдеша-Реньи
Говорят, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если для любого свойства, записанного с помощью формулы первого порядка, кванторная глубина которой не превосходит числа k, вероятность им обладатьстремится либо к нулю, либо к единице. В 1988 году Дж. Спенсер и С. Шела доказали, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если вероятность ребра является степенной функцией от количества вершин графа, где показатель степени – отрицательное иррациональное число. Мы нашли различные диапазоны рациональных значений показателя степени в вероятности ребра случайного графа, при которых он подчиняется k-закону нуля или единицы. Эффект отсутствия закона нуля или единицы, в частности, вызван тем, что для некоторых простых свойств первого порядка (например, экзистенциальных) существует пороговая вероятность, которая как раз равна степени числа вершин с соответствующим рациональным показателем. Под пороговой вероятностью свойства подразумевается такая функция от числа вершин, что при вероятности проведения ребра, асимптотически меньшей этой функции, вероятность выполнения свойства стремится к нулю, а при большей – к единице (или наоборот). Разумеется, пороговых вероятностей может быть более одной для одного свойства. Множество рациональных показателей степени в вероятностях проведения ребра, которые являются пороговыми вероятностями, называется спектром рассматриваемого свойства. В 1990 году Дж. Спенсер доказал, что существуют свойства первого порядка с бесконечным спектром. Спектром числа k мы называем объединение спектров всех свойств, выразимых формулами первого порядка, кванторные глубины которых не превосходят k. Дж. Спенсер доказал, что при достаточно больших k число 1/3 является предельной точкой в спектре числа k. Мы оценили минимальный и максимальный элементы спектров, а также минимальное значение k, при котором спектр бесконечен.
| 20.11.2015 | |