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

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

Authors
Жуковский М.Е. 1, 2 , Купавский А.Б.1, 3
Journal
Doklady Akademii Nauk
Number of issue
5
Language
Russian
Pages
503-505
Status
Published
Volume
472
Year
2017
Organizations
  • 1 Московский физико-технический институт (государственный университет), Долгопрудный Московской обл.
  • 2 Российский университет дружбы народов, Москва
  • 3 University Grenoble Alpes, France
Cite
ГОСТ MLA RIS BibTex
Share

Other records