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

• Кожевников Владислав Сергеевич
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Кожевников Владислав Сергеевич

1.6 Дисперсия числа циклов

1.7 Доказательство Теоремы 2 о пороговой вероятности появления цикла

2 Ациклические индуцированные подграфы ограниченной степени в случайном графе Эрдёша-Реньи

2.1 Существующие и новые результаты

2.2 Кодирование деревьев с заданным независимым множеством

2.3 Количество деревьев с заданным индуцированным подграфом

2.4 Количество деревьев ограниченной степени

2.5 Количество корневых лесов ограниченной степени

2.6 Ожидание числа корневых лесов ограниченной степени

2.7 Индуцированные деревья ограниченной степени в плотном случайном графе

2.8 Индуцированные леса ограниченной степени в плотном случайном графе

2.9 Индуцированные леса ограниченной степени в разреженном случайном графе

2.9.1 Доказательство Теоремы 14 о концентрации в интервале

о(1/р)

3 Ациклические индуцированные подграфы неограниченной степени в случайном графе Эрдёша-Реньи

3.1 Существующие и новые результаты

3.2 Количество корневых лесов с заданным индуцированным подграфом

3.3 Ожидание и дисперсия числа корневых лесов ограниченной степени

3.4 Доказательство Теоремы 20 о концентрации в интервале о(1/р)

Заключение

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

Работы автора по теме диссертации

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

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

Введение

Объектом исследования настоящей работы являются биномиальные случайные графы, представляющие собой наиболее распространённую модель случайного графа. Биномиальный случайный граф Я(О,р) получается из простого (неориентированного, без петель и кратных рёбер) графа О независимым удалением каждого его ребра с вероятностью (1 — р). Все графы, рассматриваемые в данной работе, простые. Поскольку всегда Я(О,р) С О, случайный граф Я(О,р) также называют биномиальным случайным подграфом графа О. Термин «биномиальный» обусловлен биномиальной схемой независимых испытаний, также известной как схема Бернулли, в соответствии с которой выбираются рёбра графа О. Такое определение является обобщением классической модели Эрдёша-Реньи случайного графа О(п,р) [1, 2], вводимого как случайный граф, рёбра которого проводятся независимо с вероятностью р между каждой парой п фиксированных вершин, т.е. фактически О(п,р) = Я(Кп,р), где Кп — полный граф на п вершинах.

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

