Законы нуля или единицы для случайных дистанционных графов тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат наук Попова Светлана Николаевна

• Попова Светлана Николаевна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Попова Светлана Николаевна

Лемма

Обозначения некоторых множеств матриц

3.5.2 Утверждения про особенные наборы произвольного порядка

3.5.3 Утверждения про особенные 3-наборы

3.5.4 Утверждения про особенные 4-наборы

3.5.5 Утверждения про особенные 5-наборы

Утверждения про особенные 5-наборы с | det H| =

Утверждения про особенные 5-наборы с | det H| =

3.6 Доказательства теорем

3.7 Доказательства утверждений

3.7.1 Доказательства утверждений про особенные наборы произвольного порядка

3.7.2 Доказательства утверждений про особенные 3-наборы

3.7.3 Доказательства утверждений про особенные 4-наборы

3.7.4 Доказательства утверждений про особенные 5-наборы

3.7.5 Доказательства лемм

Список литературы

Список основных обозначений

N — множество натуральных чисел;

— множество натуральных чисел, кратных к; Ъ — множество целых чисел; Ъ+ — множество целых неотрицательных чисел; О — множество рациональных чисел; К — множество действительных чисел; В (К) — а-алгебра борелевских подмножеств К; |А| (или $А) — мощность конечного множества А; [а] — целая часть числа а; НОК — наименьшее общее кратное;

а|ь — свойство «а делит 6», т.е. число а является делителем числа 6; I(Е) — индикатор события Е;

ЕХ — математическое ожидание случайной величины X; ЭХ — дисперсия случайной величины X;

а(Х) — сигма-алгебра, порожденная случайной величиной X, т.е. множество {{ш : X(ш) е В} : В е В(Ш)};

(х, у) — евклидово скалярное произведение векторов оу;

норма вектора х в евклидовом пространстве;

V(О) — множество вершин графа О;

Е(О) — множество ребер графа О;

■у(О) — количество вершин графа О;

е(О) — количество ребер графа О;

а(О) - количество автоморфизмов графа О;

О|у — подграф графа О, индуцированный на множество V;

О \ Ь — предикат, истинный тогда и только тогда, когда граф О обладает свойством Ь;

/(Ж) = о(д(Ж)) — для любого числа с > 0 существует такое число N0, что для любого N > Ж0 выполнено неравенство |/(Ж)| < с|д(Ж)|;

/ (Ж) = 0(д(Ж)) — найдется такое число С > 0, что для люб ого N е N выполнено неравенство |/(Ж)| < С|д(Ж)|;

/(Ж) = 0(д(Ж)) — найдутся такие числа с, С > 0, что для любого Ж е N выполнены неравенства с|д(Ж)| < |/(Ж)| < С)|.

/(п) = 0(д(п)), если существуют такие положительные числа С1, С2, п0, что при всех натуральных п > п0 выполнено С1д(п) < ](п) < С2д(п),

/ (п) = (п)), если существуют такие положител ьные числа С1,п0, что при всех натуральных п > п0 выполне но f (п) > С1д(п).

Введение диссертации (часть автореферата) на тему «Законы нуля или единицы для случайных дистанционных графов»

Введение

Актуальность темы исследования и степень ее разработанности

