Свойства первого порядка и размеры подграфов случайного графа тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Яровиков Юрий Николаевич

• Яровиков Юрий Николаевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Яровиков Юрий Николаевич

2.3 Три главные леммы

2.3.1 Лемма

2.3.2 Лемма

2.3.3 Лемма

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

3 Теорема о непредельности точки 3/5

3.1 Основной результат

3.2 Новые утверждения и конструкции

3.2.1 Построение множества

3.2.2 Вхождение графов из в произвольный граф

3.3 Три главные леммы

3.3.1 Лемма

3.3.2 Леммы 2 и

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

3.5 Некоторые финальные замечания о структуре 4-спектра

4 Размеры подграфов

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

4.2 Предварительные результаты

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

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

Заключение

Введение

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

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

Данная работа посвящена свойствам первого порядка случайного графа, а также устройству множества размеров ^-подграфов случайного графа. Теория случайных графов получила своё развитие во второй половине XX века, с тех пор как П. Эрдёш впервые использовал соображения вероятности для построения графов, обладающих определёнными свойствами [1]. С этого момента случайные графы развивались не только как инструмент для решения детерминистических задач, но и стали самостоятельной областью математики на стыке теории вероятностей и теории графов, получившей множество применений в практических сферах, таких как, например, теория сложных сетей.

Большинство утверждений в теории случайных графов носят асимптотический характер, то есть начинают иметь смысл только при достаточно большом количестве вершин. Это вызывает у исследователей особый интерес к предельным характеристикам случайных графов.

Наиболее распространенной моделью случайного графа является случайный граф Эрдёша-Реньи С(п,р), а именно, граф на п вершинах, рёбра в котором проводятся независимо друг от друга с вероятностью р. Интересны предельные вероятности того, что случайный граф С(п,р) обладает некоторым свойством Ь, при п ^ го. Бинарные характеристики графов или, проще говоря, свойства графов, с ростом количества рёбер начинают проявляться в некотором смысле внезапно. При этом, о предельной вероятности выполнения тех или иных свойств выводы удаётся сделать далеко не всегда. В 1959 году П. Эрдёш и А. Реньи установили [2], что функция р0(п) = ^ является пороговой функцией для свойства случайного графа быть связным в следующем смысле. Если р = о(р0), то вероятность того, что случайный граф С(п,р) является связным, стремится к 0. Если же, наоборот, р0 = о(р), то вероятность того, что случайный граф С(п,р) является связным, стремится к 1.

Изучение пороговых функций свойств является важнейшим направлением в теории случайных графов. В частности, в 1987 году Б. Боллобаш и А. Томасон доказали [3], что пороговая функция существует для любого монотонного свойства. Напомним, что свойство графа называется монотонно возрастающим, если для любых графов Н С С, имеющих одно и тоже множество вершин, из того, что граф Н обладает свойством Ь, следует, что граф С также об-

ладает свойством L. Аналогично определяется монотонно убывающее свойство. Отметим, что связность графа является монотонным свойством.

Важным классом свойств графов является класс свойств первого порядка, то есть свойств, которые выражаются формулами первого порядка с двумя бинарными предикатными символами: "=" и " В роли переменных выступают вершины графа, символ " =" соответствует равенству вершин, а " — смежности вершин. Формула первого порядка отличается, например, от формулы в логике второго порядка тем, что кванторы в ней могут стоять только по вершинам. Кванторная глубина формулы — это, неформально говоря, длина максимальной последовательности вложенных кванторов.

Формула первого порядка естественным образом выражает некоторое свойство первого порядка. Легко видеть, что различные формулы первого порядка могут выражать одно и то же свойство. Кванторной глубиной свойства называется минимальная возможная глубина формулы, которая задаёт данное свойство. Подробнее о формулах первого порядка см., например, в [4; 5].

Теоретические основания для изучения логики первого порядка заложил Д. Гильберт в первой половине XX века. В своём трактате 1928 года «Основы теоретической логики» [6] совместно с В. Аккерманом Гильберт изложил формализацию логики первого порядка, которая затем достигла канонического статуса. Гильбертова логика первого порядка в настоящее время является основной формализацией в математической логике и используется в современных трактовках арифметики Пеано и почти всех трактовках аксиоматической теории множеств.

Стоит упомянуть, что свойства первого порядка отличаются одной важной практической особенностью: любое свойство первого порядка является полиномиально разрешимым, то есть существует полиномиальный (по количеству вершин графа) алгоритм, определяющий, удовлетворяет ли граф данному свойству. При этом степень полинома такого алгоритма, очевидно, не превосходит кванторной глубины свойства (см. [5, Chapter 6]). Таким образом, понятие кванторной глубины является ключом к переходу от логической к вычислительной сложности.