. 0,р = о( Р(Я(О(п),р) еА) ^ {

1,р = ш(р).

В случае, если Р(Я(О(п),р) е А) ^ 1, также говорят, что Я(О(п),р) е А выполняется асимптотически почти наверное (а.п.н.).

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

тонкая классификация порогов. Порог р называется точным, если Уе > 0:

. 0, р < (1 — е)р,

Р(д(С(п),р) еЛ) ^ { у '

1,р> (1 + е)р.

Точные пороги существуют уже не для любого (даже монотонного) свойства. Значения порогов, и вообще асимптотическое поведение свойств случайного графа имеют богатую историю изучения [4—12].

Одним из наиболее хорошо изученных свойств является возрастающее свойство Лн содержания (хотя бы одной) копии фиксированного графа Н (т.е. подграфа, изоморфного графу Н) в случайном графе С(п,р). Вычисление порога свойства Лн для произвольного фиксированного Н можно найти в классических работах [8, 9, 11]. Асимптотическое пуассоновское распределение числа копий фиксированного строго сбалансированного графа при пороговом значении р установлено в [9]. Также известно, что число копий сбалансированного (но не строго) графа также сходится к некоторому распределению, но необязательно пуассоновскому [13]. Асимптотическая нормальность числа копий фиксированного графа для достаточно большого р установлена в [10—12].

Менее изучены свойства, связанные с индуцированными подграфами, т.е. максимальными по включению подграфами на заданном подмножестве вершин. В частности, актуальным является изучение распределения наибольшего размера (числа вершин) индуцированного подграфа в С(п,р), принадлежащего заданному классу графов, например, наибольшего размера пустого подграфа [14—16], подграфа ограниченной максимальной степени [17], подграфа ограниченной средней степени [18], подграфа заданной средней степени [19], пути и цикла [20, 21], дерева [19, 20, 22], леса [21, 23], паросочетания [24]. Данная задача интересна, помимо прочего, тем, что для различных классов графов, перечисленных выше, результаты и применяемые для их получения методы весьма схожие. Из методов обычно используются классические методы первого и второго момента, а также концентрационные неравенства Азумы или Талаграна [25]. Наибольший же размер подграфа во всех перечисленных выше

пЫ(пр)+0(1)

случаях оказывается сконцентрированным в окрестности величины 2 - ¿ц(1 _р) • Тем не менее, нам известна всего лишь одна статья [26], опубликованная в 2000 году Боллобашем и Томасоном, в некоторой мере обобщающая данные

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

В настоящей работе можно выделить следующие основные направления исследования свойств биномиальных случайных графов:

• пороги содержания подграфов в биномиальном случайном графе Gp(n, r, s), определяемом ниже (1), который является обобщением случайного графа Эрдёша-Реньи (Глава 1);

• предельное распределение наибольшего размера индуцированных подграфов в биномиальном случайном графе Эрдёша-Реньи G(n,p) (Главы 2, 3).

Биномиальный случайный граф Ор(п, г, в)

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

Ор(п,г,в):= Я(О(п, г, в),р), (1)

где О(п,г, в) — простой граф, вершинами которого являются все г-элементные подмножества некоторого п-элементного множества, а рёбра соединяют вершины, имеющие ровно в общих элементов. Формально, пусть 0 < в < г < п — целые числа. Тогда О(п, г, в) = (V, Е), где

У = С Щ-: \Х\ = г} , Е = {{х,у} С V : \х П у\ = в} .

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

G(n,r,s) = G(n, 1,0) = Kn. Интерес к изучению асимптотических свойств случайных графов Gp(n,r, s) возник около десяти лет назад. С тех пор им был посвящён ряд работ [27—38].

История изучения самих графов G(n,r,s), на основе которых строится случайный граф Gp(n,r,s), уходит корнями ещё в прошлый век [39, 40]. К сожалению, эти графы не имеют устоявшегося названия. В литературе они фигурируют как

• обобщённые графы Джонсона [41—46];

• однородные графы подмножеств (uniform subset graphs) [39, 40, 47, 48];

• дистанционные графы [27, 28, 34, 49];

• полные дистанционные графы [32, 36];

• дистанционные графы специального вида без определённого названия [29, 30, 50—58].

Последний вариант названия встречается в большинстве известных нам работ, посвящённых графам G(n,r,s). Тем не менее, отдельные авторы отождествляют G(n,r, s) с (полными) дистанционными графами, что не совсем удачно, так как (полными) дистанционными графами обычно называют гораздо более широкий класс графов, а именно, графы с вершинами в некотором метрическом пространстве и рёбрами, соединяющими (все) пары вершин, находящихся на заданном расстоянии друг от друга [51, 59]. Название «однородные графы подмножеств» (англ. "uniform subset graphs") вводится в статье [39], где графы G(n,r,s) впервые рассматриваются как класс, однако не получает широкого распространения. Мы предлагаем отдать предпочтение термину «обобщённые графы Джонсона» для обозначения G(n,r, s) и, соответственно, выбрать термин «случайные обобщённые графы Джонсона» для Gp(n,r,s). Во-первых, графы G(n,r,s) связаны с хорошо изученным объектом из такого раздела алгебраической комбинаторики как теория ассоциативных схем [60—62], а именно, они задают ассоциативную схему Джонсона, так что матрица смежности графа G(n, r, s) есть не что иное, как (r — s^-е отношение в ассоциативной схеме Джонсона с r классами (см. [61]). Во-вторых, если положить s = r — 1, определение графа G(n,r, s) совпадает с широко известным

определением графа Джонсона. При этом оба термина «ассоциативная схема Джонсона» и «граф Джонсона» происходят от имени Зелмера Джонсона, американского математика, известного своими работами в теории кодирования (в частности, верхней оценкой на мощность корректирующих кодов, известной как граница Джонсона [63]), из которых и были заимствованы идеи для построения ассоциативной схемы и графа Джонсона. Ввиду вышеперечисленного, графы О(п,г,в) и вовсе можно было бы назвать просто «графы Джонсона», если бы это название уже не закрепилось за их частным случаем О(п,г,г — 1). Отметим, что граф Кнезера также является частным случаем О(п,г,в) при в = 0, однако термин «обобщённый граф Кнезера» используется для обозначения графов с несколько иной конструкцией [46, 64—67].

В том или ином виде графы О(п,г, в) встречаются в различных разделах дискретной математики. С одной стороны, как уже было упомянуто, они задают отношения в ассоциативной схеме Джонсона [61], обобщают графы Джонсона О(п,г,г — 1) [68—73] и графы Кнезера О(п,г, 0) [74—81], представляющие самостоятельный интерес для изучения в теории графов. С другой стороны, они являются частным случаем дистанционных графов в пространстве Кп с евклидовой метрикой, применяющихся в решении задач комбинаторной геометрии (задача Нельсона-Хадвигера о хроматическом числе х(^п), проблема Борсука о разбиении множества в Кп на подмножества меньшего диаметра, а также различные обобщения этих задач) [51, 82, 83].

Из классических задач теории графов в О(п,г,в) изучаются, например, связность [45], сильная регулярность [41], обхват и диаметр [43, 47], а также гамильтоновость [39, 46]. Стоит отметить, что последняя задача полностью решена для О(п,г,в). Известно, что все связные графы О(п,г,в) за исключением графа Петерсона О(5, 2,0) = О(5,3,1) имеют гамильтонов цикл.

При изучении О(п,г,в) как дистанционного графа обычно используют следующее эквивалентное его определение как графа на подмножестве вершин куба [0,1]п С Кп:

V = {х е{0,1}п С Кп : \\x\li = г} , Е = {{х,у} : \\х — у\\2 = \/2(г — •

Из такого определения следует несложное соотношение

> х(0.п) > х(@(п, г, .в)), позволяющее получать нижние оценки на х(^п) и х(0п) [82, 84—90] в задаче Нельсона-Хадвигера. Аналогично получаются нижние оценки на число Борсука /(^ [82, 91] на основе соотношения / ((П)) > х(@(п, г, в)), следующего из определённого вложения графа С(п, г, в) в пространство [83]. В свою очередь, хроматическое число х(@(п,г,в)) обычно оценивается снизу с помощью числа независимости а(С(п,г, в)) из соотношения х(^(п,г,в)) > \У\/а(С(п,г,в)). Впоследствии нахождение числа х(С(и, г, в)) стало рассматриваться и как самостоятельная задача [52, 53, 58].

Число независимости а(С(п, г, в)) также имеет самостоятельную историю изучения в экстремальной теории множеств как частный случай более общей проблемы о наибольшем семействе г-элементных подмножеств некоторого п-элементного множества (или, что то же самое, о наибольшем числе рёбер в г-однородном гиперграфе на п вершинах) с запрещёнными мощностями пересечения, т.е. удовлетворяющем некоторым ограничениям на количество элементов в попарных пересечениях подмножеств из этого семейства (рёбер гиперграфа). Если запрещена только одна мощность пересечения в, такие семейства по определению являются независимыми множествами в графе С(п,г,в). К классическим результатам можно отнести известные теоремы Эрдёша-Ко-Радо [92] и Франкла-Уилсона [85], а также ряд работ [93—96]. Имеются и более новые результаты [97—99]. Отметим, что данная проблема также известна в теории кодирования как задача о кодах с запрещёнными расстояниями [83, 96, 100].

При изучении х(^(п, г, в)) и а(С(п, г, в)) естественным образом возникает вопрос стабильности этих чисел в случайном подграфе Ср(п,г,в) графа С(п,г,в), т.е. насколько сильно отличаются х(^р(п,г, в)) и а(Ср(п,г, в)) от соответственно х(@(п,г, в)) и а(С(п,г,в)) при различных значениях вероятности ребра р. В той или иной мере на этот вопрос удалось ответить для а(Ср(п,г, 0)) [31, 101], а(Ср(п,г, 1)) [35], х(Ср(п, 3,1)) [37], х(Ор(п,г, 0)) [33], х(Ср(п, 2в + 1, в)) [29] и для общего случая а(Ор(п,г, в)) [30, 34, 38] и х(Ср(п,г,в)) [30].

Помимо работ, посвящённых исследованию хроматического числа и числа независимости случайного графа Ср(п,г,в), существуют исследования числа копий фиксированного графа в Ср(п,г,в) при п ^ ж и фиксированных г и в [32], обобщающие большинство из результатов [8—13], полученных для

случайного графа Эрдёша-Реньи G(n,p).

В настоящей работе мы пойдём ещё дальше и рассмотрим подграфы переменного размера (т.е. размера, зависящего от n) в случайных графах Gp(n,r,s) при фиксированных r и s. В наиболее общем виде подграфы переменного размера можно ввести как последовательность произвольных графов H(n) и изучать их асимптотическое поведение в Gp(n, r, s) при n ^ (при r = const и s = const). Прежде всего нас будет интересовать вероятность P (Gp(n,r,s) <Е AH(„)), где AH(n) — свойство содержания копии графа H(n) в качестве подграфа.

Ясно, что при H(n) = const получается задача о подграфе, изоморфном фиксированному графу, описанная выше. Ещё одним важным частным случаем является H(n) = CN, где N = \V(Gp(n,r, s))\ — число вершин случайного графа. Это не что иное, как задача о гамильтоновом цикле. В случайном графе Эрдёша-Реньи G(n,p) известен порог появления гамильтонова цикла [6, 102]. Имеются и некоторые результаты относительно количества гамильтоновых циклов в G(n,p) [103—106]. Мы же рассмотрим графы в каком-то смысле промежуточного размера, т.е. растущего, но не слишком быстро.

Так как рассматривать переменные подграфы общего вида затруднительно, то разумно начать с частных случаев. Наиболее удобным для анализа классом графов, имеющим естественную параметризацию, представляются простые циклы Ct длины t. В пользу рассмотрения именно циклов также можно привести следующие аргументы:

• Циклы представляют отдельный интерес в теории графов. Классическими являются задачи подсчёта циклов фиксированного размера [107—114], поиска циклов, в частности, эйлеровых циклов и гамильтоновых циклов [39, 46]. Также имеются классические характеристики графа, связанные с циклами, например, обхват [43, 47] (который, стоит отметить, также играет особую роль в дистанционных графах в свете проблем Нельсона-Хадвигера и Борсука [59]).

• Самостоятельный интерес к циклам возникает и в теории случайных графов. Хорошо изучены свойство ацикличности, размер и количество унициклических компонент в случайном графе Эрдёша-Реньи G(n,p) [3]. Также, как упоминалось выше, в случайных графах изучаются гамильтоновы циклы [6, 102—106].

• В графах Gp(n, r, s) анализ произвольных связных подграфов, изоморфных фиксированному графу, сводится к рассмотрению циклов с помощью ушного разложения (англ. ear decomposition) двусвязных компонент подграфа [32]. Есть надежда, что подобный подход впоследствии можно будет применить и для подграфов переменного размера.

Порог появления копии цикла Ct в Gp(n,r,s) при t = t(n) ^ рассматривается для определённого класса функций t(n) в Главе 1. В этой главе также изучается естественным образом возникающий в ходе вычисления пороговой вероятности вопрос о числе копий Ct в графе G(n, r, s).

Наибольшие индуцированные подграфы в случайном графе Эрдёша-Реньи

Здесь мы подробнее опишем историю исследования наибольших индуцированных подграфов в G(n,p). Изучение наибольших индуцированных подграфов было инициировано Боллобашем и Эрдёшем, которые впервые рассмотрели число независимости a(G(n,p)) (которое есть не что иное, как наибольший размер индуцированного пустого подграфа) плотного (p = const) случайного графа G(n,p). В своей работе [14] они доказали, что существует функция f (n) ~ 2 log?(np), где q = —, такая что при n ^ с вероятностью, стремящейся к 1 (асимптотически почти наверное, а.п.н.)

f (n) < a(G(n,p)) < f (n) + 1.

Вслед за этим появился ряд работ, демонстрирующих, что приведенный выше результат справедлив не только для числа независимости, но и для наибольшего размера индуцированного подграфа ограниченной максимальной степени [17], подграфа ограниченной средней степени [18], подграфа заданной средней степени [19], пути и цикла [20], дерева [19], леса [23], хотя функции f (n) для этих классов отличаются (при одинаковой асимптотике f (n) ~ 2 log?(np)). Результаты такого типа называются двухточечной концентрацией, поскольку распределение рассматриваемой случайной величины (например, a(G(n,p))) асимптотически сосредоточено не более чем в двух целых значениях. Упомянутый выше довольно общий результат Боллобаша [26] указывает на то, что асимптотика f (n) ~ 2 log? (np) связана с разреженностью перечисленных выше классов графов (деревья, леса, пути, циклы, графы ограниченной средней

или максимальной степени). Здесь под разреженностью класса графов S, понимается соотношение limsup max \E(G)\/k2 = 0, т.е. разреженность

k^+ж Ggs,\V(G)\=k

графов, принадлежащих классу S. Из доказанного в [26] результата следует, что наибольший размер произвольного заданного разреженного наследуемого свойства асимптотически сконцентрирован в (2 ± е) log?(np) для произвольного заданного е > 0. На самом деле, довольно легко доказать верхнюю оценку (2 + е) log?(np) для произвольного разреженного класса графов, в то время как основная сложность возникают с доказательством нижней оценки (2 — е) log?(np). Хотя из перечисленных выше классов графов наследуемыми являются лишь леса и графы ограниченной максимальной степени, можно предположить, что результат из [26] обобщается и на другие семейства классов графов. Например, примечательно, что деревья являются максимальными по включению лесами (на фиксированном множестве вершин), а циклы являются максимальными по включению графами максимальной степени < 2, так что можно предположить, что возможно обобщение на максимальные по включению графы наследуемых классов.

Оказывается, что в разреженных (p ^ 0) случайных графах G(n,p) наибольший размер индуцированных подграфов многих классов (опять же разреженных) также сконцентрирован в окрестности 2 log?(np), хотя и не обязательно в двух точках. Например, для числа независимости двухточечная концентрация сохраняется вплоть до p > n—2/3+£ (для произвольного е > 0), в то время как при ш(1/п) < p < o(lnn/n)2/i есть серьёзные основания полагать, что двухточечной концентрации уже нет (хотя это строго не доказано) [115]. Для наибольших индуцированных путей и циклов известно, что двухточечная концентрация их размера есть при p > (lnп)2/л/п [116]. Концентрация в интервале длины O(1/p) доказана для наибольшего размера индуцированного дерева при p > (lnп)2/л/п [116]. Асимптотическая концентрация в интервале (2 ± е) log?(np) для фиксированного е > 0 и C£/n < p = o(1), где C£ — достаточно большая константа, зависящая от е, известна для наибольшего размера индуцированного пустого подграфа [15], дерева [20, 22] (в [22] доказательство приведено для p = C£/n, но работает и для больших p), паросочетания [24], пути и цикла [21], леса с компонентами изоморфными произвольному фиксированному дереву [21]. Отметим, что паросочетание также является максимальным по включению графом наследуемого класса графов

максимальной степени < 1, что косвенно говорит в пользу приведённой выше гипотезы обобщения результата [26].

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

Попытка получить промежуточный результат, более слабый, чем двухточечная концентрация, но более сильный, чем асимптотика, сразу для (почти) всего диапазона значений р была предпринята Фризом в своей работе [15]. Он доказал, что существует функция ] (п) ~ 2 logq (пр), такая что для любого £ > 0, если С£/п < р = о(1), где С£ — достаточно большая константа, зависящая от £, то а.п.н.

£

\а(С(п,р)) - /(п)\< -.

р

Заметим, что в случае р = С£/п этот результат совпадает с асимптотикой. Если же пр ^ то /(п) ~ 21прпр) и р = о(/(п)), что означает, что данный

результат сильнее простой асимптотики. Хотя нам не известны другие результаты такого рода, есть основания полагать, что концентрация в интервале размера о(1/р) имеет место для большинства упомянутых выше классов графов, для которых выполняются двухточечная концентрация и асимптотика. Это предположение доказывается для лесов в Главе 3 и для лесов ограниченной степени в Главе 2. Также в Главе 2 доказывается двухточечная концентрация для лесов ограниченной степени и деревьев ограниченной степени.

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

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

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

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

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

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

случайном графе а.п.н.

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

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

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

3. Доказана концентрация в интервале размера o(1/p) наибольшего размера индуцированного леса ограниченной и неограниченной степени в случайном графе Эрдёша-Реньи.

4. Доказана двухточечная концентрация наибольшего размера индуцированного дерева и леса ограниченной степени в плотном случайном графе Эрдёша-Реньи.

Достоверность. Все результаты работы обоснованы с приведением строгих математических доказательств. Достоверность результатов также подтверждается публикацией в рецензируемых научных журналах квартилей Q1 и Q2 (согласно Scopus).

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

• Вторая конференция Математических центров России 7-11 ноября 2022 г, МГУ, г Москва;

• 65-я Всероссийская научная конференция МФТИ 3-8 апреля 2023 г, МФТИ, г. Долгопрудный;

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

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

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения. Полный объём диссертации составляет 106 страниц. Список литературы содержит 128 наименований.

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

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

Глава 1. Циклы в случайных обобщённых графах Джонсона

1.1. Существующие и новые результаты

В данной главе рассматривается случайный граф Ср(п,г,в), определённый в (1), являющийся биномиальным случайным подграфом графа С(п,г,в). Напомним, что вершинами графа С(п, г, в) являются все г-элементные подмножества графа множества [п] (множество целых чисел от 1 до п), а рёбра соединяют те и только те вершины, которые имеют ровно в общих элементов. Случайный граф Ср(п,г,в) получается из С(п,г,в) удалением каждого ребра независимо от других с вероятностью 1 — р. Здесь и далее мы считаем, что г и в фиксированы, а п ^ Общее количество вершин в графе С(п,г,в)

Список литературы диссертационного исследования кандидат наук Кожевников Владислав Сергеевич, 2024 год

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

1. Erdos P., Renyi A. On Random Graphs I // Publicationes Mathematicae Debrecen. — 1959. — Vol. 6. — P. 290-297.

2. Gilbert E. ^.Random Graphs // The Annals of Mathematical Statistics. — 1959. —Vol. 30, no. 4.—P. 1141-1144. — DOI: 10.1214/aoms/1177706098.

3. S. Janson, T. Luczak, A. Rucinski. Random Graphs. — New York : Wiley, 2000.

4. Bollobas B., Thomason A. G. Threshold functions // Combinatorica. — 1987. — Vol. 7, no. 1. —P. 35-38. —DOI: 10.1007/bf02579198.

5. Schurger K. On the evolution of random graphs over expanding square lattices // Acta Mathematica Academiae Scientiarum Hungaricae. — 1976. —Vol. 27, no. 3/4. — P. 281-292. — DOI: 10.1007/bf01902105.

6. Komlos J., Szemeredi E. Limit distribution for the existence of hamiltonian cycles in a random graph // Discrete Mathematics. — 1983. — Vol. 43, no. 1.—P. 55-63.—DOI: 10.1016/0012-365x(83)90021-3.

7. Friedgut E., Rodl V., Rucinski A., Tetali P. A sharp threshold for random graphs with a monochromatic triangle in every edge coloring // Memoirs of the American Mathematical Society. — 2006. — Vol. 179, no. 845. — DOI: 10.1090/memo/0845.

8. 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.

9. Bollobas B. Threshold functions for small subgraphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1981. — Vol. 90, no. 2.—P. 197-206. —DOI: 10.1017/s0305004100058655.

10. Karonski M., Rucinski A. On the number of strictly balanced subgraphs of a random graph // Graph Theory. — Springer Berlin Heidelberg, 1983. — P. 79-83. —DOI: 10.1007/bfb0071616.

11. Rucinski A., Vince A. Strongly balanced graphs and random graphs // Journal of Graph Theory. — 1986. — Vol. 10, no. 2. — P. 251-264. — DOI: 10.1002/jgt. 3190100214.

12. RucinskiA. When are small subgraphs of a random graph normally distributed? // Probability Theory and Related Fields. — 1988. — Vol. 78, no. 1. — P. 1-10. — DOI: 10.1007/bf00718031.

13. Bollobas B., Wierman ./.Subgraph Counts and Containment Probabilities of Balanced and Unbalanced Subgraphs in a Large Random Graph // Annals of the New York Academy of Sciences. — 1989. — Vol. 576, 1 Graph Theory. — P. 63-70. —DOI: 10.1111/j.1749-6632.1989.tb16383.x.

14. Bollobas B., Erdos P. Cliques in random graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1976. — Vol. 80, no. 3. — P. 419427. — DOI: 10.1017/s0305004100053056.

15. Frieze A. On the independence number of random graphs // Discrete Mathematics. — 1990. — Vol. 81, no. 2. — P. 171-175. — DOI: 10.1016/0012-365x(90)90149-c.

16. Dani V., Moore C. Independent Sets in Random Graphs from the Weighted Second Moment Method // Lecture Notes in Computer Science. — Springer Berlin Heidelberg, 2011. — P. 472-482. — DOI: 10.1007/978-3-642-22935-0_40.

17. Fountoulakis N., Kang R. /., McDiarmid C. The t-Stability Number of a Random Graph // The Electronic Journal of Combinatorics. — 2010. — Vol. 17, no. 1. — DOI: 10.37236/331.

18. Fountoulakis N., Kang R. /., McDiarmid C. Largest sparse subgraphs of random graphs // European Journal of Combinatorics. — 2014. — Vol. 35. — P. 232244. —DOI: 10.1016/j.ejc.2013.06.012.

19. Kamaldinov D., Skorkin A., Zhukovskii M. Maximum sparse induced subgraphs of the binomial random graph with given number of edges // Discrete Mathematics. — 2021. — Vol. 344, no. 2. — P. 112205. — DOI: 10.1016/j.disc.2020.112205.

20. Dutta K., Subramanian C. On Induced Paths, Holes and Trees in Random Graphs // 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). — Society for Industrial, Applied Mathematics, 2018. — P. 168-177. — DOI: 10.1137/1.9781611975062.15.

21. Draganic N., Glock S., Krivelevich M. The largest hole in sparse random graphs // Random Structures & Algorithms. — 2022. — Vol. 61, no. 4. — P. 666-677. — DOI: 10.1002/rsa.21078.

22. de la Vega W F. The largest induced tree in a sparse random graph // Random Structures and Algorithms. — 1996. — T. 9, № 1/2. — C. 93—97. — DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<93::aid-rsa6>3.0.co;2-6.

23. Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Applied Mathematics. — 2021. — T. 305. — C. 211—213. — DOI: 10.1016/j.dam.2021.08.018.

24. Cooley O., Draganic N., Kang M., Sudakov B. Large Induced Matchings in Random Graphs // SIAM Journal on Discrete Mathematics. — 2021. — Vol. 35, no. 1. —P. 267-280. —DOI: 10.1137/20m1330609.

25. /anson S., Luczak T., Rucinski A. Random Graphs. — John Wiley & Sons, Inc., 2000. — DOI: 10.1002/9781118032718.

26. Bollobas B., Thomason A. The Structure of Hereditary Properties and Colourings of Random Graphs // Combinatorica. — 2000. — Vol. 20, no. 2. — P. 173-202.—DOI: 10.1007/s004930070019.

27. Zhukovskii M.E. A weak zero-one law for sequences of random distance graphs // Sbornik: Mathematics. — 2012. — Vol. 203, no. 7. — P. 1012-1044. — DOI: 10.1070/sm2012v203n07abeh004252.

28. Zhukovskii M. E. On the probability of the occurrence of a copy of a fixed graph in a random distance graph // Mathematical Notes. — 2012. — Vol. 92, no. 6. — P. 756-766.—DOI: 10.1134/s000143461211020x.

29. Gusev A. S. New upper bound for the chromatic number of a random subgraph of a distance graph // Mathematical Notes. — 2015. — Vol. 97, no. 3/4. — P. 326332. — DOI: 10.1134/s0001434615030037.

30. Bogolubsky L. I., Gusev A. S., Pyaderkin M. M., Raigorodskii A. M. Independence numbers and chromatic numbers of the random subgraphs of some distance graphs // Sbornik: Mathematics. — 2015. — Vol. 206, no. 10. — P. 1340-1374.—DOI: 10.1070/sm2015v206n10abeh004498.

31. Bollobás B., Narayanan B. P., Raigorodskii A. M. On the stability of the Erdós-Ko-Rado theorem // Journal of Combinatorial Theory, Series A. — 2016. — Vol. 137. — P. 64-78. — DOI: 10.1016/jjcta.2015.08.002.

32. Burkin A. V. Small Subgraphs in Random Distance Graphs // Theory of Probability & Its Applications. — 2016. — Vol. 60, no. 3. — P. 367-382. — DOI: 10.1137/s0040585x97t987739.

33. Kupavskii A. On random subgraphs of Kneser and Schrijver graphs // Journal of Combinatorial Theory, Series A. — 2016. — Vol. 141. — P. 8-15. — DOI: 10.1016/j.jcta.2016.02.003.

34. Pyaderkin M. M. Independence numbers of random subgraphs of distance graphs // Mathematical Notes. — 2016. — Vol. 99, no. 3/4. — P. 556-563. — DOI: 10.1134/s0001434616030299.

35. Pyaderkin M. On the stability of some Erdós-Ko-Rado type results // Discrete Mathematics. — 2017. — Vol. 340, no. 4. — P. 822-831. — DOI: 10.1016/j. disc.2016.11.015.

36. Burkin A. V., Zhukovskii M. E. Small subgraphs and their extensions in a random distance graph // Sbornik: Mathematics. — 2018. — Vol. 209, no. 2. — P. 163-186.—DOI: 10.1070/sm8674.

37. Pyaderkin M. On the chromatic number of random subgraphs of a certain distance graph // Discrete Applied Mathematics. — 2019. — Vol. 267. — P. 209-214. — DOI: 10.1016/j.dam.2019.07.002.

38. Pyaderkin M. M. On Threshold Probability for the Stability of Independent Sets in Distance Graphs // Mathematical Notes. — 2019. — Vol. 106, no. 1/2. — P. 274-285. —DOI: 10.1134/s0001434619070307.

39. Chen B.-L., Lih K.-W. Hamiltonian uniform subset graphs // Journal of Combinatorial Theory, Series B. — 1987. — Vol. 42, no. 3. — P. 257-263. — DOI: 10.1016/0095- 8956(87)90044-x.

40. Simpson J. E. On uniform subset graphs // Ars Combinatoria. — 1994. — Vol. 37.—P. 309-318.

41. Cannon A. D., Bamberg J., Praeger C. E. A Classification of the Strongly Regular Generalised Johnson Graphs // Annals of Combinatorics. — 2012. — Vol. 16, no. 3. — P. 489-506. — DOI: 10.1007/s00026-012-0142-9.

42. Molitierno J. J. Entries of the group inverse of the Laplacian matrix for generalized Johnson graphs // Linear and Multilinear Algebra. — 2017. — Vol. 66, no. 6.—P. 1153-1170. —DOI: 10.1080/03081087.2017.1340432.

43. Agong L. A., Amarra C., Caughman J.S., Herman A. J., Terada T. S. On the girth and diameter of generalized Johnson graphs // Discrete Mathematics. — 2018.— Vol. 341, no. 1.—P. 138-142.—DOI: 10.1016/j.disc.2017.08.022.

44. Kok J.Note: Vertex stress in generalized Johnson graphs of diameter 2 // Open Journal of Discrete Applied Mathematics. — 2022. — Vol. 5, no. 2. — P. 6-11. — DOI: 10.30538/psrp-odam2022.0073.

45. Yu Z., Xu L., WuX., Zheng C. On the Super (Edge)-Connectivity of Generalized Johnson Graphs // International Journal of Foundations of Computer Science. — 2023.—P. 1-15.—DOI: 10.1142/s012905412350017x.

46. Merino A., Mütze T., Namrata. Kneser graphs are Hamiltonian. — 2023. — arXiv: 2212.03918 [math.CO].

47. Chen Y., Wang W. Diameters of uniform subset graphs // Discrete Mathematics. — 2008. — Vol. 308, no. 24. — P. 6645-6649. — DOI: 10.1016/j.disc.2007.11.031.

48. Bahmani A., Emami M., Naserian O. Dominating sets for uniform subset graphs // Linear and Multilinear Algebra. — 2022. — P. 1-13. — DOI: 10.1080/03081087.2022.2158295.

49. Pyaderkin M. M. On Threshold Probability for the Stability of Independent Sets in Distance Graphs // Mathematical Notes. — 2019. — Vol. 106, no. 1/2. — P. 274-285. —DOI: 10.1134/s0001434619070307.

50. Mikhailov K. A., Raigorodskii A. M. On the Ramsey numbers for complete distance graphs with vertices in {0,1}n // Sbornik: Mathematics. — 2009. — Vol. 200, no. 12. — P. 1789-1806. — DOI: 10.1070/sm2009v200n12abeh004059.

51. Raigorodskii A. M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory / ed. by J. Pach. — Springer New York, 2013.—P. 429-460.

52. Balogh JKostochka A. V., Raigorodskii A. Coloring some finite sets in Rn // Discussiones Mathematicae Graph Theory. — 2013. — Vol. 33, no. 1. — P. 25. — DOI: 10.7151/dmgt.1641.

53. Bobu A. V., Kostina O. A., Kupriyanov A. E. Independence numbers and chromatic numbers of some distance graphs // Problems of Information Transmission. — 2015. — Vol. 51, no. 2. — P. 165-176. — DOI: 10.1134/s0032946015020076.

54. Pushnyakov F. A. On the number of edges in induced subgraphs of a special distance graph // Mathematical Notes. — 2016. — Vol. 99, no. 3/4. — P. 545-551.—DOI: 10.1134/s0001434616030275.

55. Pushnyakov F. A. The Number of Edges in Induced Subgraphs of Some Distance Graphs // Mathematical Notes. — 2019. — Vol. 105, no. 3/4. — P. 582-591. — DOI: 10.1134/s0001434619030313.

56. Pushnyakov F. A., Raigorodskii A. M. Estimate of the Number of Edges in Special Subgraphs of a Distance Graph // Mathematical Notes. — 2020. — Vol. 107, no. 1/2. —P. 322-332. —DOI: 10.1134/s0001434620010320.

57. Ogarok P. A., Raigorodskii A. M. On Stability of the Independence Number of a Certain Distance Graph // Problems of Information Transmission. — 2020. — Vol. 56, no. 4. — P. 345-357. — DOI: 10.1134/s0032946020040055.

58. Zakharov D. A. Chromatic Numbers of Some Distance Graphs // Mathematical Notes. — 2020. — Vol. 107, no. 1/2. — P. 238-246. — DOI: 10.1134/s000143462001023x.

59. Raigorodskii A. M. Cliques and cycles in distance graphs and graphs of diameters // Discrete Geometry and Algebraic Combinatorics / ed. by A. Barg, O. R. Musin. — American Mathematical Society, 2014. — P. 93-109. — DOI: 10.1090/conm/625/12493.

60. Bose R. C., Mesner D. M. On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs // The Annals of Mathematical Statistics. — 1959. — Vol. 30, no. 1. — P. 21-38. — DOI: 10.1214/aoms/1177706356.

61. Delsarte P. An algebraic approach to the association schemes of coding theory // Philips Res. Rep. Suppl. — 1973. — Vol. 10.

62. Bannai E., Ito T. Algebraic Combinatorics I: Association Schemes. — 1984.

63. Johnson S. A new upper bound for error-correcting codes // IEEE Transactions on Information Theory. — 1962. — Vol. 8, no. 3. — P. 203-207. — DOI: 10. 1109/tit.1962.1057714.

64. Frankl P. On the chromatic number of the general Kneser-graph // Journal of Graph Theory. — 1985. — Vol. 9, no. 2. — P. 217-220. — DOI: 10.1002/jgt. 3190090204.

65. Denley T. The Odd Girth of the Generalised Kneser Graph // European Journal of Combinatorics. — 1997. — Vol. 18, no. 6. — P. 607-611. — DOI: 10.1006/ eujc.1996.0122.

66. Chen Y., Wang Y. On the diameter of generalized Kneser graphs // Discrete Mathematics. — 2008. — Vol. 308, no. 18. — P. 4276-4279. — DOI: 10.1016/j.disc.2007.08.004.

67. Jafari A., Moghaddamzadeh M. J. On the chromatic number of generalized Kneser graphs and Hadamard matrices // Discrete Mathematics. — 2020. — Vol. 343, no. 2. —P. 111682. —DOI: 10.1016/j.disc.2019.111682.

68. Etzion T. On the Nonexistence of Perfect Codes in the Johnson Scheme // SIAM Journal on Discrete Mathematics. — 1996. — Vol. 9, no. 2. — P. 201-209. — DOI: 10.1137/s0895480194275692.

69. Etzion T., Bitan S. On the chromatic number, colorings, and codes of the Johnson graph // Discrete Applied Mathematics. — 1996. — Vol. 70, no. 2. — P. 163175. —DOI: 10.1016/0166-218x(96)00104-7.

70. Daven M., Rodger C. A. The Johnson graph J(v,k) has connectivity 8 // Congressus Numerantium. — 1999. — Vol. 139. — P. 123-128.

71. Etzion T., Brouwer A. Some new distance-4 constant weight codes // Advances in Mathematics of Communications. — 2011. — Vol. 5, no. 3. — P. 417-424. — DOI: 10.3934/amc.2011.5.417.

72. Alspach B. Johnson graphs are Hamilton-connected // Ars Mathematica Contemporanea. — 2012. — Vol. 6, no. 1. — P. 21-23. — DOI: 10.26493/1855-3974.291.574.

73. Heidari A., Mirafzal S. M. Johnson graphs are panconnected // Proceedings -Mathematical Sciences. — 2019. — Vol. 129, no. 5. — DOI: 10.1007/s12044-019-0527-3.

74. Lovasz L. Kneser's conjecture, chromatic number, and homotopy // Journal of Combinatorial Theory, Series A. — 1978. — Vol. 25, no. 3. — P. 319-324. — DOI: 10.1016/0097-3165(78)90022-5.

75. Brouwer A. E., Schrijver A. Uniform Hypergraphs // Packing and Covering in Combinatorics. Mathematical Centre Tracts. — 1979. —No. 106. —P. 39-73.

76. Poljak S., Tuza Z. Maximum bipartite subgraphs of Kneser graphs // Graphs and Combinatorics. — 1987. — Vol. 3, no. 1. — P. 191-199. — DOI: 10.1007/ bf01788540.

77. Chen Y.-C. Triangle-free Hamiltonian Kneser graphs // Journal of Combinatorial Theory, SeriesB. — 2003. — Vol. 89,no. 1.—P. 1-16.—DOI: 10.1016/s0095-8956(03)00040-6.

78. Matousek J. A Combinatorial Proof of Kneser's Conjecture* // Combinatorica. — 2004. — Vol. 24, no. 1. — P. 163-170. — DOI: 10.1007/s00493-004-0011-1.

79. Valencia-Pabon M., Vera J.-C. On the diameter of Kneser graphs // Discrete Mathematics. — 2005. — Vol. 305, no. 1-3. — P. 383-385. — DOI: 10.1016/j.disc.2005.10.001.

80. Östergärd P. R. J., Shao Z., XuX. Bounds on the domination number of Kneser graphs // Ars Mathematica Contemporanea. — 2014. — Vol. 9, no. 2. — P. 187195. — DOI: 10.26493/1855-3974.491.b02.

81. Mütze T., Nummenpalo J., Walczak B. Sparse Kneser graphs are Hamiltonian // Journal of the London Mathematical Society. — 2020. — DOI: 10.1112/jlms. 12406.

82. Raigorodskii A. M. Borsuk's problem and the chromatic numbers of some metric spaces // Russian Mathematical Surveys. — 2001. — Vol. 56, no. 1. — P. 103139. — DOI: 10.1070/rm2001v056n01abeh000358.

83. Raigorodskii A. M. Combinatorial Geometry and Coding Theory* // Fundamenta Informaticae. — 2016. — Vol. 145, no. 3. — P. 359-369. — DOI: 10.3233/FI-2016-1365.

84. Frankl P. Extremal Problems and Coverings of the Space // European Journal of Combinatorics. —1980. —Vol. 1,no. 2.—P. 101-106. —DOI: 10.1016/s0195-6698(80)80045-x.

85. Frankl P., Wilson R. M. Intersection theorems with geometric consequences // Combinatorica. — 1981. — Vol. 1, no. 4. — P. 357-368. — DOI: 10.1007/ bf02579457.

86. Chilakamarri K. B. On the chromatic number of rational five-space // Aequationes Mathematicae. — 1990. — Vol. 39, no. 2/3. — P. 146-148. — DOI: 10.1007/bf01833145.

87. Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space // Mathematika. — 1972. — Vol. 19, no. 1. — P. 1-24. — DOI: 10.1112/ s0025579300004903.

88. Cantwell K. Finite Euclidean Ramsey theory // Journal of Combinatorial Theory, Series A. — 1996. — Vol. 73, no. 2. — P. 273-285. — DOI: 10.1016/s0097-3165(96)80006-9.

89. Kupavskii A. B., Raigorodskii A. M. On the chromatic number of R9 // Journal of Mathematical Sciences. — 2009. — Vol. 163, no. 6. — P. 720-731. — DOI: 10.1007/s10958-009-9708-4.

90. Exoo G., Ismailescu D., Lim M. On the Chromatic Number of R4 // Discrete & Computational Geometry. — 2014. — Vol. 52, no. 2. — P. 416-423. — DOI: 10.1007/s00454-014-9612-7.

91. Kahn /., Kalai G. A Counterexample to Borsuk's Conjecture // Bulletin of the American Mathematical Society. —1993. — Vol. 29, no. 1. — P. 60-63. — DOI: 10.1090/s0273-0979-1993-00398-7.

92. Erdos P., Ko C., Rado R. Intersection theorems for systems of finite sets // The Quarterly Journal of Mathematics. — 1961. — Vol. 12, no. 1. —P. 313-320. — DOI: 10.1093/qmath/12.1.313.

93. Nagy Z. A constructive estimation of the Ramsey number // Matematikai Lapok. — 1974. — Vol. 23. — P. 301-302.

94. Frankl P. On families of finite sets no two of which intersect in singleton // Bulletin of the Australian Mathematical Society. — 1977. — Vol. 17, no. 1. — P. 125-134.—DOI: 10.1017/s0004972700025521.

95. Frankl P., Furedi Z. Forbidding just one intersection // Journal of Combinatorial Theory, Series A. — 1985. — Vol. 39, no. 2. — P. 160-176. — DOI: 10.1016/ 0097-3165(85)90035-4.

96. Frankl P., Rodl V. Forbidden intersections // Transactions of the American Mathematical Society. — 1987. — Vol. 300, no. 1. — P. 259-259. — DOI: 10.1090/s0002-9947-1987-0871675-6.

97. Ponomarenko E. I., Raigorodskii A. M. New estimates in the problem of the number of edges in a hypergraph with forbidden intersections // Problems of Information Transmission. — 2013. — Vol. 49, no. 4. — P. 384-390. — DOI: 10.1134/s0032946013040091.

98. Zvonarev A. E., Raigorodskii A. M., Samirov D. V., Kharlamova A. A. On the chromatic number of a space with forbidden equilateral triangle // Sbornik: Mathematics. — 2014. — Vol. 205, no. 9. — P. 1310-1333. — DOI: 10.1070/sm2014v205n09abeh004419.

99. Bobu A. V., Kupriyanov A. E., Raigorodskii A. M. Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection // Sbornik: Mathematics. — 2016. — Vol. 207, no. 5. — P. 652-677. — DOI: 10.1070/sm8473.

100. Bassalygo L., Cohen G., Zemor G. Codes with forbidden distances // Discrete Mathematics. —2000.—Vol. 213,no. 1-3.—P. 3-11.—DOI: 10.1016/s0012-365x(99)00161-2.

101. BALOGH J., BOLLOBAS B., NARAYANAN B. P. TRANSFERENCE FOR THE ERDOS-KO-RADO THEOREM // Forum of Mathematics, Sigma. — 2015. — Vol. 3.—DOI: 10.1017/fms.2015.21.

102. Posa L. Hamiltonian circuits in random graphs // Discrete Mathematics. — 1976. — Vol. 14, no. 4. — P. 359-364. — DOI: 10.1016/0012-365x(76)90068-6.

103. Bollobas B., Frieze A. M. On Matchings and Hamiltonian Cycles in Random Graphs // Random Graphs '83, Based on lectures presented at the 1st Poznan Seminar on Random Graphs. — Elsevier, 1985. — P. 23-46. — DOI: 10.1016/ s0304-0208(08)73611-9.

104. Frieze A., Krivelevich M. On two Hamilton cycle problems in random graphs // Israel Journal of Mathematics. — 2008. — Vol. 166, no. 1. — P. 221-234. — DOI: 10.1007/s11856-008-1028-8.

105. Krivelevich M., Samotij W. Optimal Packings of Hamilton Cycles in Sparse Random Graphs // SIAM Journal on Discrete Mathematics. — 2012. — Vol. 26, no. 3. — P. 964-982. — DOI: 10.1137/110849171.

106. Knox F., Kühn D., Osthus D. Edge-disjoint Hamilton cycles in random graphs // Random Structures & Algorithms. — 2013. — Vol. 46, no. 3. — P. 397-445. — DOI: 10.1002/rsa.20510.

107. Ross I. C., Harary F. On the determination of redundancies in sociometric chains // Psychometrika. — 1952. — Vol. 17, no. 2. — P. 195-208. — DOI: 10.1007/bf02288782.

108. Harary F., Ross I. C. The Number of Complete Cycles in a Communication Network // The Journal of Social Psychology. — 1954. — Vol. 40, no. 2. — P. 329-332.—DOI: 10.1080/00224545.1954.9714242.

109. Harary F., Manvel B. On the number of cycles in a graph // Matematicky casopis. — 1971. — Vol. 21. — P. 55-63.

110. Alon N., Yuster R., Zwick ^.Finding and counting given length cycles // Algorithmica. — 1997. — Vol. 17, no. 3. — P. 209-223. — DOI: 10.1007/bf02523189.

111. Chang Y. C., Fu H. L. The Number of 6-Cycles in a Graph // Bulletin of the ICA. — 2003. — Vol. 39. — P. 27-30.

112. Воропаев А. Н., Перепечко С. Н. Количество простых циклов фиксированной длины в неориентированном графе. Явные формулы в случае малых длин // Discrete and Continuous Models and Applied Computational Science. — 2012. — № 2. — С. 6—12.

113. Movarraei N., Boxwala S. A. On the Number of Cycles in a Graph // Open Journal of Discrete Mathematics. — 2016. — Vol. 06, no. 02. — P. 41-69. — DOI: 10.4236/ojdm.2016.62005.

114. Giscard P.-L., Kriege N., Wilson R. C. A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length // Algorithmica. — 2019. — Vol. 81, no. 7. — P. 2716-2737. — DOI: 10.1007/s00453-019-00552-1.

115. Bohman T., Hofstad J.Two-Point Concentration of the Independence Number of the Random Graph // Forum of Mathematics, Sigma. — 2024. — T. 12. — DOI: 10.1017/fms.2024.6.

116. Dutta K., Subramanian C. R. On Induced Paths, Holes, and Trees in Random Graphs // SIAM Journal on Discrete Mathematics. — 2023. — T. 37, № 1. — C. 279—303. — DOI: 10.1137/21m1409895.

117. Gao P, Isaev M., McKay B. Kim-Vu's sandwich conjecture is true for d > log4n. — 2023. — arXiv: 2011.09449 [math.CO].

118. Zhao Y. Spectral Distributions of Random Graphs //. — 2012.

119. Meyer C. Matrix Analysis and Applied Linear Algebra. — SIAM, 2000. — DOI: 10.1137/1.9780898719512.

120. Bapat R. B. Graphs and Matrices. — Springer London, 2014. — DOI: 10.1007/ 978-1-4471-6569-9.

121. Sinclair A. Improved bounds for mixing rates of Markov chains and multicommodity flow: Extended abstract // Lecture Notes in Computer Science. — Springer Berlin Heidelberg, 1992. — P. 474-487. — DOI: 10.1007/bfb0023849.

122. Glock S. Note on induced paths in sparse random graphs. — 2021. — DOI: 10.48550/ARXIV.2102.09289.

123. Moon J. W. Counting labelled trees. — 1970.

124. Bergeron F., Labelle G., Leroux P. Combinatorial Species and Tree-like Structures. — Cambridge University Press, 1997. — DOI: 10.1017/cbo9781107325913.

125. Flajolet P, Sedgewick R. Analytic Combinatorics. — Cambridge University Press, 2009. — DOI: 10.1017/cbo9780511801655.

126. Kozhevnikov V., Raigorodskii A., Zhukovskii M. Large cycles in random generalized Johnson graphs // Discrete Mathematics. — 2022. — Vol. 345, no. 3.—P. 112721.—DOI: 10.1016/j.disc.2021.112721.

127. Kozhevnikov V., Zhukovskii M. Large cycles in generalized Johnson graphs // Journal of Graph Theory. — 2023. — Vol. 104, no. 4. — P. 904-918. — DOI: 10.1002/jgt.23006.

128. Ахмеджанова М., Кожевников В. Индуцированные леса и деревья в случайном графе Эрдёша-Реньи // Доклады Российской академии наук. Математика, информатика, процессы управления. — 2024. — Т. 516, № 1. — С. 21—25. — DOI: 10.31857/S2686954324020041.