Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/Program2/zhukovskii_summary.pdf Дата изменения: Mon Oct 15 15:15:26 2012 Дата индексирования: Mon Feb 4 19:13:05 2013 Кодировка: Windows-1251 Поисковые слова: http astrokuban.info astrokuban

Краткое изложение заявки

М.Е. Жуковский

Основными объектами наших исследований являются граф ЭрдешаРеньи и случайный дистанционный граф. Говорят, что случайный граф подчиняется закону 0 или 1, если для любого свойства первого порядка вероятность его выполнения стремится либо к 0, либо к 1. В 1988 г. Дж. Спенсер и С. Шела установили, что если вероятность наличия ребра является степенной функцией от количества вершин графа с иррациональным показателем из интервала (-1,0), то закон 0 или 1 для случайного графа ЭрдешаРеньи справедлив. В случае рационального показателя случайный граф ЭрдешаРеньи не подчиняется закону 0 или 1. Случайный граф подчиняется j -закону 0 или 1, если для любого свойства, выражаемого с помощью формулы первого порядка с ограниченной числом j кванторной глубиной, вероятность такого свойства стремится к 0 или к 1. В 2010 г. мы доказали, что если показатель степени в вероятности ребра превосходит -1/(j - 2), то случайный граф подчиняется j -закону 0 или 1. Кроме того, в случае равенства показателя числу -1/(j - 2) случайный граф не подчиняется закону 0 или 1. В связи с этим возник вопрос, существуют ли в этом случае пределы вероятностей выполнения всех свойств, выражаемых формулами с кванторной глубиной, ограниченной числом j . В 2012 г. мы установили, что описанная сходимость действительно имеет место. Доказательство данных результатов опирается на теоремы о распределении малых подграфов в случайном графе. Существенно используются результаты Дж. Спенсера и С. Шела о количествах расширений различных видов. Кроме того, мы доказали теорему об асимптотике количества максимальных расширений в случайном графе, которая сыграла ключевую при доказательстве наших законов. В будущем планируется продвижение в j -законе 0 или 1 за правую границу интервала (0, 1/(j -2)]. В частности, мы хотим доказать, что для любого натурального числа j > 2 существует такое число m, что для всех показателей степени, равных несократимым дробям со знаменателем, большим m, случайных граф подчиняется j -закону 0 или 1. Кроме того, мы планируем проверить гипотезу, что случайный граф подчиняется j -закону 0 или 1, если показатель принадлежит интервалу (-1, -(j - 2)/(j - 1)). Вершины случайного дистанционного графа суть векторы в евклидовом пространстве, координаты которых равны 0 или 1. Разрешено проводить ребра, соединяющие только пары вершин, отстоящие друг от друга на наперед заданное расстояние. Ребра проводятся независимо с равными вероятностями. Мы доказали, что если вероятность наличия ребра убывает (возрастает) медленнее, чем любая степенная, то закон 0 или 1 для случайного дистанционного графа не выполнен (в отличие от графа ЭрдешаРеньи). Однако, мы нашли последовательности случайных дистанционных графов, для которых он выполнен. Мы планируем найти и другие последовательности случайных дистанционных графов (количество вершин которых растет медленнее, чем в найденной последовательности), подчиняющиеся закону 0 или 1. Нам удалось выделить последовательности, подчиняющиеся j -закону для j , принимающего значения 4,5,6. В ближайшее время планируется получить аналогичные результаты при j > 6.

1