Можно показать, что не любое свойство графа выразимо на языке первого порядка. Например, таковым не является свойство графа быть связным [7]. Классическим подходом к задаче о выразимости является подбор конечных моделей, опровергающих выразимость. Например, чтобы доказать, что свойство графа быть связным не может быть выражено формулой первого порядка кванторной глубины к, достаточно подобрать два графа, которые неразличимы никакой формулой первого порядка кванторной глубины к, но один из них связен, а другой нет. Для доказательства существования таких двух графов естественно применять вероятностный метод: можно рассмотреть две независимые реализации случайного графа с подходящей вероятностью проведения ребра и большим количеством вершин. Зафиксируем некоторый класс свойств С (например, класс всех свойств первого порядка). Неразличимость с асимптотической вероятностью

1 двух случайно и независимо сгенерированных графов никаким свойством из С эквивалентна так называемому закону нуля или единицы. Говорят, что для функции р = р(п) выполняется закон нуля или единицы в классе свойств С, если для любого свойства из С вероятность того, что случайный граф G(n,p) обладает данным свойством, стремится либо к нулю, либо к единице, с ростом числа вершин к бесконечности. Далее, говоря о законе нуля или единицы, мы будем подразумевать, что речь идёт о классе свойств первого порядка.

Первым делом можно поставить вопрос о справедливости закона нуля или единицы в случае плотного графа, то есть при р = const. Справедливость закона нуля или единицы для р = const в классе свойств первого порядка установили в 1969 году Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький и В.А. Таланов [8] и независимо в 1976 году Р. Фейгин [9]. В 1991 году Дж. Спенсер обобщил данный результат для всех таких р = р(п), что рпа ^ 0 при п ^ <х для любого а > 0 [10]. Естественный вопрос, таким образом, заключается в том, выполняется ли закон нуля или единицы для р = п~а (случай разреженного графа). Ответ был получен Дж. Спенсером и С. Шелахом в 1988 году. При иррациональном а > 0 функция р = п~а удовлетворяет закону нуля или единицы [11]. При рациональном а ситуация сложнее: закон нуля или единицы может как выполняться, так и не выполняться, в зависимости от конкретного значения а. В работе [11] Спенсер и Шелах также получили полное описание таких а, что закон нуля или

— Ы

единицы выполняется для р = п .

Несмотря на то, что нарушение закона нуля или единицы позволяет заключить существование формулы первого порядка, с положительной вероятностью различающей два независимых случайно сгенерированных графа, этот факт не позволяет найти минимальную кванторную глубину такой формулы. Рассматривая в качестве класса С все свойства первого порядка кван-торной глубины не более к, можно сформулировать fc-закон нуля или единицы. Итак, функция р = р(п) удовлетворяет к-закону нуля или единицы, если для любого свойства первого порядка кванторной глубины не более к вероятность того, что случайный граф G(n,p) обладает данным свойством, стремится либо к нулю, либо к единице. Справедливость fc-закона нуля или единицы для разреженного случайного графа (р = п~а) и различных значений к, а изучалась в работах [12—17].

Поговорим о втором классе задач, решаемых в данной диссертации. Речь пойдет про классическое направление экстремальной комбинаторики, связанное с теорией Рамсея [18—21]. Число Рамсея R(s\,..., Sk) — это минимальное такое N, что при любой раскраске ребер полного графа на N вершинах в к цветов найдётся цвет г, для которого в графе присутствует клика (то есть множество вершин, попарно соединённых ребрами) на Si вершинах, все ребра которой раскрашены в цвет г. Нахождение точных значений (или даже асимптотик) для чисел Рамсея в общем и многих частных случаях представляется очень сложной задачей. Таким образом, получение

нижних и верхних оценок чисел Рамсея в некоторых частных случаях (например, при г = 2) является целью многочисленных работ [22—26]. Отметим, что при к = 2 удобно говорить не о размерах одноцветных клик в полном графе, покрашенном в два цвета, а о кликах и независимых множествах (то есть множествах вершин, попарно не соединенных ребром) в произвольном графе.

Впервые вероятностный метод для нахождения нижних оценок для чисел Рамсея применил П. Эрдёш в 1947 году [27]: он показал, что с ростом s к бесконечности почти любой граф на не более чем 2s/2 вершинах не содержит ни клики, ни независимого множества размера s. Насколько нам известно, лучшая на текущий момент нижняя оценка для R(s,s) получена Дж. Спенсером [28] с использованием метода П. Эрдёша, модифицированного с помощью локальной леммы Ловаса [29], и составляет