Изучением асимптотики вероятностей свойств первого порядка случайного графа занимались П. Эрдеш и А. Реньи (см. [33]), Ю.В. Глебе к и П. Д.И. Коган, М.И. Лиогонький и В.А. Таланов (см. [3]), Р. Фагин (см. [34]), А. Бласс, Ю. Гуревич, Д. Козен (см. [27]), П. Колайтис, X. Промел, Б. Ротшилд (см. [43]), Дж. Спенсер и С. Шелах (см. [48], [50]), Дж. Спенсер, Г. Тардош, Л. Тома и Т. Лучак (см. [45], [46], [52], [53]), П. Колайтис и М. Варди (см. [44] М. МкАртур (см. [47]), Р.Х. Гильман, Ю. Гуревич и А. Мясников (см. [36 и др. Более подробную историю изучения асимптотики вероятностей свойств первого порядка можно найти в [10], [30], [31], [39], [50], .

Первый закон нуля или единицы для свойств первого порядка случайного графа в модели Эрдеша и Реньи был доказан в 1969 году Ю.В. Глебским, Д.И. Коганом, М.И. Лиогоньким и В.А. Талановым (независимо в 1976 году Р. Фагиным). Ими было установлено, что если L — свойство первого порядка, а P(L) — количество графов из Qn5 обладающих этим свойством, где Qn ~ множество всех графов без петель и кратных ребер на множестве вершин {1,..., N}, то либо

, P (L) lim р^ = 1,

м^ж |QM |

либо

P(L) lim = 0.

м^ж |Qn |

Иными словами, если вероятность ребра в модели Эрдеша-Реньи равна 1/2, то для любого свойства первого порядка либо с вероятностью, стремящейся к 1, случайный граф обладает этим свойством, либо с вероятностью, стремящейся к 1, не обладает. В [49] этот результат был распространен на класс функций p(N), удовлетворяющих следующему условию:

Va > 0 min(p, 1 - p)Na ^ ж, N ^ ж. (1)

В 1988 году Дж. Спенсеру и С. Шел а удалось расширить этот класс функций (см. [48]). Они доказали, что для p = Nгде a £ R \ Q, закон нуля или единицы также справедлив. Если же a £ (Q П (0,1]) U{1 + 1/k|k £ N},

то случайный граф не подчиняется закону нуля или единицы. При а > 1, а Е {1 + 1/k|k Е N}, случайный граф подчиняется закону нуля или единицы. В работе [43] были получены законы нуля или единицы для графов, свободных от полных подграфов данного размера. В 2007 году Ю. Гуреви-чем, Р. Гилманом и А. Мясниковым был доказан закон нуля или единицы для графа с бесконечным количеством вершин (см. [36]).

Пусть N Е N 0 < Р < 1. Рассмотрим множество QN = {G = (VN, E)} всех неориентированных графов без петель и кратных ребер с множеством вершин VN = {1,..., N}. Случайный граф Эрдеша-Реньи — это случайный элемент G(N,p) со значениями во множестве Qn и распределением Pn,p на

Fn = 2Qn ,

определенным формулой

Pn,p(G)= p|E|(1 - p)cN-|E|.

Изучение случайных графов началось после того, как П. Эрдеш установил, что «вероятностный метод» (см. [1], [12], [26]) помогает решать многие задачи экстремальной теории графов. С использованием «вероятностного метода» Эрдеш доказал, что для любых натуральных чисел g > 3 и k > 3 существует граф с хроматическим числом k и циклом наименьшей длины g. Вероятностный метод использовали также Р. Пэли, А. Зигмунд, Дж. Литтлвуд, А. Оф-форд и другие. Вероятностные свойства некоторых комбинаторных структур изучали еще в 1940 году М. Кендалл и Б. Бабинтон-Смит. В 1943 году Т. Селе впервые применил «вероятностный метод» к экстремальным задачам комбинаторики. По случайным графам в конце 50-х годов XX века было написано несколько работ, среди них наиболее известны статьи Г.В. Форда и Г.Е. Уленбека (1956 год), E.H. Гильберта (1957 год), Т.Л. Остина, P.E. Фэйги-на, В.Ф. Пенне и Дж. Риордана (1959 год) и П. Эрдеша и А. Реньи (1959-1960 года, см [33]).

Пусть C — некоторый класс свойств графов. Говорят, что случайный граф G(N,p) подчиняется закону нуля или единицы для класса свойств C, если для любого свойства L из класса C вероятность того, что случайный граф G(N,p) обладает свойством L, стремится к 0 или 1 при N ^ то.

Наиболее изученным в этом направлении является класс свойств, выражаемых конечными формулами первого порядка (см. [2], [25]). Эти формулы строятся с помощью символов отношения =; логических связок —, V, Л; перемениых x,y,xi...; кванторов V, 3. Символы переменных в языке первого порядка обозначают вершины графа. Символ отношения ~ выражает свойство двух вершин быть соединенными ребром, символ отношения

= выражает свойство двух вершин совпадать. Обозначим черезP множество функций p = p(N), для которых случайный граф Эрдеша-Реньи подчиняется закону нуля или единицы для класса свойств первого порядка. Класс свойств первого порядка обозначим через L. Как уже было сказано выше, если для p = p(N) справедливо соотношение (1), Top G P. Кроме того, все функции p = N-а, a G R \ Q, также принадлежат P. Разумеется, p =1 — N—а G P, если a G R \ Q.

Формулы второго порядка отличаются от формул первого порядка возможностью квантификации общности и существования не только над атомами, но и над предикатами. Примером свойства второго порядка служит связ-

p=

нуля или единицы для свойств второго порядка случайного графа Эрдеши

p

1

Монадический язык является языком второго порядка, в котором помимо предикатов = добавлен унарный предикат Gx, который означает принадлежность множеству X, по которому осуществляется квантификация. При p = const случайный граф G(n,p) не подчиняется монадическому закону нуля или единицы (см. [42]). При a G (0,1) для случайного графа G(n,n—а) также не выполнен монадический закон нуля или единицы (см. [55]). Можно

показать, что при р = п-а, где а £ (1 + щ, 1 + у) для некоторого I £ М, случайный граф С(п, п-а) подчиняется монадическому закону нуля или единицы.

Огромное количество работ посвящено и другим интересным задачам, связанным с исследованиями случайного графа G(N,p). П. Эрдеш, А. Репьи, К. Шургер, Б. Боллобаш, 3. Палка, А.Д. Барбур и др. внесли значительный вклад в изучение распределения малых подграфов в случайном графе. Распределением количества деревьев занимались П. Эрдеш, А. Репьи. Б. Боллобаш, А.Д. Барбур и др. Вопросам, касающимся связности случайного графа, посвящены работы E.H. Гильберта, Т.Л. Остина, П. Эрдеша, А. Реньи, В.Е. Степанова, И.Н. Коваленко, Г.И. Ивченко, И.В. Медведева, Б. Боллобаша и др. Поиском гигантской компоненты и определением ее размера занимались Т. Лучак, Дж. Вирман, Б. Боллобаш, П. Эрдеш, А. Реньи и др. Условия, при которых случайный граф является гамильтоновым, были исследованы в работах И. Палясти, В.А. Перереплика, Дж.В. Муна, Е.М. Райта, Дж. Комлоша, Е. Семереди, Л. Поша, А.Д. Коршунова и др. Длину максимального пути для p = c/N изучали М. Айтаи, Дж. Комлош, Е. Семереди, В.Ф. де ла Вега, Б. Боллобаш, Т.И. Фенне, A.M. Фриз и др. В работах А.Дж. Хоффмана, P.P. Синглетона, P.M. Дэмерелла, Е. Бэннэя,

Т. Ито, Х.Д. Фридмана, П. Эрдеша, А. Реньи, Б. Боллобаша и др. изучено распределение диаметра случайного графа.

Помимо описанных моделей случайных графов изучались и многие другие. Модель случайного графа О(Ж, Ы) то своим свойствам похожа на О(Ж,р). Пусть Ы — натуральное число из отрезка [1, С^], а — множество всех

графов О = (Уж, Е) с условием | Е | = Ы. Тогда случайным графом О(Ж, Ы) называется случайный элемент с равномерным распределением на множестве Многие авторы, исследовавшие случайный графО(Ж,р), изучали также и случайный граф О (Ж, Ы) и получили для пего схожие результаты. Случайный дистанционный граф и граф О(Ж,р) являются частным случаем случайного графа О(Ж, {р^,^2е{1,...,ж})• Если при определении случайного графа считать, что некоторые пары вершин соединены с различными вероятностями, т.е. ребро {жг1, Жг2}, 1 < ¿1, ¿2 < Ж, проведено с вероятностью е [0,1], то будем обозначать такой граф О(Ж, {р^2}^1,^2е{1,...,ж})- Одним из важнейших примеров этого случайного графа является случайный граф где = (Уж, ) — неориентированный граф на Ж вершинах без петель и кратных ребер. А именно, О(^ж,р) = О(Ж, {р^г2}«1,г2е{1,...,ж}), если

} еЕж;

Рг1г2 I 0, , } е Еж.

Случайный дистанционный граф — это случайный граф О(^жгде _ некоторый дистанционный граф. В данной работе мы будем рассматривать случайные графы О(^ж, р), где в качестве графов ^ж будем брать различные дистанционные графы, задаваемые некоторыми наборами параметров.

Рассмотрение дистанционных графов мотивировано классической задачей комбинаторной геометрии о хроматическом числе пространства (см. [14] и [15]). Впервые полный дистанционный граф в геометрическом контексте рассмотрели в 1981 году П. Франкл и Р.М. Уилсон. С помощью этого графа они показали, что хроматическое число пространства растет экспоненциально (см. [35]). В 1991 году Дж. Кап и Г. Калии применили результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том, что всякое ограниченное неодноточечное множество в может быть разбито на п + 1 часть меньшего диаметра (см. [14] и [41]). Таким образом, изучение внутренней структуры дистанционного графа и его подграфов играет исключительно важную роль. Сейчас с исследованием дистанционных графов связаны одни из самых широко изучаемых разделов комбинаторной геометрии (см. [14], [15], [28]). Также дистанционные графы связаны с исследованием равновесных кодов с запрещенными расстояниями (см. [13]).

Упомянем еще одну модель случайного графа, случайный регулярный граф. Пусть задано число г £ N причем г < N — 1 и гХ четно. Пусть, кроме того, (Х) — множество всех г-регулярных графов на множестве вершин VN. Тогда случайный элемент Ог (Х), имеющий равномерное распределение на

(Х), называется случайным регулярным графом. Эта модель менее изучена, чем С(Х,р) и М), так как получение короткой асимптотической формулы для числа г-регулярных графов на N вершинах является сложной задачей. В 1960 г. Р. Рид установил точную формулу для этого числа. Изучением случайных регулярных графов занимались Ф. Харари, Е.М. Палмер, Е.А. Бендер, Е.Р. Кэнфилд, А. Бекеши, Р. Бекеши, Дж. Комлош, Б. Болло-баш.

Цель работы. Цель данной диссертации состоит в решении следующих

задач: исследовать закон нуля или единицы для последовательностей случайных дистанционных графов с вершинами в {—1, 0,1}п; найти условия, при которых для случайного дистанционного графа с вершинами в Ъп выполнен закон нуля или единицы или можно выделить подпоследовательность, подчиняющуюся закону нуля или единицы; исследовать предельные вероятности свойств первого порядка для случайного графа с вершинами в булевом кубе.

Научная новизна. Все результаты, полученные в работе, являются новыми.

Теоретическая и практическая значимость работы

Диссертация носит теоретический характер. Полученные результаты дают возможность рассчитывать и оценивать предельные вероятности существования в графе определенных структур. Доказанные в работе законы нуля или единицы имеют ценность для задач о выразимости графовых свойств. Кроме того, изучение случайных дистанционных графов представляет ценность для задач комбинаторной геометрии.

Методология и методы исследования

Для доказательства основных результатов диссертации мы использовали разнообразную технику. Так, установление законов нуля или единицы потребовало не только применения теоремы Эренфойхта (см. [32], [39], [54] и раздел 1.1) и использования свойства полного расширения, но и разработки выигрышной стратегии Консерватора, основанной на понятии особенного набора вершин. Понятие особенного набора вершин также играет ключевую

роль при построении свойств первого порядка, для которых не выполнен как классический, так и расширенный закон нуля или единицы. При опровержении законов нуля или единицы были использованы методы теории вероятностей (в том числе метод моментов) для оценки асимптотических вероятностей свойств случайного дистанционного графа. При доказательстве законов нуля или единицы для случайных дистанционных графов, а также при изучении особенных наборов были доказаны некоторые вспомогательные леммы об удовлетворяющих некоторым неравенствам целочисленных решениях систем линейных уравнений с целыми коэффициентами.

Положения, выносимые на защиту

В диссертации получены новые результаты, которые состоят в следующем:

1. Найдены условия на параметры случайного дистанционного графа с вершинами в {-1, 0,1}п, при которых случайный граф подчиняется закону нуля или единицы.

2. Найдены условия на параметры случайного дистанционного графа с вершинами в {—1,0,1}п, при которых существует подпоследовательность случайных дистанционных графов, подчиняющаяся закону нуля или единицы.

3. Найдены условия на параметры случайного дистанционного графа с вершинами в при которых случайный граф подчиняется закону нуля или единицы.

4. Найдены условия на параметры случайного дистанционного графа с вершинами в при которых существует подпоследовательность случайных дистанционных графов, подчиняющаяся закону нуля или единицы.

5. Опровергнут расширенный закон нуля или единицы для случайных графов с вершинами в булевом кубе.

6. Найдены условия, при которых последовательность случайных графов с вершинами в булевом кубе подчиняется ^'-закону нуля или единицы (расширенному ^'-закону нуля или единицы), где; < 6.

Степень достоверности и апробация результатов

Все результаты строго доказаны.

По теме диссертации были сделаны доклады на следующих научных семинарах:

— Научный семинар «Вероятностные методы в комбинаторике» на кафедре математической статистики механико-математического факультета МГУ, под руководством профессора A.M. Райгородского (2013-2017 гг., неоднократно).

— Научный семинар по теории кодирования в ИППИ им. Харкевича, под руководством д.ф.-м.н. Л.А. Бассалыго РАН (2013г.).

— Кафедральный научно-исследовательский семинар на кафедре дискретной математики в МФТИ, под руководством профессора A.M. Райгородского (2014 г.).

Результаты диссертации докладывались на следующих конференциях: «RSA 2013» (Познань, Польша, 2013), «МФТИ-56» (Москва, 2013), «Ломоносов-2014» (Москва, 2014), «Workshop on extremal graph theory» (Москва, 2014), «Summit:240» (Будапешт, Венгрия, 2014), международный семинар "Теоретико-групповые методы исследования физических систем" (Сыктывкар, 2017).

Публикации

Результаты диссертации опубликованы в 9 работах автора (4 из которых входят в перечень ВАК), список которых приведен в конце диссертации. Все работы написаны без соавторов.

Благодарности

Автор признателен профессору Андрею Михайловичу Райгородскому за постановку задач и неоценимую помощь в работе. Автор также благодарен к.ф.-м.н. Максиму Евгеньевичу Жуковскому за полезные замечания.

Краткое содержание работы

Данная работа состоит из трех глав, которые посвящены изучению закона нуля или единицы (а также некоторых его ослабленных вариантов) для различных моделей случайных дистанционных графов.

Впервые закон нуля или единицы в контексте формул первого порядка для случайных дистанционных графов был исследован М.Е. Жуковским. Оказалось, что для рассмотренной им модели случайного дистанционного графа закон нуля или единицы не выполняется. Однако было доказано, что существует подпоследовательность случайных дистанционных графов, которая подчиняется закону нуля или единицы. Случайные дистанционные графы, рассмотренные М.Е. Жуковским, являются частным случаем случайных дистанционных графов с вершинами в { —1,0,1}п, зависящих от некоторого набора параметров, которые изучаются в первой главе данной работы. Оказалось, что для случайного дистанционного графа с вершинами в {-1,0,1}п удается найти нетривиальные условия на параметры, при которых он подчиняется закону нуля или единицы. Кроме того, в первой главе приводятся условия на параметры, при которых можно выделить подпоследовательность случайных дистанционных графов, подчиняющуюся закону нуля или единицы. Во второй главе результаты первой главы переносятся на гораздо более общую модель случайных дистанционных графов — модель случайных дистанционных графов с вершинами Ъп. В третьей главе изучаются ослабленные варианты закона нуля или единицы (в параграфе 3.2 будет объяснено, что именно подразумевается под такими ослабленными вариантами). При изучении закона нуля или единицы для случайных дистанционных графов возникла гипотеза, что когда закон нуля или единицы не выполнен (т.е. вероятности свойств первого порядка случайного графа не стремятся к 0 или 1), верно более слабое утверждение: все частичные пределы последовательности этих вероятностей равны 0 или 1 (назовем это расширенным законом нуля или единицы). Эта гипотеза была опровергнута, что потребовало глубокого изучения свойств случайного дистанционного графа. Также в третьей главе изучаются законы нуля или единицы для формул первого порядка с кванторной глубиной, ограниченной некоторым числом ; (так называемый ^'-закон нуля или единицы). Даются условия, при которых имеет место один из трех возможных случаев: выполнен ^'-закон нуля или единицы; ;-закон нуля или единицы не выполнен, но выполнен расширенный ^'-закон нуля или единицы; не выполнен расширенный ;-закон нуля или единицы.

Гл яв ^^

Закон нуля или единицы для случайных дистанционных графов с вершинами в { — 1, 0,1}п

В этой главе мы сформулируем определения свойств графов первого порядка, закона нуля или единицы и игры Эренфойхта, инструмента, применяющегося для доказательства закона нуля или единицы. Все эти объекты мы будем использовать и в главах 2 и 3. Основным результатом главы являются теорема 1.4.1, в которой даются условия, при которых случайный дистанционный граф с вершинами в {—1,0,1}п подчиняется закону нуля или единицы, и теорема 1.4.2, в которой приводятся условия, при которых существует подпоследовательность, подчиняющаяся закону нуля или единицы. Результаты данной главы сформулированы и доказаны в [57].

1.1 Закон нуля или единицы

Дадим основные определения. Пусть N £ М,р : N ^ [0,1], — множество неориентированных графов без петель и кратных ребер с множеством вершин {1,...,Х}. Случайным графом Эрдеша-Реньи 0(Х,р) (см. [1], [11], [16], [26], [39]) называется случайный элемент со значениями в множестве с распределением Ря,р на где

^ = 2^, Ря,р (С) = р|Е| (1 — р)^—|Е |,

Е — множество ребер графа С. Иными словами, любые две различные вер-

р

всех остальных пар вершин (см. [1], [11], [26], [33], [39], [45]).

Свойства графов первого порядка определяются формулами первого порядка (см. [2], [25]), которые строятся с помощью символов отношения^, =, логических связок —, V, Л, перемениых х, у,..., кванторов V, 3. Символ

отношения ~ выражает свойство двух вершин быть соединенными ребром, символ отношения = выражает свойство двух вершин быть совпадающими.

Случайный граф Эрдеши Репьи подчиняется закону нуля или единицы, если для любого свойства первого порядка L выполнено

lim PNp(L) = 0 или lim PNp(L) = 1,

где через Pn,p(L) обозначается вероятность события, что случайный граф G(N,p) обладает свойством L.

В 1969 году Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький и В.А. Таланов получили следующий закон нуля или единицы, который в 1976 году был независимо доказан Р. Фагиным.

Теорема 1.1.1 ([3], [34]) Пусть p(N) = p^dep е [0,1]. Тогда, случайный граф G (N,p) подчиняется закону нуля, или, единицы.

Дж. Спенсер получил следующее обобщение этой теоремы.

Теорема 1.1.2 ([49]) Пусть min(p, 1 — p)Na ^ то при N ^ то для любого а > 0. Тогда, случайный гpaфG(N,p) подчиняется закону нуля, или, единицы.

С. Шелах и Дж. Спенсер расширили класс функций p(N), для которых случайный граф G(N,p) подчиняется закону нуля или единицы.

Теорема 1.1.3 ([48]) Пусть p(N) = N—а, где 0 < а < 17 а — иррациональное. Тогда, случайный граф G (N,p) подчиняется закону нуля, или, единицы.

1.2 Случайные дистанционные графы с вершинами в

{-1, 0,1}п

Введем теперь модель случайного дистанционного графа с вершинами в {—1,0,1}П которая будет рассматриваться в данной главе. Пусть а, Ь : N ^ 0>+, с : N ^ ^ ^ ^^^^^^^^^^ функции. Пусть {п*}^ _ последовательность, составленная из всех элементов множества {п : а(п), Ь(п), с(п) е Z}, упорядоченных по возрастанию. Определим граф Оп = (Уп, Еп), в котором

Уп = {V = (V1,...,^п) : V е {-1,0,1}, |{г е {1,... ,п} : V = 1}| = а, |{г е {1,... ,п} : V = -1}| = Ь, |{г е {1,... ,п} : V = 0}| = 6 = п - а - Ь},

Еп = {{и, V} е Уп х Уп : (и, V) = с},

где (u, v) — евклидово скалярное произведение. Такие графы называются дистанционными, поскольку их ребра соответствуют парам вершин, которые отстоят друг от друга на некоторое наперед заданное расстояние (см. [28]). При разных значениях параметров такие графы использовались в работах

[15], [17]—[20] для отыскания нижних оценок хроматических чисел различных пространств, а также в работах [21]—[24] для получения нижних оценок числа Борсука и построения контрпримеров к гипотезе Борсука.

Случайный дистанционный граф с вершинами в {—1,0,1}n ^ это случайный элемент G(Gn,p) со значениями в множестве с распределением PanP па FGn, где

П üGn = {G = (V,E) : V = Vn,E С En},

Fcn = 2^, PGn ,p(G) = p|E|(1 — p)|En|—|E|.

Частный случай этой модели с а = d = n/2, b = 0, c = n/4 изучался в [5]-[8],

[16].

Последовательность случайных дистанционных графов {G(Gni , p)}jподчиняется закону нуля или единицы, если для любого свойства первого порядка L

lim pGn4 ,p(L) = ^и lim pGn4 ,p(L) = 0.

, ij j^TO ij

Будем говорить, что случайный граф 0(Сп,р) подчиняется закону нуля или единицы, если этому закону подчиняется последовательность {0(Сп ,р)}«£м-Впервые законы нуля или единицы для случайных дистанционных графов были исследованы в работах М.Е. Жуковского [5]-[8], где рассматривался случайный граф 0(Сп,р) с а = ^ = п/2, Ь = 0,с = п/4. Оказалось (см. [5]), что закон нуля или единицы для такого случайного дистанционного графа не выполнен. Однако в [8] были найдены подпоследовательности случайных дистанционных графов, подчиняющиеся закону нуля или единицы.

1.3 Методы доказательства закона нуля или единицы

Доказательство закона нуля или единицы для последовательностей случайных графов основывается на теореме Эренфойхта, связывающей справедливость этих законов с существованием выигрышной стратегии второго игрока в игре Эренфойхта (см. [1], [16]). В этой игре ЕНК(С, Н, ¿) на графах С и Н с фиксированным числом раундов £ участвуют два игрока Новатор и Консерватор. Каждый раунд состоит из двух частей. В ^'-м раунде сначала Новатор выбирает вершину х^ £ V(С) или же у^ £ V(Н). Затем Консерватор выбирает вершину в другом графе. Если Новатор выбирает, скажем, вершину х^ £ V (С) совпадающую с некоторой в ершиной х«, выбранной ранее в

г-м раунде (г < ^ то Консерватор должен выбрать вершину у; е V(Н). К концу £-го раунда выбрано по £ вершин го каждого графа. Пусть х1,... , х — вершины, выбранные из V(О) у1,..., у — вершины, выбранные из V(Н), где х; и у; — вершины, выбранные в г-м раунде. Консерватор выигрывает тогда и только тогда, когда индуцированные подграфы на выбранных вершинах являются изоморфными, т.е. при всех 1 < г < ] < £ выполнено, что {х^х^} е Е(О) тогда и только тогда, когда {у*,у^} е Е(Н).

Из теоремы Эренфойхта (см. [1], [16]) следует, что последовательность случайных графов {^(Оп.,р)}^ подчиняется закону нуля или единицы тогда и только тогда, когда для любого £ е N

г /Консерватор выигрывает в \

^ 'р х 'р ^ ЕНЩ£ (Опг ,р), а (Оп, ,р),£)У = 1

где Рап. р х р — прямое произведение вероятностных мер.

г 3

В [3] для доказательства закона нуля или единицы для случайного графа Эрдеша - Реньи, а, точнее, для доказательства существования выигрышной стратегии Консерватора, было предложено свойство полного расширения. Это свойство также было использовано при доказательстве законов нуля или единицы для последовательностей случайных дистанционных графов в работах [5]—[8].

Граф О обладает свойством полного расширения уровняЬ, если для любых к, I е таких, что к+1 < £, для любых различных вершин и1,..., , ^>1,... , V/ существует такая вершина х, та о {х, м,} е Е (О) для каждого г е {1,..., к} и {х, г^-} е Е(О) для каждого ] е {1,..., /}.

