Аннотация:
Рассматриваются случайные графы Эрдёша-Реньи $G(n,p)$ на $n$ вершинах, определяемые тем свойством, что ребро между любыми двумя вершинами проводится с вероятностью $p$. В 1988 году Дж. Спенсер и С. Шелах доказали, что если $p=n^{-a}$, где $a$ - положительное иррациональное число, то для любого свойства, выразимого в логике первого порядка, вероятность того, что случайный граф обладает этим свойством стремится либо к 1, либо к 0 при $n$ стремящемся к бесконечности (иными словами, выполнен закон нуля или единицы). Если же $a$ из интервала $(0,1)$ - рациональное число, то закон нуля или единицы не выполнен. Позже докладчиком было доказано, что для любого свойства, выразимого формулами языка первого порядка кванторной глубины не более $k$, выполнен закон нуля или единицы, если $a$ принадлежит интервалам $(0,1/(k-2))$ и $(1-1/(2^{k}-2),1)$. На концах этих интервалов закон нуля или единицы не выполнен.
Для произвольного свойства $L$, выразимого в логике первого порядка, назовем спектром $S(L)$ множество всех чисел $a$ из $(0,1)$ таких, что закон нуля или единицы для свойства $L$ и случайного графа $G(n,n^{-a})$ не выполнен. В 1990 году Дж. Спенсер доказал, что существует свойство с бесконечным спектром. Спектром числа $k$ назовем объединение по всем свойствам $L$, выражаемым формулами кванторной глубины $k$, множеств $S(L)$. Недавно в совместной работе с Дж. Спенсером нам удалось получить новые результаты о распределении точек в спектре. В частности, мы оценили наименьшую и набольшую предельные точки в этом множестве, а также получили оценки на наименьшее $k$, спектр которого бесконечен.
|