У-2 S2s/2(1 + 0(1)).

е

Графы, для которых и число независимости, и кликовое число имеют логарифмический размер по отношению к количеству вершин, называются рамсеевыми. Более формально, граф G на п вершинах называется с-рамсеевым для некоторой константы с > 0, если и размер его максимальной клики, и его число независимости ограничены сверху величиной с log п. П. Эрдёш, Р. Фаудри и В. Шош выдвинули гипотезу об устройстве с-рамсеевых графов [30; 31]. Рассмотрим множество

£(G,k) = {\Е(Н)\ : Н ^ G,v(H) = к]

— множество размеров (количеств рёбер) всех возможных индуцированных подграфов на к вершинах графа G. Гипотеза о с-рамсеевых графах заключается в следующем. Для любого с > 0 найдется такое b > 0, что справедливо следующее утверждение. Если граф G на п вершинах является с-рамсеевым, то

£ \£(G,k)\ > bn5/2.

к^п

Данная гипотеза была подтверждена М. Кваном и Б. Судаковым в 2019 году [32]. Доказательство гипотезы представляет собой кульминацию серии важных результатов, к которым мы обратимся в следующем разделе. Структуре множества £(G, к) для случайного графа G и различных к посвящены работы [33], [34].

Степень разработанности темы

Остановимся более подробно на исследуемых нами объектах. Биномиальный случайный граф G(n,p) — это случайный элемент множества всех простых графов

{G =(М = {1,...,п], £)] ,п е N

с распределением Р(С(п,р) = 0) = р|£|(1 — р)(2)-|£|. Иначе говоря, каждое ребро проводится с вероятностью р Е [0,1] независимо от остальных рёбер.

Пороговые вероятности выполнения свойств графов изучались, помимо прочего, в [3; 35; 36]. Как уже упоминалось, для монотонных свойств вопрос о существовании пороговой вероятности свойств решён полностью.

Теорема 1 (Б. Боллобаш, А. Томасон, 1987, [3]). Пусть Ь — некоторое возрастающее свойство графов. Тогда существует функция р0 = р0(п), для которой выполняется следующее:

• если р = о(р0), то Р(С(п,р) обладает свойством Ь) А 0, п А то;

