СПЕКТР НЕГЛУБОКИХ МОНАДИЧЕСКИХ СВОЙСТВ РАЗРЕЖЕННЫХ СЛУЧАЙНЫХ ГРАФОВ

Говорят, что случайный граф подчиняется монадическому -закону нуля или единицы, если для любой монадической формулы кванторной глубины вероятность того, что она истинна для случайного графа, стремится либо к нулю, либо к единице. В настоящей работе мы рассматриваем случай вслед за Дж. Спенсером и С. Шелахом. Мы доказали, что наименьшее , при котором сущестует бесконечно много значений , для которых случайный граф не подчиняется -закону нуля или единицы, равно 4.