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

• Семенов Александр Сергеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Семенов Александр Сергеевич

1.3 Похожие задачи

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

1.4.1 Метод интерполяции

1.4.2 Аппроксимация моделей

1.4.3 Завершение доказательства

2 Закон больших чисел для независимых множеств общего вида

2.1 Основные определения

2.2 История задачи и новые результаты

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

2.4 Описание алгоритма

2.5 Классификация вершин гипердеревьев

2.6 Аппроксимация гипердеревьями

2.6.1 Случайное гипердерево

2.6.2 Аппроксимация моделей

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

3 Раскраски случайных гиперграфов

3.1 Основные определения

3.2 История задачи и новые результаты

3.3 Доказательство верхней оценки

3.4 Доказательство нижней оценки

3.4.1 Точная пороговая вероятность

3.4.2 Другая модель

3.4.3 Подсчет числа раскрасок

3.4.4 Подсчет моментов

3.4.5 Завершение доказательства

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

3.5.1 Оценки коэффициентов А(к,д)

3.5.2 Малые £ е [0,1/4 - й 1п к/к]

3.5.3 Средние £ е [1/4 - й 1п к/к, 1/4 - 2-2к/3]

3.5.4 Большие £ е [1/4 - 2-2к/3,1/4]

Заключение

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

Список работ автора по теме диссертации

Введение

Настоящая работа посвящена исследованию в области теории случайных гиперграфов. Вначале напомним, что гиперграфом Н называется пара множеств Н = (V, Е), где V = V(Н) — это некоторое конечное множество, элементы которого называются вершинами гиперграфа, а Е = Е(Н) — произвольная совокупность подмножеств V, которые принято называть ребрами гиперграфа Н. Нас будут интересовать только к-однородные гиперграфы, то есть такие, в которых каждое ребро состоит ровно из к вершин. Основным объектом изучения в диссертации является классическая биномиальная модель случайного гиперграфа Н(п,к,р), п > к ^ 2, п,к Е М, р Е (0,1). В этой модели каждое подмножество из к вершин случайно и независимо друг от друга с вероятностью р включается в множество ребер гиперграфа. Отметим, что величина р также может являться функцией от числа вершин р = р(п). При к = 2 модель Н(п,к,р) есть ни что иное, как классическая биномиальная модель случайного графа С(п,р).

Первые задачи в теории случайных графов были рассмотрены еще в 5060-е годы XX века в работах П. Эрдеша и А. Реньи [1], [2], [3]. Саму модель случайного графа С(п,р) также называют моделью Эрдеша-Реньи. С тех пор вышло множество работ посвященных различным свойствам и характеристикам случайного графа С(п,р), а также были написаны выдающиеся монографии [4], [5], [6] и [7].

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

Напомним, что множество вершин W С V в гиперграфе (графе) Н = (V, Е) называется независимым, если оно не содержит полных ребер внутри себя, т.е. для любого ребра А Е Е выполнено А ^ W. Максимальный

размер независимого множества в Н называется его числом независимости. Число независимости графа H принято обозначать через а(Н). Число независимости случайного графа G(n,p) активно изучалось начиная с 70-х годов. Вначале был исследован случай постоянного p в работах Д. Матулы [8], Дж. Гримметта и К. МакДиармида [9]. Окончательно вопрос был решен в совместной работе П. Эрдеша и Б. Боллобаша [10]. Далее последовал ряд обобщений в работах А. Фриза [11] и работе М. Бояти, Д. Гамарника и П. Тетали [13].