Известно (см. [1]), что если графы О и Н обладают свойством полного расширения уровня £ - 1, то у Консерватора есть выигрышная стратегия в игре ЕНЩО,Н,£).

При доказательстве того, что случайный дистанционный граф {а(Оп ,р)}^ обладает свойством полного расширения уровня £ с асимптотической вероятностью 1, мы будем использовать следующее свойство последовательностей графов. Скажем, что последовательность графов {Опобладает свойством Ь^, где £ е N если существует такое число в > 0 и функция ^>(п, £) = |в) чт0 Для любых вершин V!,..., V е в графе Оп есть не менее ^>(п,£) вершин, соединенных ребрами с v1,..., при всех п е

1.4 Основные результаты

Пусть функция р : N ^ [0,1] такова, что шт(р(п), 1 - р(п))|^|^ ^ то при п ^ то для любого V > 0. Основные результаты данной главы опи-

сывают, для каких функций а(п),Ь(п),с(п),^(п) случайный граф 0(Сп,р) подчиняется закону 0 или 1, а для каких нет.

В приводимых ниже теоремах накладываются ограничения не на функции а(п) и Ь(п), а только на разность а(п) — Ь(п), при этом предполагается, что а(п) и Ь(п) целые, если а(п) — Ь(п) целое.

Сформулируем условия, при которых случайный дистанционный граф подчиняется закону 0 или 1.

