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

• Серкова Ольга Игоревна
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Серкова Ольга Игоревна

4.2 Первый этап

4.3 Оценки

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

4.5 Второй этап

4.6 Третий этап

5 Бутстрэп-перколяция

5.1 История задачи

5.2 Результаты для свойства стабильности в случае константного р

5.3 Стабильность в случае р = о(1)

5.4 Результаты для свойства стабильности в случае р = о(1)

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

6.1 Доказательство эквивалентности

6.2 Достаточные свойства

6.3 Доказательство для неслучайного графа

6.4 Доказательство свойств для случайного графа

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

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

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

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

7.2.1 Насыщающая структура размера х = [1пп\

7.2.2 Насыщающая структура размера у = р

7.2.3 Насыщающая структура размера п

Заключение

Обозначения

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

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

Введение

Актуальность темы исследования. На протяжении веков человечество интересуется комбинаторными свойствами различных структур. Одной из таких структур является граф.

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

Часто графы, с которыми приходится работать, настолько большие, что проверка тех или иных свойств на практике занимает огромное время или в приниципе невозможна, несмотря на современные вычислительные мощности. Особенно актуально это сейчас, так как XXI век характеризуется беспрецедентным ростом объема и сложности сетевых структур. Социальные взаимодействия, Интернет, нейронные связи мозга, финансовые транзакции, биологические системы — в эпоху больших данных эти явления формируют невероятно сложные сети огромного размера. Традиционные методы анализа, рассчитанные на детерминированные и ограниченные графы, сталкиваются с вычислительными и концептуальными трудностями при работе с такими масштабами и неопределенностью. В частности, эти сложности обусловлены тем фактом, что большинство задач определения свойств графа (например, задача коммивояжера, обнаружение клик заданного размера или проверка свойств раскрашиваемости) являются ИР-трудными.

Но обязательно ли проверять конкретный большой граф на выполнение свойства? Может быть, большинство графов этим свойством обладают, и тогда можно просто работать в предположении, что оно выполняется? Это соображение является мотивацией к изучению так называемых случайных графов. Случайный граф — это случайный элемент на множестве графов конкретного размера, который задается различными моделями (подходящая подбирается под задачу). Чаще всего нас интересует поведение случайного графа при п ^ о, так как при очень большом размере сети ее свойства практически не зависят от размера. Если мы сможем доказать, что случайный граф с очень большой

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

Понятие случайного графа начало активно использоваться в середине ХХ века. В 1959 году Эрдеш предложил принципиально новый подход к изучению графовых свойств, заложив основы вероятностного метода. Его ключевая идея заключалась в использовании случайного графа как инструмента доказательства: если определенное комбинаторное свойство выполняется с ненулевой вероятностью в подходящей случайной модели, то это доказывает существование хотя бы одного детерминированного графа, обладающего этим свойством. Этот метод позволил обойти необходимость явного конструирования сложных объектов, открыв новые пути в экстремальной комбинаторике.

Работы Эрдеша не просто предложили полезный инструмент, но и стимулировали глубокое изучение случайных графов как самостоятельных математических объектов. Исследования, начатые в 1960-70-х годах, особенно детальный анализ эволюции графа Эрдеша-Реньи при добавлении рёбер, выявили поразительное явление — резкие фазовые переходы, роднящие теорию случайных графов со статистической физикой. Было обнаружено, что при плавном изменении параметра (например, вероятности появления ребра) глобальные свойства графа претерпевают качественные скачки в узком критическом интервале, аналогичные фазовым переходам в веществе (например, переходу жидкость-газ или возникновению спонтанной намагниченности в модели Изинга).

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

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

гамильтоновы пути — являются монотонными. Как заметили Боллобаш и Томасон в 1987 году, монотонность влечет феномен резких фазовых переходов, о которых писалось выше: при переходе через р0 вероятность свойства изменяется от почти 0 к почти 1 в узком интервале значений параметра вероятности проведения ребра р.

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

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

В этом контексте поиск и анализ заданных подграфов случайного графа перестает быть чисто теоретической задачей. Обнаружение специфических паттернов — треугольников, клик и других заданных конфигураций [36, 25, 63, 12, 98, 24] — является важным инструментом для анализа реальных сетей.

Теперь непосредственно поговорим об актуальности задач, изучаемых в диссертации.

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

В модели случайного графа Эрдёша-Реньи С(п,р) каждое ребро между парой вершин из п-вершинного множества проводится с вероятностью р = р(п). Пороговой вероятностью для возрастающего свойства называется такое

р0 = р0(п), что при р/р0 ^ ж с вероятностью, стремящейся к единице с ростом п, свойство выполняется, а при р/р0 ^ 0 — не выполняется с вероятностью, стремящейся к единице. Аналогично можно определить это понятие и для убывающих свойств (предел меняется, наоборот, с 1 на 0).

В 1960 году Эрдеш и Реньи [36] сформулировали принципиальный вопрос: при какой пороговой вероятности р случайный граф С(п,р) начинает содержать гамильтонов цикл? Решение, полученное Поша лишь в 1976 году [98] (а также улучшенное Коршуновым [69], Комлошем и Семереди [66]), стало вехой, продемонстрировавшей возможность точного предсказания сложных глобальных свойств через вероятностные параметры.

Обобщением гамильтонова цикла является к-я степень гамильтонова цикла. Это цикл на всех вершинах графа такой, что ребрами соединены не только соседние вершины, но и из каждой вершины ребра идут в к предыдущих вершин цикла. Не так давно были найдены (Кюном и Остгусом [71], а также Нараянаном с соавторами [60]) пороговые вероятности для вхождения степеней гамильтонова цикла в случайный граф. Доказательства этих результатов сложны и существенно используют специфические свойства к-ых степеней циклов. Таким образом, они не позволяют непосредственным образом получить соответствующие результаты для хоть сколь-нибудь более широкого класса остовных подграфов. Одной из основных задач данной работы является нахождение пороговой вероятности вхождения заданного подграфа в случайный граф для широкого класса остовных подграфов. В частности, мы рассматриваем к-вырожденные графы, которые также можно считать обобщением деревьев: их можно представить в виде последовательности вершин, где ребра идут в не более, чем к каких-то более ранних вершин, но не обязательно в предыдущие, как это происходит в случае к-ой степени пути.

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

Риордан [101] получил результат, который позволяет доказывать, что некий остовный подграф содержится в случайном графе, для очень широкого класса подграфов и некоторых принципиальных условиях на вероятность ребра. Однако применение теоремы Риордана не всегда возможно или может не давать

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

Еще более сложной проблемой является задача нахождения точной пороговой вероятности в ситуациях, когда она существует — иными словами, такой последовательности р0 = р0(п), что свойство графа еще более резко меняет свою выполнимость в окрестностях ро — достаточно умножить р0 на константу большую или меньшую единицы, чтобы свойство начало или перестало выполняться с высокой вероятностью. Методы из перечисленных выше работ часто оказываются не достаточно аккуратны для нахождения точной пороговой вероятности. Так, например, на разрешение гипотезы о точной пороговой вероятности для второй степени гамильтонова цикла ушло более пяти лет [60, 113]. В настоящей диссертационной работе мы уделяем внимание и этому классу задач.

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

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

Процессом бутстрэп-перколяции будем называть процесс добавления ребер в некоторый граф Г так, что при каждом добавлении ребра появляется новая копия некого заданного графа Н (содержащая это ребро), пока мы не получим граф С. В этом случае граф Н называется шаблоном, а минимальное число ребер в графе Г таком, что из него с помощью этого процесса можно получить граф С, называется числом слабой насыщаемости wsat(G, Н). Эта величина отражает

критический минимум структурных связей, необходимых для гарантированного появления целевой конфигурации в процессе роста графа. Это понятие было впервые введено Боллобашем в 1968 году [21] и с тех пор активно изучается.

Активной областью исследования в последние два десятилетия является перенесение экстремальных свойств графов на их случайные подграфы. Так, например, ведется поиск классов графов, для которых число слабой насыщаемости случайного графа с некоторой вероятностью ребра является стабильным, то есть совпадает с числом для полного графа. Другой логично возникающий вопрос: при какой вероятности ребра число слабой насыщаемости стабильно для какого-то конкретного шаблона? Обеим задачам тоже уделяется внимание в диссертации.

Степень разработанности темы. Объектом изучения диссертации являются случайные графы. Граф — это математический объект, который позволяет описывать любые системы, в которых есть попарные связи между элементами. Формально, граф — это пара С = (V, Е), где V — множество вершин графа, а Е — множество ребер. Каждое ребро — это неупорядоченная пара {а, Ь}, где а,Ь Е V .В диссертации рассматриваются графы без петель, то есть предполагается, что каждое ребро {а,Ь} удовлетворяет а = Ь.

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

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

Перечислим наиболее изученные модели:

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

•Равномерная модель. Случайным графом С(п,т) называется случайный

элемент множества графов с n вершинами и m = m(n) ребрами, выбранный

случайно и равновероятно.

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

Впервые случайные графы использовали Дженнингс и Морено в 1938 году в статье по статистической социологии, в которой авторы сравнивали экспериментальную социальную сеть со случайной [93]. Их случайная сеть позже оказалась биномиальной моделью G(n,p). Также, еще до создания теории, случайные графы применили Соломонофф и Рапопорт в статье 1951 года, где представили мозг в виде случайной сети [102]. Авторы использовали другую модель случайного графа—граф с фиксированной степенью вершины, где соседи выбирались равновероятно.

Также в 1959 году случайный граф появляется в математической статье знаменитого венгерского математика Эрдеша в рамках применения вероятностного метода, одного из подходов в дискретной математике [35]. А основы математической теории случайных графов были заложены в том же 1959 году им же и Реньи [37] и независимо от них Гильбертом [52].

Гильберт в статье «Random graphs» предложил модель G(n,p) и изучал вероятность ее связности [52]. Интересно, что автор разработал эту модель с конкретной прикладной целью: он предлагал использовать ее в качестве описания телефонной сети. Гильберт работал в телефонной компании Белла и хотел найти вероятность того, что в случае отказа каких-то линий сети (непроведенные ребра) все еще можно будет направить звонки между двумя точками. Эрдеш и Реньи в своей статье «On random graphs» ввели модель G(n,m) и рассмотрели вопрос связности, а также некоторые вопросы о количестве компонент связности в этом графе [37]. Их статьи [37, 36, 38, 39] и [40] заложили фундамент современной науки о случайных графах и привлекли к ней интерес других исследователей.

Дальнейшее развитие темы активно ускорилось в середине 1980х годов с выходом знаменитой книги Боллобаша «Случайные графы» [18] (1985 год), а также с созданием серии специализированных конференций группой дискретной математики из университета Адама Мицкевича (1983 год). Эти конференции проводятся по сей день.

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

Диссертационная работа посвящена исключительно классической биномиальной модели, о которой и пойдет речь дальше. Стоит отметить, что при некоторых достаточно широких условиях на вероятность ребра выполнимость свойств в биномиальной и равномерной модели эквивалентна в асимптотическом смысле.

За последние десятилетия накоплен огромный массив работ, посвященных случайному графу С(п,р) в моделях Эрдеша —Реньи (см., например, [7, 17, 18, 34, 56, 1, 2]). К числу исследованных задач относятся распределение малых подграфов [15, 37, 95], количества деревьев [16, 36], существование и размер гигантской компоненты [16, 78, 83], распределение диаметра [33, 55] и многие другие.

Для дальнейшего изложения нам придется формализовать понятие графового свойства. Каждый граф (неслучайный) может обладать или не обладать какими-либо свойствами. Например, он может быть связным, содержать цикл или треугольник (цикл длины три). Формально свойством графа будем называть некоторое множество графов (графы из этого множества обладают этим свойством). Будем говорить, что свойство графа выполняется асимптотически почти наверное (а.п.н.), если вероятность выполнения этого свойства стремится к 1 с ростом п к бесконечности.

Свойство графа Q называется возрастающим, если для любого графа С и для любого Н такого, что С является его остовным подграфом, из С Е Q следует Н Е Q, т.е. при добавлении ребер свойство сохраняется. Свойство Q называется убывающим, если для любого графа С и для любого остовного Н С С, из С Е Q следует Н Е Q, т.е. при убавлении ребер свойство сохраняется.

Пороговой вероятностью возрастающего свойства называется такое

Ро = p0(n), что при p/p0 ^ ж свойство а.п.н. выполняется, а при p/p0 ^ 0 свойство а.п.н. не выполняется. Точной пороговой вероятностью возрастающего свойства называется такое p0 = p0(n), что Ve > 0 при p ^ (1 + e)p0 свойство а.п.н. выполняется, а при p ^ (1 — e)p0 свойство а.п.н. не выполняется. Аналогично эти понятия определяются и для убывающих свойств (выполнимость при маленьких и больших p меняется местами).

Уже в своей основопологающей работе об эволюции случайного графа [36] Эрдеш и Реньи сформулировали понятие пороговой вероятности. Нетрудно понять, что для нетривиального возрастающего свойства Q и для каждого фиксированного n растет P(G(n,p) <Е Q) возрастает при увеличении p. Поэтому существует единственное решение pc(Q) уравнения P(G(n,p) <Е Q) = 2. В 1987 году Боллобаш и Томасон [20] доказали, что а.п.н. G(n,p) <Е Q, если p/pc(Q) ^ ж, и а.п.н. G(n,p) ^ Q, если p/pc(Q) ^ 0, то есть pc(Q) является пороговой вероятностью. Фридгут [47, 48] показал, что для возрастающих свойств существование пороговой вероятности, но не точной пороговой вероятности, равносильно тому, что в случайном графе содержится некоторый подграф ограниченного размера. С тех пор значения pc(Q) для возрастающих свойств Q исследовались в многочисленных работах. Однако общего решения пока не найдено.

Тем не менее для произвольного возрастающего свойства Q значение pc(Q) можно найти с точностью до логарифмического множителя, используя понятие порога математического ожидания. Под порогом pe(Q) математического ожидания подразумевается максимальное значение p, такое что существует

множество графов Q', удовлетворяющее условию Y1 ple(G) ^ | и Q С (Q'),