Многие из известных результатов для случайных графов естественным образом удалось перенести в теорию гиперграфов, но далеко не все. Например, теоремы для числа независимости случайных k-однородных гиперграфов Н(n,k,p) в случае не слишком быстро убывающего p были доказаны в работах М. Кривелевича и Б. Судакова [15], Дж. Шмидт, Э. Шамира и Э. Апфола [16], Э. Шамира [17]. В диссертации с помощью метода интерполяции получено обобщение результата М. Бояти, Д. Гамарника и П. Тетали для случайных гиперграфов при p = cn/(, где c > 0 фиксированное положительное число. В этой ситуации число ребер случайного гиперграфа Н(n, k,p) в среднем равно cn, т.е. оно в среднем линейно по числу вершин. Подобные гиперграфы принято называть разреженными.

В случае гиперграфов имеется возможность обобщения классического понятия независимых множеств и числа независимости. Пусть j — некоторое натуральное число. Множество вершин W С V в гиперграфе Н = (V, E) называется j-независимым, если каждое ребро гиперграфа имеет не более j вершин внутри W, т.е. для любого ребра A £ E выполнено |A П W| ^ j. Числом j-независимости гиперграфа Н называется максимальный размер j-независимого множества в Н и обозначается через aj (Н). В уже упомянутой работе [15] М. Кривелевич и Б. Судаков обосновали закон больших чисел для числа j-независимости только в случае не слишком быстро убывающего p = p(n), а точнее при p • (^ n, т.е. во всех случаях вплоть до разреженного. Для случая p = cn/(имеются лишь оценки вида ein и c2n для несовпадающих постоянных c1,c2 > 0. При помощи анализа алгоритма поиска максимального независимого множества в гиперграфе и анализа ветвящихся процессов в диссертации показано, что в случае p = cn/(при небольших значениях постоянной c может быть найден предел сходимости по вероятности отношения числа j-независимости к числу вершин.

Как уже было отмечено, еще одним важным направлением исследования являются раскраски графов и гиперграфов. Раскраской вершин гиперграфа Н = (V, E) в r цветов называется отображение множества вершин V в множество цветов {1,... ,r}. Раскраска гиперграфа Н называется правильной, если в ней каждый цветовой класс является независимым множеством

в H. Наименьшее число цветов, при котором существует правильная раскраска гиперграфа H, называется хроматическим числом гиперграфа H и обозначается х(Н). Задача о поиске асимптотического распределения хроматического числа случайного графа G(n,p) была поставлена Эрдешем еще в 60-е годы XX века. Почти 30 лет понадобилось на ее решение. Только в 1988 году в случае постоянного p в работе Б. Боллобаша [43] был доказан закон больших чисел для хроматического числа случайного графа. В случае же не слишком быстро убывающих p = o(n) аналогичный результат принадлежит Лучаку [44]. Множество работ (например, [45] — [48]) посвящено случаю np = c = const. В этом случае хроматическое число ограничено с вероятностью, стремящейся к 1. В связи с этим задачу оказалось возможным переформулировать в проблему поиска порогового значения c = c(r), до которого хроматическое число не будет превосходит заданное значение r с вероятностью, стремящейся к 1. Однако, поиск точного значения пороговой величины c(r) весьма затруднителен, в настоящее время известны лишь ее достаточно близкие оценки.

Первые нижние и верхние оценки порогового значения c для гиперграфов, в случае p = cn/ (были получены Алоном и Спенсером в совместной работе [49]. В своей работе они оценивали пороговую вероятность наличия правильной двухцветной раскраски. Их результат последовательно улучшался в работах Ахлиоптаса, Кима, Кривелевича и Тетали [50], Ахлиоптаса и Мура [51], Коджа-Оглана и Здеборовой [52] и, наконец, в некотором роде наилучший результат получили Коджа-Оглан и Панагиоту [53].

По аналогии с числом j-независимости рассматривают j-хроматическое число гиперграфа (цветовые классы должны быть j-независимыми множествами). Основные результаты о j-хроматическом числе случайного гиперграфа Н(n,k,p), при p, стремящемся к нулю при n ^ ж, можно найти в работах [15], [17], [41]. В диссертации рассматривается случай p = cn/(2), для которого при помощи методов первого и второго моментов получены верхняя и нижняя оценка для порогового значения постоянной c, до которого j-хроматическое число гиперграфа равняется двум с вероятностью, стремящейся к

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

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

Общая характеристика работы

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

Цель работы

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

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

Все результаты диссертации являются новыми и получены автором самостоятельно. Основные из них состоят в следующем.

1. Для числа независимости случайного гиперграфа Н(п, к,р) в разреженном случае р = сп/(доказан закон больших чисел.

2. Для числа ]-независимости случайного гиперграфа Н(п,к,р) в сильно разреженном случае р = сп/(, с £ (0, ] доказан закон больших чисел, а также найдена предельная константа, выраженная в виде решения некоторого трансцендентного уравнения.

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

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

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

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

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

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

Результаты диссертации докладывались:

1. на 58-й научной конференции Московского физико-технического института (г. Долгопрудный, 2015 г.);

2. на XXIII Международной конференции студентов, аспирантов и молодых учёных «Ломоносов» (г. Москва, 2016 г.);

3. на IX международной Петрозаводской конференции "Вероятностные методы в дискретной математике" (г. Петрозаводск, 2016 г.);

4. на международной конференции "Workshop on Combinatorics and Number Theory" в Литве (г. Вильнюс, 2017 г.);

5. на международной конференции "Random Structures and Algorithms" в Польше (г. Гнезно, 2017 г.);

6. на спецсеминаре "Экстремальная комбинаторика и случайные структуры" кафедры теории вероятностей механико-математического факультета МГУ (рук. Д.А. Шабанов, 2017 г.);

7. на "Большом семинаре кафедры теории вероятностей" механико-математического факультета МГУ (рук. академик А.Н. Ширяев, 2018 г.).

Публикации

Результаты диссертации опубликованы в работах [С1] - [С5] списка работ автора. Всего по теме диссертации опубликовано пять работ, из которых две в соавторстве. Работы [С1], [С3], [С5] опубликованы в журналах, индексируемых базами Web of Sciences и Scopus.

Структура работы

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

ляет 72 страницы, из них 4 страницы занимает список литературы (57 наименований).

Глава 1

Закон больших чисел для числа независимости случайного гиперграфа

Результаты главы опубликованы в работах [С1] - [С2].

1.1 Основные определения

Начнем с основных определений. Гиперграфом Н называется пара множеств Н = (V, Е), где V = V(Н) — это некоторое конечное множество, элементы которого называются вершинами гиперграфа, а Е = Е(Н) — произвольная совокупность подмножеств V, которые принято называть ребрами гиперграфа Н. Если каждое ребро А Е Е состоит ровно из к вершин (т.е. А — это к-подмножество V), то говорят, что гиперграф Н является к-однородным. В качестве примера к-однородного гиперграфа можно рассмотреть так называемый полный гиперграф на п вершинах т.е. такой гиперграф, у которого множество ребер состоит из всевозможных к-подмножеств его вершин. Если к = 2, то к-однородный гиперграф будет представлять собой обыкновенный граф.

Множество вершин W С V в гиперграфе Н = (V, Е) называется независимым, если оно не содержит полных ребер внутри себя, т.е. для любого ребра А Е выполнено А <£ W. Одной из важнейших характеристик гиперграфа Н является его число независимости — максимальный размер независимого множества в Н. Число независимости гиперграфа Н принято обозначать через а(Н).

Основным объектом изучения диссертационной работы является классическая биномиальная модель случайного гиперграфа Н(п,к,р), п > к ^ 2, п,к Е М, р Е (0,1). В этой модели случайный гиперграф является случайным элементом, принимающим значения на множестве всех к-однородных гиперграфов на множестве из п вершин Уп (например, Уп = {1,... , п}) и имеющий

следующее распределение: для любого Н' = (УП,Е') выполнено

р(Н (п,к,р) = Н') = р|Е,|(1 - р)(к)-|Е'1.

Несложно видеть, что случайный гиперграф Н(п,к,р) получается последовательным независимым включением с вероятностью р всех к-подмножеств Уп в качестве ребер (схема Бернулли на к-подмножествах). При к = 2 модель Н(п,к,р) есть ни что иное, как классическая биномиальная модель случайного графа С(п,р), активные исследования которой начались со знаменитых работ П. Эрдеша и А. Реньи [1], [2], [3]. Модель С(п,р) также часто называют моделью Эрдеша-Реньи.

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

1.2 История задачи и новые результаты

Первые работы, посвященные изучению числа независимости случайного графа С(п,р), были написаны в начале 70-х годов прошлого века. Среди таких работ можно выделить работы Д. Матулы [8], Дж. Гримметта и К. МакДиармида [9], П. Эрдеша и Б. Боллобаша [10]. Последними авторами была показана сильная концентрация значений а(С(п,р)) при фиксированном Р £ (0,1).

Теорема 1.1 (Эрдеш, Боллобаш). Пусть р £ (0,1) фиксировано. Тогда для любого е > 0 выполнено

р(к-£ ^ а(С(п,р)) ^ к+е — 1) ^ 1 при п ^ то,

где

е

к+е = [2п — 2п + 22 + 1 + е1,

е

к—£ = |_2^п — 21og61оёбп +21оёб 2 +1 — , а Ь = (1 — р)—1.

Таким образом, для фиксированного р £ (0,1) при п ^ то из теоремы 1.1 вытекает закон больших чисел для числа независимости случайного графа:

а(^(п,р)) Р) 1 (11)

В 1990 году А. Фризом [11] было получено обобщение вышеприведенного результата на случай достаточно быстро убывающих функций р = р(п) = о(1) (при п и то). Им был обоснован следующий результат.

Теорема 1.2 (Фриз). Для любого е > 0 существует такая положительная величина что при условии ¿£ ^ пр = о(п) выполнено

Р

2

а(С(п,р))--(1п(пр) — 1п1п(пр) — 1п2 + 1)

р

< е ) и 1, п и то. р

Теорема 1.2 даёт порядок а(С(п,р)) равный 21пРпр), но необходимо отметить, что точная асимптотика числа независимости (закон больших чисел) имеет место только при растущей функции пр, то есть для пр и то при п и то выполнено

а^'г,р)) А 1. (1.2)

21п(пр)/р

Случай же постоянного пр = с долго оставался открытым. Легко заметить, что число независимости С(п, с/п) для постоянной с > 0 должно иметь линейный порядок по числу вершин, ведь таково уже число изолированных вершин (вершин, из которых не выходит ни одного ребра) в случайном графе. В связи с этим была выдвинута следующая естественная гипотеза (см. например, [12]): для любого с > 0 существует такая константа 7(с) Е (0,1), что при п и то

а(С(п'с/п) -и 7 (с). (1.3)

п

Только в 2013 году М. Бояти, Д. Гамарник и П. Тетали [13] с помощью метода интерполяции, взятого из математической физики, доказали эту гипотезу. Отметим, однако, что в их работе обосновывается именно существование величины 7(с), но явного вида 7(с) как функции от с им получить, к сожалению, не удалось.

Наконец, при пр и 0 ребер в графе становится настолько мало, что при п и то это дает следующее соотношение:

а(С(п,р)) -и 1 (14)

п ' '

Независимые множества в однородных гиперграфах активно изучались еще с 60-х годов, когда была поставлена знаменитая проблема Турана (см., например, [14]). Многие результаты теории графов естественным образом удалось перенести в теорию гиперграфов, но далеко не все. Например, аналог теоремы 1.2 был доказан в работе М. Кривелевича и Б. Судакова [15].

Теорема 1.3 (Кривелевич, Судаков). Пусть к ^ 3 фиксировано, тогда существует такое &0 = &0(к) > 0, что при условии

& = (к — 1)(П — 1)р ^ ¿о

и & = о(пк—1) выполнено

1

к-1

\ П\к^1 (1 + (1п^ а(Н(п, к,р))

__1_

(1.5)

Как и в случае графов теорема 1.3 дает закон больших чисел для числа независимости только при растущем значении & ^ то. При постоянном же & мы имеем просто некоторые оценки вида с1п и с2п для несовпадающих постоянных с1,с2 > 0.

Теорема 1.3 для случая плотного случайного графа (при р ^ п—е) была доказана в более ранних работах [16] и [17].

Основной результат настоящей главы — это закон больших чисел для числа независимости случайного гиперграфа Н(п,к,р) в разреженном случае, когда математическое ожидание числа ребер линейно по отношению к числу вершин. В теореме 1.4, приведенной ниже, мы обобщаем результат (1.3) на случай гиперграфов. Формулировка теоремы звучит так.

Теорема 1.4. Для любых фиксированных к ^ 3 и с > 0 существует такая величина 7(к, с) £ (0,1), что при р = сп/(П) выполнено

а(Н (п,к,р)) р

п

> 7(к, с), п ^ то. (1.6)

1.3 Похожие задачи

Задача о поиске числа независимости случайных графов активно изучается не только в классической модели, но и для специальных классов графов с дополнительными ограничениями на его структуру. Одним из таких классов, например, могут быть дистанционные графы (см. [18], [19]), у которых вершины являются точками пространства, а ребра — отрезками, заданной длины. Одни из первых результатов для чисел независимости таких графов были получены в работе Ж. Надя [20]. Очень подробно изучены дистанционные графы, которые представляют собой п-мерный куб. Например, в работе [21] была найдена асимптотика числа независимости случайного подграфа

п-мерного куба. Наконец, в общем случае оценки для числа независимости случайных дистанционных графов были получены в недавних работах [22]

-[31].

Еще одним активно изучаемым классом графов являются ё-регулярные графы. В таких графах степени всех вершин одинаковы и равны некоторому числу ё. Замечено, что максимальное независимое множество в таких графах имеет линейный по отношению к числу вершин размер. Пусть С(п, ё) граф, выбранный случайно и равномерно из множества всех ё-регулярных графов на п вершинах. При растущем ё в работах [32] и [33] была найдена точная асимптотика для величины . Для фиксированного ё долгое

время существовали лишь верхние и нижние оценки [34]-[37], отличающиеся умножением на некоторую положительную величину. Точную асимптотику удалось найти в недавней работе [38] и только для достаточно больших значений ё.

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

При доказательстве теоремы мы следуем методу интерполяции из работы Бойяти, Гамарника и Тетали [13]. Во-первых, мы воспользуемся утверждением, которое показывает, что для доказательства теоремы достаточно проверить, что имеет предел нормированное математическое ожидание числа независимости.

Утверждение 1.1. Для любой функции р = р(п) Е (0,1) выполнено

а(Н (п,к,р)) — Еа(Н (п,к,р)) р „

——-----—--— —> 0, п и то.

п

Доказательство. Воспользуемся следующей теоремой (см. теорему 1.20 из [4]) об оценке вероятности большого уклонения.

Теорема 1.5 (Янсон). Пусть Z1,... ^т — независимые случайные векторы, Е . Пусть / : х • • • х и К — такая борелевская функция, что существуют постоянные с1,... ,ст, для которых выполнены неравенства

(x1, . . . , хт) /(x1, . . . , xi — 1,yi, хг+1, ... , хт) \ ^ с1,1

при всех х1 Е ,... ,хт Е -,уг Е , % = 1,... ,т. Тогда для случайной величины X = /(^1,..., Zm) и для любого Ь > 0 выполнено

Г 2Ь2 Р(\Х — ех\ ^ Ь) < 2ехЫ

т2 2^=1 Ч

Чтобы применить данную теорему занумеруем все вершины гиперграфа номерами от 1 до n. Пусть для любого i £ {1,...,n} случайный вектор Zi состоит из (i — 1) индикаторов, соответствующих наличию в гиперграфе H(n,k,p) ребер вида (i, j), где 1 ^ j < i. Тогда число независимости можно представить как функцию от такого набора случайных векторов, так как они однозначно описывают гиперграф. Нетрудно заметить, что при изменении набора ребер у одной вершины, число независимости может измениться максимум на единицу, а значит, a(H(n, k,p)) удовлетворяет условию теоремы 1.5 с параметрами ci,..., cn равными единице. Тогда уже при t = n1/2+<, ö > 0, выполнено

p(|a(H(n,k,p)) — ea(H(n,k,p))| ^ n1/2+<) < 2exp {— n2<} — 0.

Откуда незамедлительно вытекает искомая сходимость. □

Тем самым, для установления (1.6) достаточно показать, что существует такая константа 7 = 7(k, c) £ (0,1), что при p = cn/Q)

ea(H (n,k,p)) /7 ч .

—v v ' —^ 7(k, c) при n —у то. (1.7)

n

В свою очередь для доказательства данной сходимости мы покажем супераддитивность последовательности ea(H(n,k,p)) как функции от n. Согласно несложному утверждению супераддитивность гарантирует наличие предела при делении на n. Для полноты изложения материала мы приведем его доказательство (см. также [13]).

Утверждение 1.2. Пусть ß £ (0,1), положительная постоянная C и последовательность положительных чисел {ai}°==1 с условием, что ai ^ i для всех i, удовлетворяют неравенству

an > an, + an2 — C • nß, (1.8)

для любых n,n1,n2 таких, что n1 + n2 = n. Тогда существует предел —n

n

при n — то.

Доказательство. Рассмотрим функцию f (x) = определенную для x ^ 1. Заметим, что неравенство (1.8) будет выполнено и для нецелых n,n1,n2 (возможно для меньшей константы C). Обозначим

г* у f(x)

f = lim sup-.

x—то x

Для £ > 0 найдем такое k £ N, что 1/k < £ ^ 1/(k — 1). Теперь выберем xo = x0(s), что

f(X0) ^ f*— £, kßXß—1 <£. x00

Нетрудно убедиться, что такое х0 действительно существует. Пусть далее х > кх0. Возьмем такое г, что кх0 • 2Г ^ х < кх0 • 2Г+1, тогда последовательно применяя г раз неравенство (1.8) с п1 = п2 = п/2, получим соотношение

г—1

К (х) > 2Г/(х • 2—г) — С • ^ 21 (х/21 )в > 2г/(х • 2—г) — С' • 2(1—в)гхв,

1=0

где С' = С(21—в — 1). Теперь найдем такое %, что (к + %)х0 ^ х • 2—г ^ (к + % + 1)х0. Нетрудно заметить, что % ^ к. Тогда опять, последовательно применяя к+% раз неравенство (1.8) с п1 = х0 и п2 = х^2—г—х0, х^2—г—2х0,..., получим

К(х • 2—г) > (к + %)/(хо) — С • к(х • 2—г)в.

Следовательно,

К(х) > 2г(к + %)/(хо) — С'' • к2(1—в)гхв,

где С" = С + С'/к. Таким образом,

Кх) > 2г(к + (хо) _ С" к2(1—в)гхв—1 > х > (к + % + 1)х0 • 2г >

> 1 — --1- (К* — е) — С'' • к2(1—в)гхв—1 >

1

ч к + % + 1

(т.к. 1/к < е)

> (1 — е) (К* — е) — С'' • к2(1—в)гхв—1. Заметим, что

к2(1—в)г хв—1 ^ к2(1—в)г (к2г хо У-1 = кв хв—1 < е. Следовательно, для всех х > кх0,

К (х)

X

> (1 — е)(К* — е) — С''• е.

Произвольность е и ограниченность С'' окончательно доказывают существование искомого предела. □

Именно для установления свойства супераддитивности для последовательности Еа(С(п,с/п)) Бойяти, Гамарником и Тетали был использован метод интерполяции.

1.4.1 Метод интерполяции

Пусть зафиксировано множество V из п вершин, которое разбито на две непересекающиеся части V и V?, V = п^ г = 1, 2, где п1 + п2 = п. Рассмотрим 0 ^ г ^ [сп] и случайный гиперграф Н(п, к, [сп],г), который состоит из [сп] ребер и получен следующим образом:

• первые его г ребер е1,...,ег ("зеленые ребра") выбираются случайно, независимо и равновероятно среди всех возможных упорядоченных наборов из к вершин V (тем самым, вершины в ребре могут повторяться и сами ребра могут оказаться одинаковыми), т.е. для любого А £ Vк выполняется

р(е? = А) = -1;

пк

• оставшиеся [сп] — г ребер ("красные ребра") /1,..., /[сп]_г выбираются так: сначала с вероятностью п^/п выбирается множество Vi, затем уже ребро выбирается случайно, независимо и равновероятно среди всех возможных упорядоченных наборов из к вершин Vi, т.е. для любого А £ ^¿к выполняется

= А) = п ■ п^к.

Отметим также, что определение независимого множества в Н(п, к, [сп], г) не меняется, несмотря на то, что гиперграф может содержать ребра с повторяющимися вершинами. Множество вершин независимо, если полностью не содержит ни одного ребра гиперграфа.

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

{Н(п,к, [сп],г)}Гг0.

При г = [сп] случайный гиперграф Я(п,к, [сп], [сп]) состоит из [сп] зеленых ребер и "похож" на Н(п,к,сп/(к)). А вот при г = 0 случайный гиперграф Н(п, к, [сп], 0) состоит из [сп] красных ребер и является объединением двух случайных гиперграфов на множествах вершин V и V?, т.е. "похож" на объединение непересекающихся гиперграфов Н(п^к,сп^(), г = 1, 2.

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

Лемма 1.1. Для любого г = 1,..., [сп], выполнено

еа(Н(п, к, [сп], г)) ^ еа(Н(п, к, [сп], г — 1)).

Доказательство. Случайный гиперграф Н(п, к, [сп], г) может быть получен из гиперграфа Н(п,к, [сп],г — 1) удалением одного "зеленого" ребра, и добавлением одного "красного". Рассмотрим случайный гиперграф Н' = (V, Е'), составленный из г — 1 случайного "зеленого" ребра и [сп] —г случайных "красных" ребер. Пусть также е — случайное независимое с Н' "зеленое" ребро, а / — случайное независимое с Н' "красное" ребро. Тогда

Обозначим а(Н') = I и введем О — пересечение всех независимых множеств размера I в Н'. При добавлении любого ребра к Н' его число независимости может измениться не более чем на 1, причем оно

• не меняется, если новое ребро не полностью входит в О (ведь тогда сохраняется хотя бы одно независимое множество Н' размера I, не содержащее всех вершин нового ребра);

• уменьшается на 1, если новое ребро полностью входит в О. Отсюда можно получить, что

Н' и е = Н(п, к, [сп], г), Н' и / = Н(п, к, [сп], г — 1).

е(а(Н' + е)|Н') = I

где О,; = V П О. Осталось заметить, что в силу выпуклости функции х выполнено соотношение

к

из которого следует, что

е(а(Н' + е)|Н') ^ е(а(Н' + /)|Н').

Усредняя по Н', получаем искомое неравенство:

еа(Н(п, к, [сп], г)) = еа(Н' + е)

^ еа(Н' + /) = еа(Н(п, к, [сп], г — 1)).

Лемма доказана.

□

1.4.2 Аппроксимация моделей

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

Отметим также, что число независимости является липшицевой с параметром 1 по ребрам функцией гиперграфа, т.е. если есть два к-однородных гиперграфа Н1 = (V, Е1) и Н2 = (V, Е2), то

\а(Н1) — а(Н2)\ ^ \Е1&Е2\. (1.9)

При помощи аппроксимации моделей мы докажем следующую лемму.

Лемма 1.2. Пусть с > 0,к > 3 — фиксированные числа. Тогда для всех п,п1,п2 с условием п = п1 + п2 выполнено

2

Еа(Н(п, к,р)) > ^ еа(Н(пг, к,р) — О(^п),

г=1

где р = сп/(пк), рм = сщ/{Щ).

Аппроксимацию будем проводить в следующем порядке: сначала покажем, что аналогичное свойство выполнено для гиперграфа Н(п,к, [сп\, [сп\), затем — для равномерной модели случайного гиперграфа Н(п,к,т), и, наконец, — вернемся к биномиальной модели Н(п, к, р).

Утверждение 1.3. Пусть с> 0,к > 3 — фиксированные числа. Тогда для всех п, п1,п2 с условием п = п1 + п2 выполнено

2

еа(Н(п,к, [сп\, [сп\)) > ^^ еа(Н(щ,к, \ сщ\, [сп^])) — 0(у/п).

г=1

Доказательство. Согласно лемме 1.1 имеет место неравенство

еа(Н(п, к, [сп\, [сп\)) > Еа(Н(п,к, [сп\, 0)).

Рассмотрим случайные величины ^ с распределением Б%п([сп\,п.ь/п) для % = 1,2. Далее возьмем два случайных гиперграфа Н'(щ^,^), % = 1,2, полученных следующим образом: вначале мы случайно выбираем количество

ребер после чего случайно и независимо с этим выбираем упорядоченных наборов из к вершин из V». Гиперграф же Н(п», к, [сп»], [сп»]) строится точно также, но имеет фиксированное [сп»] число ребер, а не случайное. Отметим также, что случайный гиперграф Н(п,к, [сп], 0) равен объединению двух непересекающихся случайных гиперграфов Н^п^к,^), г = 1, 2. Из условий липшицевости (1.9) получим,

|ба(Н'(пг, к, £г)) - еа(Н(п»,к, [сп»], [сп»]))| ^ е|£ - [сп»]| ^

(т.к. ~ Вгп( [сп] , п^/п))

^ е|£г - е£»| + 0(1) ^ + 0(1) = О(^) = О(уп).

В итоге,

еа(Н(п, к, [сп], [сп])) ^ еа(Н(п,к, [сп],0)) =

2 2

:а(Н/(п;, к, ^ ^ Еа(Н (п»,к, [сп»|, [сп»!)) -

¿=1 г=1

Утверждение доказано. □

^ еа(Н/(п», к, £) ^ ^ еа(Н(п», к, [сп»], [сп»])) - 0(

Теперь покажем, что модель Н(п, к, [сп], [сп]) близка к равномерной модели гиперграфа Н(п,к, [сп]).

Утверждение 1.4. Пусть с > 0,к ^ 3 — фиксированные числа. Тогда для любого п выполнено

|еа(Н (п, к, [сп], [сп]) - еа(Н (п, к, [сп]))| = О(^п).

Доказательство. Пусть Н/ — случайный к-однородный гиперграф, получающийся из Н(п, к, [сп], [сп]) удалением неполных ребер (т.е. ребер, в которых есть повторяющиеся вершины) и отождествлением мультиребер (т.е. одинаковых ребер). Обозначим число неполных ребер в гипеграфе Н(п, к, [сп], [сп]) через У, а число ребер в гиперграфе Н/ — через X. Легко понять, что в силу равномерности и независимости выбора ребер в гиперграфе Н(п, к, [сп], [сп]) условное распределение Н/ при условии X = т есть просто равномерная модель Н(п, к, т).

Снова в силу липшицевости числа независимости имеем,

|еа(Н(п, к, [сп])) - еа(Н(п, к, [сп], [сп]))| < < еУ + е|Х - [сп]|.

Далее,

(1.10)

С^ . к!

еУ = [сп] • | 1 | = 0(1), (1.11)

\ / /kit \ Iсп г n\ I i nk — kW

EX — W l1 Л nk

'n\ ( ck! _ / 1

+ о ) — cn+от.

\к) \пк — 1 \n2k-2 у ;

Второй момент случайной величины X также легко вычисляется:

eA" -eX + <k)(&- - +{,-*-/ - EX + (Э((3 - О^ + о ()) - Cn2 + ось

Значит, DX — O(n) и, стало быть,

e|x - [cn\i < e|x - ex| + o(i) < Vox + o(i) — o(Vn).

Последнее соотношение вместе с неравенствами (1.10) и (1.11) завершает доказательство. □

Следующее утверждение связывает классические модели: равномерную и биномиальную.

Утверждение 1.5. Пусть c> 0,k ^ 3 — фиксированные числа. Тогда для любого n и p — cn/ (k) выполнено

lEa(H(n,k, Icn\) - Ea(H(n,k,p))l — O(Vn).

Доказательство. Заметим, что биномиальная модель может представлена следующим образом: выбираем случайное число будущих ребер гиперграфа £, где £ ~ Bin((k), p), а затем уже выбираем сами ребра в выбранном количестве, т.е. это равномерная модель только с изначально случайным числом ребер. Отсюда, как и раньше, получаем, что

lEa(H (n, k, |cn\) - Ea(H (n,k,p))l < e|£ - [cn\l <

n\ffn\ Л (nk - k\\ (nk - 2k\\

^ е\£ — \ + 0(1) ^ + 0(1) = ^ (п)р(1 — р) + 0(1) = 0(^п).

Утверждение доказано. □

Согласно утверждению 1.3 выполнено свойство супераддитивности для последовательности еа(н(п,к, [сп\, [сп\)): для любых п,п1,п2 с условием п1 + п2 = п,

2

еа(н(п,к, [сп\, [сп\)) > ^^ еа(н(щ,к, [сщ\, [сщ\)) — 0(у/п).

г=1

В свою очередь, утверждения 1.4 и 1.5 показывают, что при р = сп/(и

р» = сп/( Ю

|еа(Н(п, к, [сп], [сп])) - еа(Н(п,к,р))| = О(^п),

|еа(Н(п»,к, [сп»], [сп»])) - еа(Н(п»,к,р»))| = 0(л/п).

Собирая все вместе, мы и получаем искомое свойство супераддитивности числа независимости:

2

(п,к,р)) ^ ^ еа(Н(п»,

»=1

ea(H(n, k,p)) ^ ^ ea(H(n», k,p»)) - О(УП),

где p = cn/(П), p» = cn»/(ПкО • Лемма 1.2 доказана. 1.4.3 Завершение доказательства

Лемма 1.2 в сочетании с утверждением 1.2 обеспечивает существование предела

Y(k,c) = lim Ea(H(n'fc,p))

n^TO n

при p = cn/(k). Данный предел вместе с утверждением 1.1 обеспечивает справедливость теоремы 1.4.

Глава 2

Закон больших чисел для независимых множеств общего вида

Результаты главы опубликованы в работе [С3].

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

2.1 Основные определения

Пусть ] — некоторое натуральное число. Множество вершин W С V в гиперграфе Н = (V, Е) называется ]-независимым, если каждое ребро гиперграфа имеет не более ] вершин внутри W, т.е. для любого ребра А С Е выполнено |А П W | ^ ].

Естественным образом можно ввести и обобщение для числа независимости. Числом ]-независимости гиперграфа Н называется максимальный размер ]-независимого множества в Н и обозначается через а (Н).

Заметим, что если гиперграф является к-однородным, то имеет смысл рассматривать только 1 ^ ] ^ к - 1, ведь при остальных ] все подмножества вершин будут независимыми. При ] = 1 (ребро имеет не более одной вершины в независимом множестве) 1-независимые множества в однородном гиперграфе принято называть сильными независимыми множествами, а в случае ] = к - 1 (ребро полностью не содержится в независимом множестве) (к - 1)-независимые множества называют слабыми независимыми множествами. Часто при обозначении слабого числа независимости нижний индекс вовсе опускают и обозначают а^-1(Н)=а(Н). Напомним, что именно слабому числу независимости была посвящена первая глава. Также отметим, что при к = 2, когда речь идет об обыкновенных графах, понятия сильных и слабых независимых множеств совпадают.

В этой главе мы продолжим изучать биномиальную модель гиперграфа,

однако, мы будем рассматривать не слишком большие значения вероятности включения ребра р = сп/(, где с ^ у. Оказывается, что в подобных условиях случайный гиперграф Н(п, к, р) имеет достаточно простую структуру. Хорошо известно (см. [39]), что в этом случае с вероятностью, стремящейся к 1,

1. случайный гиперграф Н(п,к,р) не имеет больших компонент, максимальный размер компоненты связности равен 0(1п п) при с < и

0(п2/3+) при с = щ-1) для любого фиксированного 6 > 0;

2. число циклов в Н(п, к,р) не превосходит 0(1п п) при с < щ-у и 0(1п2 п)

при с = щ-у;

3. гипердеревья занимают п(1 - о(1)) вершин в гиперграфе Н(п, к,р).

Напомним, что гипердерево — это связный гиперграф без циклов. Циклом же длины в в гиперграфе Н = (V, Е) называется такая чередующаяся последовательность (г>1, А1, -и2 ..., , А5, г>5+1) различных вершин г>1,..., ^ и различных ребер А1,..., Ав, что V £ А»-1 П А», г = 1,..., в и г>в+1 = г^. Несложно понять, что к-однородное гипердерево из в ребер состоит из в(к - 1) + 1 вершины и имеет ту же структуру, что и обычное дерево-граф. Если выделить одну из вершин в качестве начальной (корня), то остальные вершины естественно упорядочиваются по реберному расстоянию от корня и для каждой вершины найдется единственная другая вершина — ее родитель, имеющая с ней общее ребро, но находящаяся на меньшем расстоянии от корня.

2.2 История задачи и новые результаты

Произвольные 3-независимые множества активно изучаются в последние годы. Так, например, в работе [40] исследуются экстремальные задачи о числе 3-независимых множеств в однородных простых гиперграфах. В уже упомянутой работе [15] М. Кривелевич и Б. Судаков доказали следующую теорему.

Список литературы диссертационного исследования кандидат наук Семенов Александр Сергеевич, 2019 год

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

[1] P. Erdos, A. Renyi, "On random graphs I", Publ. Math Debrecen, 6, 1959, 290-297.

[2] P. Erdos, A. Renyi, "On the evolution of random graphs", Magyar Tud. Akad. Mat. Kutato Int. Kozl, 5, 1960, 17-61.

[3] P. Erdos, A. Renyi, "On the evolution of random graphs", Bull. Inst. Int. Statist. Tokyo, 38, 1961, 343 - 347.

[4] B. Bollobas, Random Graphs, Cambridge University Press, Cambridge, 2002.

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

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

[7] A. Frieze, M. Karonski, Introduction to random graphs, Cambridge University Press, Cambridge, 2015.

[8] D.W. Matula, "On the complete subgraphs of a random graph", Combinatory Mathematics and its applications, Chapel Hill, 1970, 356-369.

[9] G. Grimmett, C. McDiarmid, "On colouring random graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 77 (1975), 313-325.

[10] B. Bollobas, P. Erdos, "Cliques in random graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 80 (1976), 419-427.

[11] A. Frieze, "On the independence number of random graphs", Discrete Mathematics, 81 (1990), 171-175.

[12] N. Wormald, "Models of random regular graphs", Surveys in Combinatorics, London Mathematical Society Lecture Notes Series, 267, Cambridge University Press, Cambridge, 1999, 239-298.

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

[14] A. F. Sidorenko, "What we know and what we do not know about Turan numbers", Graphs and Combinatorics, 11 (1995), 179-199.

[15] M. Krivelevich, B Sudakov, "The chromatic numbers of random hyper-graphs", Random Structures and Algorithms, 12 (1998), 381-403.

[16] J. Schmidt-Pruzan, E. Shamir, E. Upfal, "Random hypergraph coloring algorithms and the weak chromatic number", Journal Graph Theory, 8, 1985, 347-362.

[17] E. Shamir, "Chromatic number of random hypergraphs and associated graphs", Adv. Comput. Res, 5 (1989), 127-142.

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

[19] A.M. Raigorodskii, "Coloring Distance Graphs and Graphs of Diameters", Thirty Essays on Geometric, Graph Theory, J. Pach ed., 2013, 429-460.

[20] Z. Nagy, "A certain constructive estimate of the Ramsey number", Matem-atikai Lapok, 23 (1972), 301-302, 26.

[21] K. Weber, "On the independence number of random subgraphs of the n-cube", Annals of Discrete Math., 33 (1987), 333 - 337.

[22] Н.М. Деревянко, С.Г. Киселев, "Числа независимости случайных подграфов некоторых дистанционных графов", Проблемы передачи информации, 4 (2017), 307-318.

[23] B. Bolobas, B.P. Narayanan, A.M. Raigorodskii, "On the stability of the Erdos-Ko-Rado theorem", J. Comb. Th. Ser. A, 2015.

[24] P. Devlin, J. Kahn, "On the "stability" in the Erdos-Ko-Rado theorem", SIAM J. Discrete Math., 30:2 (2016), 1283-1289.

[25] Л.И. Боголюбский, А.С. Гусев, М.М. Пядёркин, А.М. Райгородский, "Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов", Доклады РАН, 457:4 (2014), 383-387.

[26] Л.И. Боголюбский, А.С. Гусев, М.М. Пядёркин, А.М. Райгородский, "Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов", Матем. сб., 206:10 (2015), 3-36.

[27] М.М. Пядёркин, "Об устойчивости в теореме Эрдеша-Ко-Радо", Доклады РАН, 462:2 (2015), 144-147.

[28] М.М. Пядёркин, "Числа независимости случайных подграфов некоторого дистанционного графа", Матем. заметки., 99:2 (2016), 288-297.

[29] М.М. Пядёркин, "Числа независимости случайных подграфов дистанционных графов", Матем. заметки., 99:4 (2016), 564-573.

[30] М.М. Пядёркин, А.М. Райгородский, "О случайных подграфах кнезеров-ского графа и его обобщений", Доклады РАН, 470:4 (2016), 384-386.

[31] M. Pyaderkin, "On the stability of some Erdos-Ko-Rado type results", Discret. Math., 340:4 (2017), 822-831.

[32] A.M. Frieze, T. Luczak, "On the independence and chromatic numbers of random regular graphs", Journal of Combinatorial Theory, Series B, 54:1 (1992), 123-132.

[33] M. Krivelevich, B. Sudakov, V. H. Vu, N. C. Wormald, "Random regular graphs of high degree", Random Struct. Alg., 18 (2001), 346-363.

[34] B. Bollobas, "The independence ratio of regular graphs", Proc. Amer. Math. Soc, 83:2 (1981), 433-436.

[35] A.M. Frieze, S. Suen, "On the independence number of random cubic graphs", Random Structures and Algorithms, 5 (1994), 649-664.

[36] B. D. McKay, "Independent sets in regular graphs of high girth", Proceedings of the Singapore conference on combinatorial mathematics and computing (Singapore, 1986), 23 (1987), 179-185.

[37] N. C. Wormald, "Differential equations for random processes and random graphs", Ann. Appl. Probab, 5:4 (1995), 1217-1235.

[38] J. Ding, A. Sly, N. Sun, Maximum independent sets on random regular graphs, arXiv: 1310.4787.

[39] J. Schmidt-Pruzan, E. Shamir, "Component structures in the evolution of random hypergraphs", Combinatorica, 5:1 (1985), 81-94.

[40] А. Е. Балобанов, Д. А. Шабанов, "О числе независимых множеств в простых гиперграфах", Матем. заметки, 103:1 (2018), 38-48.

[41] J. Schmidt, "Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number", Discrete Mathematics, 66:3 (1987), 259-277.

[42] R. Karp, M. Sipser, "Maximum matchings in sparse random graphs", 22nd Annual Symposium on Foundation of Computer Science, 1981, 364-375.

[43] B. Bollobas, "The chromatic number of random graphs", Combinatorica, 8 (1988), 49-55.

[44] T. Luczak, "The chromatic number of random graphs", Combinatorica, 11 (1991), 45-54.

[45] T. Luczak, "A note on the sharp concentration of the chromatic number of random graphs", Combinatorica, 11:3 (1991), 295-297.

[46] D. Achlioptas, A. Naor, "The two possible values of the chromatic number of a random graph", Ann. of Math., 162:3 (2005), 1335-1351.

[47] A. Coja-Oghlan, "Upper-bounding the k-colorability threshold by counting covers", Electronic Journal of Combinatorics, 20:3 (2013), Research paper 32.

[48] A. Coja-Oghlan, D. Vilenchik, "The Chromatic Number of Random Graphs for Most Average Degrees", International Mathematics Research Notices, 2016:19 (2015), 5801-5859.

[49] N. Alon, J. Spencer, "A note on coloring random k-sets", Unpublished manuscript.

[50] D. Achlioptas, J.H. Kim, M. Krivelevich, P. Tetali, "Two-colorings random hypergraphs", Random Structures and Algorithms, 20, 2002, 249-259.

[51] D. Achlioptas, C. Moore, "Random k-SAT: two moments suffice to cross a sharp threshold", SIAM Journal on Computing, 36, 2005, 740-762.

[52] A. Coja-Oghlan, L. Zdeborova, "The condensation transition in random hypergraph 2-coloring", Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, 241-250.

[53] A. Coja-Oghlan, K. Panagiotou, "Catching the k-NAESAT threshold", Proc. 44th STOC, 2012, 899-908.

[54] M. Dyer, A. Frieze, C. Greenhill, "On the chromatic number of a random hypergraph", J. Combin. Theory Ser. B, 113, 2015, 68-122.

[55] Д.А. Шабанов, "О концентрации хроматического числа случайного гиперграфа", Доклады Академии Наук, 475, 2017, 24-28.

[56] P. Ayre, A. Coja-Oghlan, C. Greenhill, "Hypergraph coloring up to condensation", Random Structures and Algorithms, 2018.

[57] H. Hatami, M. Molloy, "Sharp thresholds for constraint satisfaction problems and homomorphisms", Random Structures and Algorithms, 33, 2008, 310-332.

Список работ автора по теме диссертации

[С1] А.С. Семенов, Д.А. Шабанов, "О числах независимости случайных разреженных гиперграфов", Дискретная математика, 28, 2016, 126-144.

[С2] А.С. Семенов, "Число независимости случайного разреженного k-однородного гиперграфа", IX международная конференция «Вероятностные методы в комбинаторике»», Петрозаводск (30 мая — 3 июня, 2016 г.), расширенные тезисы, Ин-т прикладных мат. исследований Карел. науч. центра Рос. акад. наук; [науч. ред. В. В. Мазалов ; отв. ред. Е. Н. Спектор], Петрозаводск : [Издательство ПетрГУ], 2016, 90-91.

[С3] А.С. Семенов, Д.А. Шабанов, "Независимые множества общего вида в случайных сильно разреженных гиперграфах", Проблемы передачи информации, 54, 2018, 63-77.

[С4] A. S. Semenov, "On the j-chromatic number of random hypergraphs.", Proceedings of the "Vilnius conference on combinatorics and number theory", 2017, 22.

[С5] А.С. Семенов, "Двухцветные раскраски случайного гиперграфа", Теория вероятностей и ее применения, 64, 2019, 75-97.