• если р0 = о(р), то Р(С(п,р) обладает свойством Ь А 1, п А то.

Упомянем ещё один важнейший класс свойств графов — свойство содержать в качестве подграфа некоторый фиксированный граф С. Пороговые функции некоторых таких свойств нашли П. Эрдёш и А. Реньи в 1960 году [35]. Предварительно нам потребуется несколько определений. Пусть е(С) и у(с) — соответственно количество рёбер и вершин графа С. Плотностью графа С назовём отношение р(С) = . Граф С называется сбалансированным, если для каждого его подграфа Н выполнено неравенство р(Н) ^ р(С). Если последнее неравенство строгое для любого собственного подграфа Н, то граф называется строго сбалансированным.

Итак, сформулируем теорему о пороговой функции свойства содержать копию сбалансированного графа С в качестве подграфа.

Теорема 2 (П. Эрдёш, А. Реньи, 1960, [35]). Пусть С — сбалансированный граф. Тогда функция р = является пороговой для графа С(п,р) и свойства содержать копию графа С.

В 1985 году А. Ручиньски и А. Винс обобщили этот результат на случай произвольных графов. Для графа С положим

ртах(С) = шах р(Н).

Теорема 3 (А. Ручиньски, А. Винс, 1985, [36]). Функция р = и1/ртах(с) является пороговой для графа С(п,р) и свойства содержать копию графа С.

Наконец, в 1981 году Б. Боллобаш нашел асимптотическое распределение количества копий в С(п,р) фиксированного строго сбалансированного графа в случае, когда вероятность проведения ребра равна пороговой вероятности появления копии рассматриваемого графа. Пусть С — строго сбалансированный граф.

Теорема 4 (Б. Боллобаш, 1981, [37]). Пусть а — количество автоморфизмов графа С, р =

п-1/р(с). Тогда

Мс А Ро{в(1/а),п А то.

Здесь А обозначает сходимость по распределению, Pois(1/a) — пуассоновская случайная величина со средним 1/а, а ng — количество копий G в случайном графе G(n,p) (с точностью до перенумерации вершин).

Свойство графа содержать копию G в качестве подграфа является свойством, выразимым в логике первого порядка. Свойства первого порядка графов выражаются формулами первого порядка, которые в свою очередь записываются с помощью переменных, двух бинарных предикатных символов (= и ~), логических связок (а, —, Л, V,...) и кванторов по переменным (V, 3). Приведём пример свойства первого порядка. Свойство «содержать треугольник» является свойством первого порядка кванторной глубины 3. В самом деле, несложно проверить, что граф содержит треугольник тогда и только тогда, когда на нём справедлива формула 3х13х23х3(х1 ~ х2 Л Х\ ~ х3 Л х2 ~ х3). Подробнее о свойствах первого порядка и теории конечных моделей см., например, в [4; 5; 38].

Законы нуля или единицы для свойств первого порядка графов изучались, среди прочего, в [8; 9; 11; 39]. Также упомянем обзор [40]. Как говорилось выше, справедливость закона нуля или единицы для р = const в классе свойств первого порядка установили в 1969 году Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький и В.А. Таланов (и независимо в 1976 году Р. Фейгин).

Теорема 5 (Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький и В.А. Таланов, 1969, [8]; Р. Фейгин, 1976, [9]). Случайный граф G(n,p) при фиксированномр подчиняется закону нуля или единицы.

Традиционно в теории случайных графов также рассматривают выделенный случай разреженного графа, а именно, графа G(n,p) при р = п~а для некоторого а > 0 [1], [11]. Легко заметить, что закон нуля или единицы в случае разреженного случайного графа выполняется не для всех а. Рассмотрим, например, некоторый строго сбалансированный граф G плотности р > 0. По теореме [37] вероятность появления графа G в качестве подграфа в G(n,n~1/p) не стремится ни к нулю, ни к единице. Следовательно, для функции р(п) = п~1/р закон нуля или единицы нарушается.

Строго сбалансированный граф плотности р можно построить для произвольного р ^ 1 [41], из чего следует, что для любого рационального а е (0,1] закон нуля или единицы для р = п-а не выполняется.

Как было упомянуто в предыдущем разделе, при иррациональном а закон нуля или единицы для р = п-а, наоборот, выполняется, что было установлено Дж. Спенсером и С. Шелахом.

Теорема 6 (Дж. Спенсер, С. Шелах, 1988, [11]). Пусть р = п~а, а — положительное иррациональное число. Тогда для функции р(п) выполняется закон нуля или единицы.

Наконец, пользуясь результатами А. Ручиньски и А. Винса 1986 года, Дж. Спенсер и С. Шелах в 1988 году доказали следующую теорему.

Теорема 7 (Дж. Спенсер, С. Шелах, 1988, [11]; А. Ручински, А. Винс, 1986, [41])). Пусть а > 0 — рациональное число.

• Если а > 2 или а е (1 + щ-, 1 + 1) для некоторого I е N, то для функции р = п~а справедлив закон нуля или единицы.

• При всех остальных значениях а закон нуля или единицы для р = п~а не выполняется.

Изучению fc-закона нуля или единицы посвящены работы [12—17]. Очевидное следствие теоремы 6 состоит в том, что fc-закон нуля или единицы имеет место при иррациональных а для любого к е N. При рациональных а ситуация сложнее: fc-закон нуля или единицы может как выполняться, так и нарушаться, о чём свидетельствует следующая теорема.

Теорема 8 (М.Е. Жуковский, 2012, [12]). Пусть

р(п) = п~а, а е (о,-^—^ .

Тогда для функции р(п) выполняется k-закон нуля или единицы. При этом для функции р(п) = 1

п к-2 нарушается к-закон нуля или единицы.

Спектром числа к е N (fc-спектром, обозначается S(к)) назовём множество таких а е (0,1), что для функции р(п) = п~а не выполняется fc-закон нуля или единицы. Явное описание множества S(к) в общем случае является, по всей видимости, очень сложной проблемой [42]. Тем не менее, некоторые результаты удалось получить в вопросе исследования предельных точек S(к). Само по себе утверждение о том, что S(к) может быть бесконечен, является в некоторой степени контринтуитивным и впервые было показано в 1990 году Спенсером [43; 44]. Спектром свойства L первого порядка называется множество таких а е (0,1), для которых P(G(n,n~а) е L) не стремится ни к нулю, ни к единице.

Поскольку формул кванторной глубины к конечное количество (см., например, [5, Chapter 3]), чтобы доказать, что S(к) бесконечен для некоторого к, необходимо и достаточно предъявить формулу первого порядка кванторной глубины не более к с бесконечным спектром. В [43] Дж. Спенсер приводит свойство первого порядка с бесконечным спектром, которое описывается формулой первого порядка кванторной глубины 14. Далее, в 2016 году Дж. Спенсер и М.Е. Жуковский нашли ещё одну предельную точку S(к).

Теорема 9 (Дж. Спенсер, М.Е. Жуковский, 2016, [16]). При достаточно большом к точка jrzil является предельной точкой S(к).

Отметим, что любая предельная точка fc-спектра является предельной точкой «сверху»: для каждого а > 0 существует е > 0 такое, что интервал (а — £,а) не содержит точек fc-спектра [43, Section 8.4]. В 2018 году М.Е. Жуковский в работе [17] показал, что

Теорема 10 (М.Е. Жуковский, 2016, [17]). Точка 2 является предельной в спектре числа 5.

Наконец, из теоремы 8 следует, что спектр числа 3 пуст. Таким образом, минимальная кван-торная глубина свойства с бесконечным спектром равна либо 4, либо 5. В работе [13] М.Е. Жуковским и А.Д. Матушкиным установлено, что множество возможных предельных точек Б(4) ограничено значениями {1/2, 3/5}.

Перейдём к рассмотрению множества размеров индуцированных ^-подграфов случайного графа. Устройство этого множества изучалось в работах [33; 34]. Рассмотрим £ (С, к) = {1Е(Н )| : Н ^ С,у(Н) = к} — множество размеров (количеств рёбер) всех возможных индуцированных подграфов на к вершинах графа С. Как упоминалось ранее, устройство множества £ (С, к) тесно связано с гипотезой П. Эрдёша, Р. Фаудри и В. Шош об устройстве с-рамсеевых графов.

Гипотеза 1. Для любого с> 0 найдется такое Ь > 0, что справедливо следующее утверждение. Если граф С на п вершинах является с-рамсеевым, то

£ |£(С,к)1 > Ьп5/2.

к^п

Как мы упоминали ранее, гипотеза 1 была доказана М. Кваном и Б. Судаковым в 2019 году [32]. Доказательство представляет собой кульминацию серии важных результатов. В 2009 году Н. Алон и А.В. Косточка показали [33], что для указанной величины справедлива оценка порядка 0,(п2). Это утверждение является следствием следующей теоремы.

Теорема 11 (Н. Алон, А.В. Косточка, 2009, [33]). Для любого 0 < е < 1/2 существует п0 = п0(е), для которого справедливо следующее. Пусть п > п0 и пусть С — граф на п вершинах, для которого е < е(С)(С2) 1 < 1 — е. Тогда для любого к ^ справедливо

|£ (в,к)1 ^ 10-7к.

Отметим, что для любого константного с > 0 существует е = е(с) > 0, для которого любой с-рамсеев граф на п вершинах удовлетворяет соотношению е < е(С)(С^) 1 < 1 — £, как было показано П. Эрдёшем и Э. Семереди в [45].

Обратимся к биномиальному случайному графу. Несложно показать, что С(п, 1/2) асимптотически почти наверное является с-рамсеевым для значений с > ^. Это следует из того факта, что для любой константы с' > 2 случайный граф С(п, 1/2) асимптотически почти наверное не содержит ни клику, ни независимое множество размера с' 1с^2 п (см., например, [46]).

Н. Алон и А.В. Косточка изучили устройство множества £ (С, к) для случайного графа С(п, 1/2) и малых к. Оказывается, для С = С(п, 1/2) асимптотически почти наверное справедливо заключение Гипотезы 1, что следует из теоремы ниже.

Теорема 12 (Н. Алон, А.В. Косточка, 2009, [33]). Пусть G = G(n, 1/2) — случайный граф. Асимптотически почти наверное для любого к < 10~3п множество £(G, к) содержит отрезок длины по крайней мере 10-5к3/2.

Теорема 12, как указывают авторы, несложным образом обобщается на случай произвольного р = const. Отметим, что теорема не даёт ответа на вопрос о точности оценки размера искомого максимального отрезка. Ю. Балог и М.Е. Жуковский исследовали случай к > еп и также установили наличие отрезка большой длины в £(G, к) асимптотически почти наверное для G = G(n,p), получив верхнюю и нижнюю оценки на длину изучаемого отрезка.

Теорема 13 (Ю. Балог, М.Е. Жуковский, 2021, [34]). Пусть G = G(n,p) — случайный граф, где р е (0,1) — константа, £ > 0 — произвольная малая константа.

• Существует константа q > 0, для которой асимптотически почти наверное для любого к е {[еп\,... ,п — 1} множество £(G, к) содержит отрезок длины по крайней мере qk\jln(C^). Кроме того, асимптотически почти наверное для любого к е {1,..., \_£п\ — 1} множество £(G,k) содержит отрезок длины по крайней мере qk3/2.

• Существует константа Q > 0, для которой асимптотически почти наверное для любого к е {1,... ,п — 1} множество £(G, к) не содержит ни одного отрезка длины по крайней мере Qkу/^ ln(C*).

Теорема 13 позволяет найти порядок длины максимального отрезка в множестве £(G, к) для к > £п, но верхняя и нижняя оценки отличаются в константу раз. Для случая к < £п нижняя оценка, полученная Н. Алоном и А.В. Косточкой, имеет порядок 0(к3/2).

Цель работы и задачи исследования

Целью данной работы является доказательство или опровержение конечности 4-спектра первого порядка, а также получение асимптотики длины максимального подотрезка в множестве размеров fc-подграфов случайного графа G(n,p) при к < 8п. Для достижения поставленных целей решаются следующие задачи:

1. Доказать или опровернгуть, что 1/2 не является предельной точкой в множестве S(4).

2. Доказать или опровернгуть, что 3/5 не является предельной точкой в множестве S(4).

3. Получить точные нижнюю и верхнюю оценки асимптотики длины максимального подот-резка в множестве размеров индуцированных fc-подграфов случайного графа.

Научная новизна

Все приведённые результаты являются новыми. Для доказательства пустоты 4-спектра был разработан метод построения специального множества плотных графов, которые могут содержать данную вершину графа. Используя структуру и свойства этого множества, были приведены алгоритмы построения графов, наличие которых в случайном графе обеспечивает существование выигрышной стратегии Консерватора в игре Эренфойхта. Для доказательства теоремы о длине максимального подотрезка в множестве 8 (G, к) была сформулирована теорема о размере наиболее плотного подграфа в случайном графе G(n,p) при р = const для произвольного к < еп при малом е. Схема доказательства последней теоремы опирается на схему, предложенную для доказательства схожего утверждения в [47] с некоторыми существенными изменениями.

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

1. Доказано, что 1/2 не является предельной точкой 4-спектра первого порядка.

2. Доказано, что 3/5 не является предельной точкой 4-спектра, и таким образом доказана конечность S(4). Тем самым, минимальная кванторная глубина свойства первого порядка с бесконечным спектром равна 5.

3. Найдена асимптотика длины максимального отрезка в множестве 8(G, к) для G = G(n,p) при (ln п)1+а < к = о(п). Асимптотика длины максимального отрезка и мощности самого множества 8(G,k) совпадают.

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

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

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

Для доказательства результатов диссертации применялся аппарат теории графов, теории вероятностей, математической логики. Для доказательства пустоты 4-спектра первого порядка помимо стандартной техники (игра Эренфойхта, теоремы о пороговых вероятностях) использовались подходы, описанные в разделе «Научная новизна». Для нахождения асимптотики длины максимального отрезка в множестве размеров fc-подграфов случайного графа был адаптирован и применен метод поиска непрерывных отрезков размеров fc-подграфов, разработанный Алоном и Косточкой.

Апробация результатов

Степень достоверности полученных результатов обеспечивается приведёнными строгими доказательствами. Результаты диссертации опубликованы в 3 работах, представленных в конце списка литературы. Все эти работы опубликованы в журналах, содержащихся в собственном перечне журналов МФТИ. Личный вклад соискателя в работе с соавтором заключается в следующем. Ю.Н. Яровиков предложил идеи доказательств всех основных результатов, доказал используемые леммы и основную теорему работы.

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

• Конференция «Russian Workshop on Complexity and Model Theory», 2019, г. Долгопрудный, Россия.

• Доклад на Всероссийской научной конференции МФТИ, 2022, г. Долгопрудный, Россия.

• Доклад на конференции «Осенние математические чтения», 2022, г. Майкоп, Россия.

• Выступление на кафедральном семинаре кафедры дискретной математики МФТИ, 2024, г. Долгопрудный, Россия.

Структура диссертации

Данная работа состоит из 4 глав, исключая введение. В главе 1 введены необходимые обозначения, приводятся формулировки основных используемых утверждений. Глава 2 посвящена доказательству теоремы о непредельности точки 1/2 в 4-спектре первого порядка. В главе 3 мы завершаем доказательство теоремы о конечности 4-спектра, проверяя непредельность точки 3/5 в 5(4). Глава 4 содержит доказательство теоремы о наличии длинного подотрезка в множестве размеров fc-подграфов случайного графа.

Список литературы диссертационного исследования кандидат наук Яровиков Юрий Николаевич, 2025 год

СПИСОК ЛИТЕРАТУРЫ

1. Erdos P. On circuits and subgraphs of chromatic graphs // Mathematika. — 1962. — Т. 9, № 2. — С. 170—175.

2. Erdos P., Renyi A. On random graphs I. // Publicationes Mathematicae (Debrecen). — 1959. — Т. 6. — С. 290—297.

3. Bollobas B., Thomason A. Threshold functions // Combinatorica. — 1987. — Т. 7, № 1. — С. 35—38.

4. Верещагин Н., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. — МЦНМО, 2008. — С. 240.

5. Libkin L. Elements of finite model theory. Т. 41. — Springer, 2004.

6. Гильберт Д., Аккерман В. Основы теоретической логики. — Государственное издательство иностранной литературы, 1947. — С. 302.

7. Fagin R. Monadic generalized spectra // Mathematical Logic Quarterly. — 1975. — Т. 21, № 1. — С. 89—96.

8. Объем и доля выполнимости формул узкого исчисления предикатов / Ю. Глебский, Д. Коган, М. Лиогонький, В. Таланов // Кибернетика. — 1969. — Т. 2. — С. 17—27.

9. Fagin R. Probabilities on finite models // The Journal of Symbolic Logic. — 1976. — Т. 41, № 1. — С. 50—58.

10. Spencer J. Threshold spectra via the Ehrenfeucht game // Discrete Applied Mathematics. — 1991. — Т. 30, № 2/3. — С. 235—252.

11. Shelah S., Spencer J. Zero-one laws for sparse random graphs // Journal of the American Mathematical Society. — 1988. — Т. 1, № 1. — С. 97—115.

12. Zhukovskii M. Zero-one fc-law // Discrete Mathematics. — 2012. — Т. 312, № 10. — С. 1670— 1688.

13. Matushkin A., Zhukovskii M. First order sentences about random graphs: small number of alternations // Discrete Applied Mathematics. — 2018. — Т. 236. — С. 329—346.

14. Zhukovskii M., Matushkin A. Universal zero-one fc-law // Mathematical Notes. — 2016. — T. 99, № 3. — C. 511—523.

15. Zhukovskii M. On the zero-one 4-law for the Erdos-Renyi random graphs // Mathematical Notes. — 2015. — T. 97, № 1. — C. 190—200.

16. Spencer J., Zhukovskii M. Bounded quantifier depth spectra for random graphs // Discrete Mathematics. — 2016. — T. 339, № 6. — C. 1651—1664.

17. Zhukovskii M. On Infnite Spectra of First Order Properties of Random Graphs // Moscow Journal of Combinatorics and Number Theory. — 2016. — T. 6, № 4. — C. 73—102.

18. Graham R., Rothschild B., Spencer J. Ramsey theory. — John Wiley & Sons, 1991. — C. 216.

19. Graham R., Butler S. Rudiments of Ramsey theory. T. 123. — American Mathematical Soc., 2015. — C. 69.

20. Conlon D., Fox J., Sudakov B. Recent developments in graph Ramsey theory. // Surveys in combinatorics. — 2015. — T. 424, № 2015. — C. 49—118.

21. Chung F., Graham R. Erdos on graphs: His legacy of unsolved problems. — AK Peters/CRC Press, 1998.

22. Bohman T., Keevash P. The early evolution of the H-free process // Inventiones mathematicae. — 2010. — T. 181, № 2. — C. 291—336.

23. Mattheus S., Verstraete J. The asymptotics of r(4, t) // Annals of Mathematics. — 2024. — T. 199, № 2. — C. 919—941.

24. Spencer J. Asymptotic lower bounds for Ramsey functions // Discrete Mathematics. — 1977. — T. 20. — C. 69—76.

25. Ajtai M., Komlos J., Szemeredi E. A note on Ramsey numbers // Journal of Combinatorial Theory, Series A. — 1980. — T. 29, № 3. — C. 354—360.

26. Alon N., Rodl V. Sharp bounds for some multicolor Ramsey numbers // Combinatorica. — 2005. — T. 25, № 2. — C. 125—141.

27. Erdos P. Some remarks on the theory of graphs // Bulletin of the American Mathematical Society. — 1947. — T. 53. — C. 292—294.

28. Spencer J. Ramsey's theorem—a new lower bound // Journal of Combinatorial Theory, Series A. — 1975. — T. 18, № 1. — C. 108—115.

29. Erdos P., Lovasz L. Problems and results on 3-chromatic Hypergraphs and some related questions // Coll Math Soc J Bolyai. — 1974. — hhb. — T. 10.

30. Erdos P. Some of my favorite problems in various branches of combinatorics // Matematiche (Catania). — 1992. — Т. 47. — С. 231—240.

31. Erdos P. Some recent problems and results in graph theory // Discrete Mathematics. — 1997. — Т. 164, № 1—3. — С. 81—85.

32. Kwan M., Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs // Transacti-ons of the American Mathematical Society. — 2019. — Т. 372, № 8. — С. 5571— 5594.

33. Alon N., Kostochka A. Induced subgraphs with distinct sizes // Random Structures & Algorithms. — 2009. — Т. 34, № 1. — С. 45—53.

34. Balogh J., Zhukovskii M. On the sizes of large subgraphs of the binomial random graph // Discrete Mathematics. — 2022. — Т. 345, № 2. — С. 112—675.

35. Erdos P., Renyi A. On the evolution of random graphs // Publ. math. inst. hung. acad. sci. — 1960. — Т. 5, № 1. — С. 17—60.

36. Rucinski A., Vince A. Balanced graphs and the problem of subgraphs of random graphs // Congr. Numer. — 1985. — Т. 49. — С. 181—190.

37. Bollobas B. Threshold functions for small subgraphs. — 1981.

38. Immerman N. Descriptive Complexity. — Springer Graduate Texts in Computer Science (Springer, Berlin, 1999), 2015. — С. 268.

39. Luczak T., Spencer J. When does the zero-one law hold? // Journal of the American Mathematical Society. — 1991. — Т. 4, № 3. — С. 451—468.

40. Жуковский М. Е., Райгородский А. М. Случайные графы: модели и предельные характеристики // Успехи математических наук. — 2015. — Т. 70, 1 (421. — С. 35—88.

41. Rucinski A., Vince A. Strongly balanced graphs and random graphs // Journal of graph theory. — 1986. — Т. 10, № 2. — С. 251—264.

42. Жуковский М. Расширение fc-закона нуля или единицы // Доклады Академии наук. Т. 454. — Федеральное государственное бюджетное учреждение «Российская академия наук». 2014. — С. 23—23.

43. Spencer J. The strange logic of random graphs. Т. 22. — Springer Science & Business Media, 2013. — С. 178.

44. Spencer J. Infinite spectra in the first order theory of graphs // Combinatorica. — 1990. — Т. 10, № 1. — С. 95—102.

45. Erdos P., Szemeredi A. On a Ramsey type theorem // Periodica Mathematica Hungarica. — 1972. — Т. 2, № 1—4. — С. 295—299.

46. Alon N., Spencer J. The probabilistic method. — John Wiley & Sons, 2016. — С. 373.

47. El Cheairi H., Gamarnik D. Densest Subgraphs of a Dense Erdos-Renyi Graph. Asymptotics, Landscape, and Universality // SIAM Journal on Discrete Mathematics. — 2025. — Т. 39, № 2. — С. 1013—1081.

48. Ehrenfeucht A. An application of games to the completeness problem for formalized theories // Fund. Math. — 1961. — Т. 49, № 129—141. — С. 13.

49. Janson S., Luczak T., Rucinski A. Random graphs. — John Wiley & Sons, 2011.

50. Das S. A brief note on estimates of binomial coefficients. — 2016. — http : //page .mi . fu-berlin.de/shagnik/notes/binomials.pdf.

51. Paley R., Zygmund A. On some series of functions // Mathematical Proceedings of the Cambridge Philosophical Society. Т. 26. — Cambridge University Press. 1930. — С. 337—357.

52. Hoeffding W. Probability inequalities for sums of bounded random variables // Journal of the American statistical association. — 1963. — Т. 58, № 301. — С. 13—30.

53. Chernoff H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations // The Annals of Mathematical Statistics. — 1952. — С. 493—507.

54. Zhu H., Li Z., Hayashi M. Nearly tight universal bounds for the binomial tail probabilities // arXiv preprint arXiv:2211.01688. — 2022. — https://arxiv.org/pdf/2211.01688.

55. Yarovikov Y. On limit points of spectra of first-order sentences with quantifier depth 4 // Moscow Journal of Combinatorics and Number Theory. — 2020. — Т. 9, № 3. — С. 303—331.

56. Yarovikov Y., Zhukovskii M. Spectrum of FO logic with quantifier depth 4 is finite // ACM Transactions on Computational Logic. — 2024. — Т. 25, № 2. — С. 1—24.

57. Шефрукова Р. О справедливости закона 0 или 1 для неглубоких свойств первого порядка сильно разреженного случайного графа // Чебышевский сборник. — 2024. — Т. 25, 3 (94). — С. 299—334.

58. Zhukovskii M. The largest critical point in the zero-one k-law // Sbornik: Mathematics. — 2015. — Т. 206, № 4. — С. 489—509.

59. Яровиков Ю. О размерах k-подграфов биномиального случайного графа // Доклады Российской академии наук. Математика, информатика, процессы управления. — 2025. — Т. 523, № 3.