ggq'

где количество ребер в графе G обозначено e(G), а (Q') — это замыкание Q' вверх. Иными словами, (Q') содержит все графы, которые содержат хотя бы один остовный подграф из Q'. По неравенству Маркова (теорема 2, раздел 1.3) pe(Q) ^ pc(Q). Парк и Фам [97] показали, что существует C > 0 такое, что для любого возрастающего свойства Q выполняется pc(Q) ^ Cpe(Q) • log n.

Риордан [101] описал широкий класс возрастающих свойств Q, для которых логарифмический множитель в неравенстве, полученном Парк и Фам, отсутствует, тем самым установив асимптотический порядок величины pc(Q). Ниже мы приводим формулировку этого замечательного результата.

Здесь и далее v(H) — количество вершин в графе H, e(H) — количество ребер

в графе Н, с(Н) — количество компонент в графе Н, N = С

Теорема 1 (Риордан [101]). Пусть Н = Н(п) — граф на п вершинах с максимальной степенью А = А(п). Положим а = е(Н)/N и

е(Н')

7 = 8иР ~Гш\-о •

И'СИ,у(И')^3 /и(Н ) — 2

Пусть, кроме того, р = р(п) Е (0,1). Если

1. аN ^ п,

2. pN, (1 — р)л/п — ж при п —у ж,

3. пр7 / А4 — ж при п — ж,

то С(п,р) а.п.н. содержит подграф, изоморфный Н.

Одной из наиболее изученных задач в области остовных подграфов случайного графа является поиск гамильтонова цикла и его степеней. Вопрос о пороговой вероятности для гамильтонова цикла был поставлен еще в 1960 году Эрдешем и Реньи. В 1976 году наконец-то ответ был получен Поша в [98]. Другие доказательства были представлены в [69, 66, 3, 23]. Оказалось, что пороговая вероятность появления гамильтонова цикла в случайном графе равна .

Из результата Риордана следует, что при к ^ 3 и р ^ п—к случайный граф содержит к-ю степень гамильтонова цикла. При этом в силу того, что рс > ре, нетрудно заметить, что ((1 — в(1))е/п)1/к является нижней оценкой пороговой вероятности рс при к ^ 3. Таким образом, для к ^ 3 асимптотика пороговой вероятности известна и равна 0(п—1/к).

Однако для к = 2 между верхней оценкой п—1 и нижней п—1 оставался большой зазор. Д. Кюн и Д. Остгус [71] показали в 2012 году, что если р > п—1/2+£, то а.п.н. случайный граф содержит вторую степень гамильтонова цикла. Проблема была окончательно решена в статье 2021 года Кана, Нараянана и Парк [60]. Авторы доказали, что пороговая вероятность на самом деле равна п—2.

Однако «обратный» вопрос — какова максимальная степень к такая, что в случайном графе а.п.н. существует к-я степень гамильтонова пути, — при произвольном р изучен плохо. Пожалуй, наиболее естественным и сложным этот вопрос является при постоянной вероятности проведения ребра, в частности при

p = 1/2. Насколько хорошо сконцентрировано значение маскимальной степени гамильтонова цикла в случайном графе и в каком диапазоне?

Нетрудно показать с помощью неравенства Маркова (теорема 2 в разделе 1.3), что при k > log2 n в графе G(n, 1/2) а.п.н. нет k-й степени гамильтонова цикла. В случае произвольного фиксированного p £ (0,1) можно получить

верхнюю оценку на максимальную степень гамильтонова цикла log 1 n, то есть

p

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

Другим частным случаем остовных подграфов являются k-вырожденные графы. Для таких графов можно из теоремы 1 вывести результаты о пороговой вероятности. Тем не менее вопрос о значении точной пороговой вероятности для произвольного k-вырожденного подграфа остается открытым.

Недавно были получены результаты [113, 84], показывающие, что точная пороговая вероятность для k-й степени гамильтонова цикла, который является частным случаем k-вырожденного графа, равна (e/n)l/k, при любом k > 2.

Что касается области бутстрэп-перколяции, то она начала свое развитие с работ Боллобаша [21] 1968 года, где он ввел понятие слабой насыщаемости. Точное значение wsat(Kn, Ks) было получено независимо Алоном [5], Франклом [44], Калаи [61,62], также его можно вывести из более ранней работы Ловаса [74], и позже еще одно доказательство было получено Ю [111].

Значение wsat(Kn, Ks,t) для произвольных параметров все еще неизвестно, но есть результаты в частных случаях. Калаи [61] установил, что

wsat(Kn, Ktt) = (t — 1)(n + 1 — t/2)

при условии n ^ 4t — 4. Обобщение было получено Кроненберг, Мартинс и Моррисон [70] в 2020 году. Они заново доказали, что

wsat(Kn,Kt t) = (t — 1)(n + 1 — t/2),

если t ^ 2 и n ^ 3t — 3. Более того, они доказали аналогичный результат для

™5а1(кП5к*+1) = (г — 1)(п + 1 — г/2) + 1, если г ^ 2 и п ^ 3г—3. Также они получили оценки для произвольных параметров

й, г:

wsat(Kn, К^г) ^ (з — 1)(п — з) + С? (1)

если г > й ^ 2 и п ^ 2(й + г) — 3 и

wsat(Kn, Кя> ?) ^ (з — 1)(п — г + 1) + С? (2)

если г > з ^ 2 и п ^ 3г — 3. Для й = 1 точное значение числа слабой насыщаемости получается с помощью несложных рассуждений, которые мы позже приведем в тексте диссертации:

wsat(Kn5Kl> ? ) = С

Также в недавней работе Миралаей, Мохаммадиана и Тайфе-Реза [88] были получены точные значения wsat(Kn, К2>?).

Значение числа слабой насыщаемости было получено и для могих других графов С и Н (например, для полных многодольных графов [5], для несвязных копий графов [42], для гиперкубов и решеток [9, 10, 92]). Число слабой насыщаемости для гиперграфов было изучено, например, в [5, 9, 41, 42, 91, 108, 109].

В 2017 Коранди и Судаков [68] доказали, что если й ^ 3, то wsat(Kn, Ks) стабильно, т.е., а.п.н. для константного р Е (0,1),

wsat(С(n,p),Ks) = wsat(Kn, Ks).

Коранди и Судаков [68] также заметили, что их результат может быть обобщен на случай п—£(^ ^ р ^ 1 и задали следующий вопрос: при каких ограничениях на р а.п.н. выполнено wsat(G(n,p), Ks) = wsat(Kn, Ks)?

В 2020 году Бидголи, Мохаммадиан, Тайфе-Реза и Жуковский [14] доказали существование пороговой вероятности для свойства wsat(G(n,p), Ks) = wsat(Kn, Ks). Более того, они нашли следующие оценки на пороговую вероятность:

2 2

• существует с = с(в) , т.ч. если р < сп-«+1 (1п п) (°-2)(°+1) , то а.п.н.

wsat(G(n,p),Ks) = wsat(Kn, К8),

Список литературы диссертационного исследования кандидат наук Серкова Ольга Игоревна, 2025 год

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

[1] Колчин В. Ф. Случайные графы. - М.: Физматлит, 2002. - 254 с.

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

[3] Ajtai M., Komlos J., Szemeredi E. The first occurrence of Hamilton cycles in random graphs//Annals of Discrete Mathematics. - 1985. - Vol.27. -P. 173-178.

[4] Aldous D. Brownian excursions, critical random graphs and the multiplicative coalescent // Annals of Probability. - 1997. - Vol. 25. - P. 812 -854.

[5] Alon N. An extremal problem for sets with applications to graph theory // Journal of Combinatorial Theory. Series A. - 1985. - Vol. 40, no. 1. -P. 82 -89.

[6] Alon N., Furedi Z. Spanning subgraphs of random graphs // Graphs and Combinatorics. - 1992. - Vol. 8, no. 1. -P. 91 -94.

[7] Alon N., Spencer J. H. The probabilistic method. - 2nd ed. - New York: John Wiley & Sons, 2000. -P. 301

[8] Antonir A. C., Peled Y., Shapira A., Tyomkyn M., Zhukovskii M. When does a tree activate the random graph? —2025. —URL: https://arxiv.org/pdf/2507.05697 (дата обращения: 09.10.2025).

[9] Balogh J., Bollobas B., Morris R., Riordan O. Linear algebra and bootstrap percolation // Journal of Combinatorial Theory. Series A. - 2012. - Vol. 119, no. 6. -P. 1328-1335.

[10] Balogh J., Pete G. Random disease on the square grid // Random Structures and Algorithms. - 1998. - Vol. 13, no. 3-4. -P. 409-422.

[11] Barabasi A.-L. Albert R., Emergence of scaling in random networks // Science. -1999. - Vol. 286 no. 5439. - P. 509-512.

[12] Barbour A. D., Janson S., Karonski M., Rucinski A. Small cliques in random graphs // Random Structures and Algorithms. - 1990. - Vol. 1. - P. 403 -434.

[13] Bayati M., Gamarnik D., Tetali P. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs // Annals of Probability. - 2013. -Vol. 41. -P. 4080-4115.

[14] Bidgoli M. R., Mohammadian A., Tayfeh-Rezaie B., Zhukovskii M. Threshold for weak saturation stability. — 2020. — URL: https://arxiv.org/pdf/2006.06855 (дата обращения: 09.10.2025).

[15] Bollobas B. Threshold functions for small subgraphs // Mathematical Proceedings of the Cambridge Philosophical Society. - 1981. - Vol. 90. - P. 197-206.

[16] Bollobas B. The evolution of random graphs // Transactions of the American Mathematical Society. - 1984. - Vol. 286. - P. 257-274.

[17] Bollobas B. Martingales, isoperimetric inequalities and random graphs // Combinatorics (Eger 1987). - Amsterdam: North-Holland, 1988. - P. 113-139.

[18] Bollobas B. Random graphs. - 2nd ed. - Cambridge: Cambridge University Press, 2001.-P. 498.

[19] Bollobas B., Riordan O. Mathematical results on scale-free random graphs // Handbook of graphs and networks. - Weinheim: Wiley-VCH, 2003. - P. 1-34.

[20] Bollobas B., Thomason A. G. Threshold functions // Combinatorica. - 1987. - Vol. 7 no. 1. - P. 35-38.

[21] Bollobas B. Weakly k-saturated graphs // Beiträge zur Graphentheorie. - 1968. -P. 25-31.

[22] Bollobas B. The evolution of random graphs // Transactions of the American Mathematical Society. - 1984. - Vol. 286. - P. 257-274.

[23] Bollobas B. The evolution of sparse graphs // Proceedings of a Cambridge Combinatorial Conference in honour of Paul Erdös. - 1984. - P. 35-57.

[24] Bollobas B., Frieze A. M. On matchings and Hamiltonian cycles in random graphs // Annals of Discrete Mathematics. - 1985. - Vol. 28. - P. 23-46.

[25] Bollobas B. Random graphs // Combinatorics, Proceedings, Swansea. - 1981. - P. 80-102.

[26] Bollobas B. The diameter of random graphs // Transactions of the American Mathematical Society. - 1981. - Vol. 267. - P. 41-52.

[27] Bollobas B. The chromatic number of random graphs // Combinatorica. - 1988. -Vol. 8. - P. 49-56.

[28] Burtin J. D. Extremal metric characteristics of a random graph I // Theory of Probability and its Applications. - 1974. - Vol. 19. -P. 740-754.

[29] Burtin J. D. Extremal metric characteristics of a random graph II // Theory of Probability and its Applications. - 1975. - Vol. 20. - P. 82 -99.

[30] Chen Y., Han J., Luo H. On the thresholds of degenerate hypergraphs. — 2024. — URL: https://arxiv.org/pdf/2411.18596 (дата обращения: 09.10.2025).

[31] Croft H. T. Incident incidents // Eureka. - 1967. - Vol. 30. - P. 22 -26.

[32] Dani V., Moore C. Independent sets in random graphs from the weighted second moment method // Proceedings of RANDOM. - 2011. - P. 472 -482.

[33] Damerell R. On Moore graphs // Mathematical Proceedings of the Cambridge Philosophical Society. - 1973. - Vol.74. -P. 227-236.

[34] Durrett R. Random Graph Dynamics. - Cambridge: Cambridge University Press, 2006. -P. 208

[35] Erdos P. Graph theory and probability // Canadian Journal of Mathematics. - 1959. -Vol. 11. -P. 34-38.

[36] Erdos P., Renyi A. On the evolution of random graphs // Publications of the Mathematical Institute of the Hungarian Academy of Sciences. - 1960. - Vol. 5. -P. 17-61.

[37] Erdos P., Renyi A. On random graphs I // Publications Mathematicae Debrecen. -1959. - Vol. 6. -P. 290-297.

[38] Erdos P., Renyi A. On the strength of connectedness of a random graph // Acta Mathematica Academiae ScientiarumHungaricae. -1961. - Vol. 8. -P. 261-267.

[39] Erdos P., Renyi A. On random matrices // Publications of the Mathematical Institute of the Hungarian Academy of Sciences. - 1964. - Vol. 8. - P. 455 -461.

[40] Erdos P., Renyi A. On the existence of a factor of degree one of a connected random graph//Acta Mathematica Academiae Scientiarum Hungaricae. - 1966. - Vol. 17. -P. 359-368.

[41] Erdos P., Furedi Z., Tuza Z. Saturated r-uniform hypergraphs // Discrete Mathematics. - 1991. - Vol. 98, no. 2. -P. 95-104.

[42] Faudree R. J., Gould R. J. Weak saturation numbers for multiple copies // Discrete Mathematics. -2014. - Vol.336. -P. 1-6.

[43] Fischer M., Skoric N., Steger A., Trujic M. Triangle resilience of the square of a Hamilton cycle in random graphs // Journal of Combinatorial Theory. Series B. -2022. - Vol. 152. -P. 171 -220.

[44] Frankl P. An extremal problem for two families of sets // European Journal of Combinatorics. - 1982. - Vol. 3, no. 2. -P. 125-127.

[45] Frankston K., Kahn J., Narayanan B., Park J. Thresholds versus fractional expectation-thresholds // Annals of Mathematics. - 2021. - Vol. 194, no. 2. - P. 475 -495.

[46] Freuder E. C. A sufficient condition for backtrack-free search // Journal of the ACM. - 1982. - Vol. 29, no. 1. -P. 24-32.

[47] Friedgut E. Sharp thresholds of graph properties and the k-sat problem // Journal of the American Mathematical Society. - 1999. - Vol. 12, no. 4. -P. 1017-1054.

[48] Friedgut E. Hunting for sharp thresholds // Random Structures and Algorithms. -2005. - Vol. 26, no. 1-2. -P. 37-51.

[49] Frieze A., KaronskiM. Introduction to Random Graphs. - Cambridge: Cambridge University Press, 2015. - P. 424

[50] Frieze A. M. On the independence number of random graphs // Discrete Mathematics. - 1990. - Vol. 81. -P. 171 -176.

[51] Frieze A. Hamilton cycles in random graphs: a bibliography. — 2019. — URL: https://arxiv.org/pdf/1901.07139 (дата обращения: 09.10.2025).

[52] Gilbert E. N. Random graphs // The Annals of Mathematical Statistics. - 1959. -Vol. 30, no. 4. -P. 1141-1144.

[53] Glebov R., Krivelevich M. On the number of Hamilton cycles in sparse random graphs // SIAM Journal on Discrete Mathematics. - 2013. - Vol. 27. - P. 27 -42.

[54] Graham R. L., Knuth D. E., Patashnik O. Concrete mathematics: a foundation for computer science. -2nded. - Boston: Addison-Wesley, 1994. -P. 657

[55] Hoffman A., Singleton R. On Moore graphs with diameters 2 and 3 // IBM Journal of Research and Development. - 1960. - Vol. 4, no. 5. - P. 497 -504.

[56] Janson S., Luczak T., Rucinski A. Random graphs. - New York: John Wiley & Sons, 2000. - P. 333

[57] Janson S., Knuth D. E., Luczak T., Pittel B. G. The birth of the giant component // Random Structures and Algorithms. - 1993. - Vol. 4. - P. 233 -358.

[58] Johansson A., Kahn J., Vu V. Factors in random graphs // Random Structures & Algorithms. -2008. - Vol.33. -P. 1-28.

[59] Kahn J., Kalai G. Thresholds and expectation thresholds // Combinatorics, Probability and Computing. -2007. - Vol. 16, no. 3. -P. 495-502.

[60] Kahn J., Narayanan B., Park J. The threshold for the square of a Hamilton cycle // Proceedings of the American Mathematical Society. -2021. - Vol. 149, no. 1. -P. 3201 -3208.

[61] Kalai G. Hyperconnectivity of graphs // Graphs and Combinatorics. - 1985. -Vol. 1, no. 1. -P. 65-79.

[62] Kalai G. Weakly saturated graphs are rigid // Convexity and graph theory. -Amsterdam: North-Holland, 1984. -P. 189-190.

[63] Karonski M., Rucinski A. Problem 4 // Graphs and other combinatorial topics, Proceedings of the Third Czechoslovak Symposium on Graph Theory. - Prague, 1983.

[64] Karonski M., Rucinski A. On the number of strictly balanced subgraphs of a random graph // Graph Theory. - Berlin: Springer, 1983. - P. 79 -83.

[65] Knuth D. E. The art of computer programming. Vol. 1: Fundamental algorithms.

- 3rd ed. - Reading: Addison-Wesley, 1997. - 650 p.

[66] Komlos J., Szemeredi E. Limit distributions for the existence of Hamilton circuits in a random graph // Discrete Mathematics. - 1983. - Vol. 43. - P. 55 -63.

[67] Komlos J., Szemeredi E. Hamilton cycles in random graphs // Infinite and finite sets. - Amsterdam: North-Holland - 1973. -P. 1003-1011.

[68] Korandi D., Sudakov B. Saturation in random graphs // Random Structures & Algorithms. -2017. -Vol. 51,no. 1. -P. 169-181.

[69] Korshunov A. D. Solution of a problem of Erdos and Renyi on Hamiltonian cycles in nonoriented graphs // Soviet Mathematics. Doklady. - 1976. - Vol. 228, no. 3. -P. 529 -532.

[70] Kronenberg G., Martins T., Morrison N. Weak saturation numbers of complete bipartite graphs in the clique // Journal of Combinatorial Theory. Series A. - 2021. -Vol. 178. - 105357.

[71] Kûhn D., Osthus D. On Posa's conjecture for random graphs // SIAM Journal on Discrete Mathematics. -2012. - Vol.26. -P. 1440-1457.

[72] Leclerc B. Graphes d'arches // Mathematiques & Sciences humaines. - 2002. -Vol. 157. -P. 27-48.

[73] Lick D. R., White A. T. k-degenerate graphs // Canadian Journal of Mathematics.

- 1970. - Vol.22. -P. 1082-1096.

[74] Lovasz L. Flats in matroids and geometric graphs // Combinatorial surveys. -1977. -P. 45-86.

[75] Luccio F., Mesa A., Pagli L. A distributed tree data structure // Proceedings of the 1st International Symposium on Advanced Distributed Systems. - Guadalajara, 2000. -P. 1-6.

[76] Luccio F., Pagli L. Dense trees: a new structure for interconnection // Proceedings of Distributed Data and Structures 2. - Ottawa, 2000. - P. 56 -72.

[77] Luczak T. A note on the sharp concentration of the chromatic number of random graphs//Combinatorica. -1991. - Vol.11. -P. 295-297.

[78] Luczak T. Component behavior near the critical points of the random graph process //Random Structures and Algorithms. - 1990. - Vol.1. -P. 287-310.

[79] Luczak T. Component behaviour near the critical point // Random Structures and Algorithms. - 1990. - Vol. 1. -P. 287-310.

[80] Luczak T. Cycles in a random graph near the critical point // Random Structures and Algorithms. -1991. - Vol.2. -P. 421 -440.

[81] Luczak T. On the equivalence of two basic models of random graphs // Proceedings of Random Graphs'87 - Chichester: Wiley, 1990. -P. 151-158.

[82] Luczak T. The phase transition in a random graph // Combinatorics, Paul Erdos is Eighty. -Budapest: JanosBolyaiMathematical Society, 1996. -P. 399-422.

[83] Luczak T., Pittel B., Wierman J. The structure of a random graph near the point of the phase transition // Transactions of the American Mathematical Society. - 1994. -Vol. 341. -P. 721 -748.

[84] Makai T., Pasch M., Petrova K., Schiller L. Sharp thresholds for higher powers of Hamilton cycles in random graphs. — 2025. — URL: https://arxiv.org/pdf/2502.14515 (дата обращения: 09.10.2025).

[85] Matula D. The largest clique size in a random graph // Technical Report. - Dallas: Southern Methodist University — 1976. — URL: https://s2.smu.edu/ matula/Tech-Report76.pdf (дата обращения: 09.10.2025).

[86] Matula D. Expose-and-merge exploration and the chromatic number of a random graph//Combinatorica. - 1987. - Vol.7. -P. 275-284.

[87] McDiarmid C. Expected numbers at hitting times // Journal of Graph Theory. -1991. - Vol. 15. -P. 637-648.

[88] Miralaei M., Mohammadian A., Tayfeh-Rezaie B. The weak saturation number of K2t // Discrete Mathematics. - 2024. - Vol. 347, no. 9. - 114078.

[89] Montgomery R. Topics in random graphs. Lecture notes. — 2018. — URL: https://rhmontgomery.warwick.ac.uk/topicsinrandomgraphs.pdf (дата обращения: 09.10.2025).

[90] Montgomery R. Spanning trees in random graphs // Advances in Mathematics. -2019. - Vol. 356. -P. 106793.

[91] Moshkovitz G., Shapira A. Exact bounds for some hypergraph saturation problems //Journal of Combinatorial Theory. Series B. -2015. - Vol.111. -P. 242-248.

[92] Morrison N., Noel J. A. Extremal bounds for bootstrap percolation in the hypercube // Journal of Combinatorial Theory. Series A. - 2018. - Vol. 156. -P. 61 -84.

[93] Moreno J. L., Jennings H. H. Statistics of Social Configurations // Sociometry. -1938. - Vol. 1, no. 3/4. -P. 342-374.

[94] Nenadov R., Skoric N. Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs // Random Structures and Algorithms. -2019. - Vol. 54. -P. 187-208.

[95] Palka Z. On the number of vertices of given degree in a random graph // Journal of Graph Theory. - 1982. - Vol.4. -P. 321 -329.

[96] Penrose M. Random Geometric Graphs. -Oxford: Oxford University Press, 2003. - P. 330

[97] Park J., Pham H. A proof of the Kahn-Kalai conjecture // Journal of the American Mathematical Society. - 2024. - Vol. 37. - P. 235 -243.

[98] Posa L. Hamiltonian circuits in random graphs // Discrete Mathematics. - 1976. -Vol. 14. -P. 359-364.

[99] Price D. D. S. A general theory of bibliometric and other cumulative advantage processes // Journal of the American Society for Information Science. - 1976. -Vol. 27. - P. 292 -306.

[100] Radziszowski S. P. Small Ramsey Numbers // Electronic Journal of Combinatorics. -2004. - Dynamic Survey DS1. -42 p.

[101] Riordan O. Spanning subgraphs of random graphs // Combinatorics, Probability and Computing. -2000. - Vol.9. -P. 125-148.

[102] Solomonoff R., Rapoport A. Connectivity of random nets // Bulletin of Mathematical Biophysics. -1951. - Vol. 13. -P. 107-117.

[103] Rodl V., Szemeredi E., Rucinski A. An approximate Dirac-type theorem for k-uniform hypergraphs // Combinatorica. - 2008. - Vol. 28, no. 2. - P. 229-260.

[104] Spencer J. Threshold functions for extension statements // Journal of Combinatorial Theory. Series A. - 1990. - Vol. 53. -P. 286-305.

[105] Spencer J. Counting extensions // Journal of Combinatorial Theory. Series A. -1990. - Vol. 55, no. 2. - P. 247 -255.

[106] Shamir E., Spencer J. Sharp concentration of the chromatic number of random graphs Ощр // Combinatorica. - 1987. - Vol. 7. -P. 121 -129.

[107] Todd P. A k-tree generalization that characterizes consistency of dimensioned engineering drawings // SIAM Journal on Discrete Mathematics. - 1989. - Vol. 2. -P. 255-261.

[108] Tuza Z. Asymptotic growth of sparse saturated structures is locally determined // Discrete Mathematics. - 1992. - Vol. 108, no. 1-3. -P. 397-402.

[109] Tuza Z. Extremal problems on saturated graphs and hypergraphs // Ars Combin. - 1988. - Vol. 25B. -P. 105-113.

[110] Rucinski A., Vince A. Strongly balanced graphs and random graphs // Journal of Graph Theory. - 1986. - Vol. 10. -P. 251 -264.

[111] Yu J. An extremal problem for sets: a new approach via Bezoutians // Journal of Combinatorial Theory. Series A. - 1993. - Vol.62. -P. 170-175.

[112] Yule G. U. A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F. R. S. // Journal of the Royal Statistical Society. - 1925. - Vol. 88, no. 3. -P. 433-436.

[113] Zhukovskii M. Sharp thresholds for spanning regular subgraphs. — 2025. — URL: https://arxiv.org/pdf/2502.14794v3 (дата обращения: 09.10.2025).

Список работ, опубликованных автором по теме диссертации

[114] Калиниченко О. И., Тайфе-Реза Б., Жуковский М. Е. Слабо насыщенные подграфы случайного графа // Доклады Российской академии наук. Математика, информатика, процессы управления. - 2023. - Т. 509. - С. 46-49.

[115] Серкова О. И. О некоторых остовных подграфах случайных графов // Доклады Российской академии наук. Математика, информатика, процессы управления. - 2025. - Т. 523. - С. 66-70.

[116] Kalinichenko O., Zhukovskii M. Weak saturation stability // European Journal of Combinatorics. - 2023. - Vol. 113. - 103777.