Теорема 1.4.1. Пусть а — Ь = о(п), с = о(а — Ь), а = 0(п), ¿(п) ^ то при п ^ то и для любого т £ N существует такое г0 £ N что при г > г0 а(п«) — Ь(п«) п с(п«) делятся на т. Тогда случайный граф 0(Сп,р) подчиняется закону 0 или 1.

В следующей теореме описывается довольно широкий класс функций а (п), Ь(п), с(п), ¿(п), для которых можно найти последовательность, подчиняющуюся закону 0 или 1. При этом случайный граф может и не подчиняться закону О или 1.

Теорема 1.4.2. Пусть при, всехп £ N выполнено а(п) — Ь(п) = апп+/(п), с(п) = «п п + д(п)7 где ап = а + 7п; а,7п £ 0,0 <а< 1,7п ^ 0 пр ип ^ то7 / (п),д(п) £ / = °(тпп),д = о(7пп), ¿(п) ^ то пр и п ^ то. Пусть, кроме того, последовательность {п^. такова, что для любого т £ N существует такое ]0, что при ] > ]0 числа НОД(ащ п^., а^ п^.), a(nij) — Ь(п^.) и

у j

c(nij) делятся на т. Тогда последователь ность {0 (Сп. подчиняется,

закону 0 или, 1.

Поясним формулировку теоремы 1.4.2. Из приведенных в ней асимптотик для функций а(п) — Ь(п) и с(п) следует, что а(п) — Ь(п) = ап + о(п), с(п) = а2п + о(п). В теореме 1.4.2 накладываются более сильные ограничения на функции а(п), Ь(п), с(п). А именно, даются условия а(п) — Ь(п) = (а + 7п)п + /(п) и с(п) = (а + 7п)2п + д(п), где 7пп растет медленнее п, а ](п) и д(п) растут медленнее, чем 7пп. Отметим также, что параметр а обязан быть рациональным.

Список литературы диссертационного исследования кандидат наук Попова Светлана Николаевна, 2018 год

Список литературы

[1] Н. Алон, Дж. Спенсер, Вероятностный метод., Москва, БИНОМ. Лаборатория знаний, 2007.

[2] И.К. Верещагин, А. Шень, Языки и исчисления, Москва, МЦНМО, 2000.

[3] Ю.В. Глебе к и П. Д.И. Коган, М.И. Лиогонький, В.А. Таланов, Объем и доля выполнимости формул узкого исчисления предикатов, Кибернетика 2, 1969, с. 17-26.

[4] М.Е. Жуковский, Законы нуля или единицы для формул первого порядка с ограниченной кванторной глубиной. Доклады Академии Наук. 2011. Т. 436. № 1. С. 14 - 18.

[5] М.Е. Жуковский, Ослабленный закон "нуля или единицы" для случайных дистанционных графов. Вестник РУДН. 2010. Т. 2. № 1. С. 11 - 25.

[6] М.Е. Жуковский, Ослабленные законы "нуля или единицы" для случайных дистанционных графов. Доклады Академии Наук. 2010. Т. 430. №3. С. 314-317.

[7] М.Е. Жуковский, Ослабленный закон нуля или единицы для случайных дистанционных графов. Теория вероятностей и ее применения. 2010. Т. 55. № 2. С. 344 - 349.

[8] М.Е. Жуковский, О последовательности случайных дистанционных графов, подчиняющейся закону нуля или единицы Проблемы передачи информации. 2011. Т. 47. № 3. С. 39 - 57.

[9] М.Е. Жуковский, "Ослабленный закон нуля или единицы для последовательностей случайных дистанционных графов" Матем. сборник, 203:7 (2012), 95 - 128.

[10] М.Е. ЖУковский, А.М. Райгородский, Случайные графы: модели и предельные характеристики, Успехи математических наук, 2015, 70(1):35-88.

[11] В.Ф. Колчин, Случайные графы, 2-е издание, Физматлит, Москва, 2004.

[12] H.H. Кузюрин, Вероятностные приближенные алгоритмы в дискретной оптимизации, Дискретн. анализ и исслед. опер., сер. 2, 2002, 9(2): 97—114.

[13] Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, Москва, «Связь», 1979.

[14] A.M. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, 2007.

[15] A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи Матем. Наук, 2001, 56(1): 107-146.

[16] A.M. Райгородский. Модели случайных графов. М.: МЦНМО, 2011.

[17] A.M. Райгородский. О хроматических числах сфер в евклидовых пространствах. Доклады РАН. 2010. Т. 432. №2. С. 174 - 177.

[18] A.M. Райгородский. О хроматическом числе пространства clq-нормой. Успехи матем. наук. 2004. Т. 59. №5. С. 161 - 162.

[19] A.M. Райгородский, И.М. Шитова. О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями. Матем. сборник. 2008. Т. 199. №4. С. 107 - 142.

[20] A.M. Райгородский. О хроматическом числе пространства с двумя запрещенными расстояниями. Доклады РАН. 2006. Т. 408. №5. С. 601 -604.

[21] A.M. Райгородский. О размерности в проблеме Борсука, Успехи матем. наук. 1997. Т. 52. №6. С. 181 - 182.

[22] A.M. Райгородский. Об одной оценке в проблеме Борсука, Успехи матем. наук. 1999. Т. 54. №2. С. 185 - 186.

[23] A.M. Райгородский. Вокруг гипотезы Борсука, Итоги науки и техники Серия "Современная математика". 2007. Т. 23. С. 147 - 164.

[24] A.M. Райгородский. Контрпримеры, к гипотезе Борсука, на сферах малого радиуса. Доклады РАН. 2010. Т. 434. N2. С. 161 - 163.

[25] В.А. Успенский, Н.К. Верещагин, В.Е. Плиско, Вводный курс математической логики, МГУ, Физматлит, Москва, 1997.

[26] В. Bollobâs, Random Graphs, 2nd Edition, Cambridge University Press, 2001.

[27] A. Blass, Y. Gurevich, D. Kozen, A zero-one law for logic with a fixed point operator, Inform, and Control, 1985, 67: 70-90.

[28] P. Brass, W.O.J. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

[29] J. Brenner, L. Cummings, The Hadamard Maximum Determinant Problem, Amer. Math. Monthly. 1972. V. 79. №6. P. 626-630.

[30] K.J. Compton, 0 — 1 laws in logic and combinatorics, Proc. NATO Advanced Study Institute on Algorithms and Order (I. Rival, ed.), Reidel, Dordrecht, 1988, 353-383.

[31] H.-D. Ebbinghaus, J. Flum, Finite model theory, 2nd Edition, Springer, 1999.

[32] A. Ehrenfeucht, An application of games to the completness problem for formalized theories, Warszawa, Fund. Math., 1960, 49: 121-149.

[33] P. Erdos, A. Renyi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutatö Int. Közl., 1960, 5: 17-61.

[34] R. Fagin, Probabilities in finite models, J. Symbolic Logic, 1976, 41: 50-58.

[35] P. Frankl, R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1981, 1: 357-368.

[36] R.H. Gilman, Y. Gurevich, and A. Miasnikov, A geometric zero-one law, 2007, arXiv:0706.0271.

[37] Y. Gurevich, Chapter Zero-one laws, Book Current trends in theoretical computer science, edited by G. Rozenberg and A. Salomaa, World Scientific Series in Computer Science, Volume 40, 1993.

[38] P.E. Haxell, Y. Kohayakawa, T. Luczak, Turan's extrem,a,I problem, in random graphs: forbidding even cycles, J. Combin. Theory, Ser. B, 1995, 64: 273-287.

[39] S. Janson, T. Luczak, A. Rucinski, Random Graphs., New York, Wiley, 2000.

[40] G. Kabatiansky, E. Krouk, S. Semenov, Error Correcting Codes and Security for Data Networks, Wiley and Sons, 2005.

[41] J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 1993, 29(1): 60-62.

[42] M. Kaufmann, S. Shelah, On random models of finite power and monadic logic, Discrete Mathematics, 1985, 54(3): 285-293.

[43] P.G. Kolaitis, H.J. Promel and B.L. Rothschild, Kl+l-/ree graphs: asymptotic structure and a 0-1 law, Transactions of the American Mathematical Society, 1987, 303(2): 637-671.

[44] P.G. Kolaitis, M.Y. Vardi, Innitary logics and 0-1 laws, Inform, and Computation, 1992, 98: 258-294.

[45] T. Luczak, J. Spencer, When does the zero-one law hold?, J. Amer. Math. Soc., 1991, 4: 451-468.

[46] T. Luczak, S. Shelah, Convergence in homogeneous random graphs, Random Structures and Algorithms, 1995, 6: 371-392.

[47] M. McArtur, The asymptotic behavior of L^ w on sparse random graphs, Logic and Random Structures, 1997, 33: 53-63.

[48] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc., 1988, 1: 97-115.

[49] J.H. Spencer, Threshold spectra via the Ehrenfeucht game Discrete Applied Mathematics, Discrete Applied Mathematics, 1991, Volume 30, Issues 2-3, 235-252.

[50] J.H. Spencer, The Strange Logic of Random Graphs, Number 22 in Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.

[51] J.H. Spencer, Zero-one laws with variable probability, J. Symbolic Logic, 1993, 58: 1-14.

[52] J.H. Spencer, G. Tardos, Ups and downs of first order sentences on random graphs, Combinatorica, 2000, 20: 263-280.

[53] J.H. Spencer, L. Thoma, On the limit values of probabilities for the first order properties of graphs, Contemporary Trends in Discrete Mathematics, DIMACS Series vol. 49, Amer. Math. Soc., R. Graham et. al., eds., 1999, 317-336.

[54] T. Shwentick, On Winning Ehrenfeucht Games and Monadic NP, Ann. Pure Appl. Logic, 1996, 79(1): 61-92.

[55] J. Tyszkiewicz, On Asymptotic Probabilities of Monadic Second Order Properties, Lecture Notes in Computer Science, 1993, 702: 425-439.

[56] P. Winkler, Random structures and zero-one laws, Finite and Infinite Combinatorics in Sets and Logic, N.W. Sauer, R.E. Woodrow and B. Sands, eds., NATO Advanced Science Institute Series, Kluwer Academic Publishers, Dordrecht 1993, 399-420.

[57] С.Н. Попова, Закон нуля или единицы для случайных дистанционных графов с вершинами в {—1,0,1}n, Проблемы передачи информации, 2014, 50(1) :79—101.

[58] С.Н. Попова, Законы нуля или единицы для случайных дистанционных графов с вершинами в {0,1}n, Доклады Академии Наук. 2014. Т. 458. т. с. 1 - 4.

[59] С.Н. Попова, Закон нуля или единицы для случайных дистанционных графов с вершинами в Zn, Математический сборник, 2016, 207(3): 153174.

[60] С.Н. Попова, Законы нуля или единицы для случайных дистанционных графов с вершинами в булевом кубе, Математические труды, 2016, 19(1) :10б—177.

[61] S.N. Popova, Zero-one law for random distance graphs with vertices in {—1, 0,1}n, Abstracts of Conference "Random Structures and Algorithms", Poznan, August 5-9, 2013.

[62] S.N.Popova, Zero-one law for random distance graphs, Abstracts of Conference "Lomonosov", Moscow, April 7-11, 2014.

[63] S.N. Popova, Zero-one laws for random distance graphs with vertices in {0,1}n, Abstracts of Workshop on Extremal Graph Theory, Moscow, June 6, 2014.

[64] S.N. Popova, Zero-one law for random distance graphs with vertices in Zn, Abstracts of Summit:240 Conference, Budapest, July 7-11, 2014.

[65] С.Н. Попова, k-законы нуля, или, единицы для случайных дистанционных графов, Тезисы докладов международного семинара "Теоретико-групповые методы исследования физических систем", Сыктывкар, 21-23 сентября, 2017.