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

• Денисов Илья Олегович
• кандидат наук
• 2023

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

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

1.2 Смежные задачи

1.3 Новые результаты

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

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

1.6 Случайный гиперграф в динамике

2 Концентрация хроматических чисел случайных гиперграфов

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

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

2.3 Новые результаты

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

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

2.5.1 О точной пороговой вероятности

2.5.2 Переход к равномерной модели

2.5.3 Использование второго момента

2.5.4 Вычисление моментов случайной величины Хп

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

2.6.1 Центральные строки

2.6.2 Общие оценки

2.6.3 Хорошие строки

2.6.4 Плохие строки

2.6.5 Разбор случаев

2.6.6 Только плохие строки

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

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

3.2 Новый результат

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

Заключение

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

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

Диссертационная работа посвящена исследованию в области теории случайных гиперграфов. Теория случайных графов и гиперграфов начала формироваться на рубеже 50-60-х годов прошлого века в классических работах П. Эрдеша и А. Репьи [1] и [2], хотя в комбинаторных задачах случайные графы применялись и ранее. Эрдешем и Реньп были получены первые результаты о пороговых вероятностях в случайных графах, а также об эволюции случайного графа. На этом фундаменте в дальнейшем выросло целое направление в вероятностной комбинаторике, называемое сегодня теорией случайных графов и гиперграфов. Основные ее результаты можно найти в монографиях [3—5].

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

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

Вторая модель, рассматриваемая в диссертации, — это модель Н(п,к,т), п > к ^ 2 т е М, в которой у нас есть множество из п вершин, и мы независимо и каждый раз равновероятно выбираем т ребер из множества всех возможных ^-подмножеств множества вершин. Отметим, что несмотря на наличие асимптотической эквивалентности между моделями Н(п, к,р)м Н(п, к, т) (см. [4]) топкие

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

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

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

Асимптотическое поведение чисел независимости для случайных графов в модели G(n,p) активно изучается с 80-х годах прошлого века. Первые результаты были получены в работах Д. Ми гулы [6], Дж. Гримметта и К. МакДиар-мида [7], П. Эрдеша и Б. Боллобаша [8] для случая постоянного р £ (0,1). В частности, была доказана концентрация значений a(G(n,p)) в двух соседних числах. Для случайных гиперграфов ситуация обстоит несколько сложнее: числа j-независимости изучались в работах Дж. Шмидт, Э. Шамира с соавторами |9 11], и в связи с исследованием j-хроматических чисел были получены некоторые оценки чисел j-независимости Н(п,к,р). Наиболее полное исследование по числам j-независимости было проведено М. Кривелевичем и Б. Судаковым [12], ими был доказан "закон больших чисел" для числа j-независимости в неразреженном случае, т.е. при >> п (более подробно результаты описываются в соответствующей главе диссертации). В работах A.C. Семенова и Д.А. Шабанова [13, 14] изучалось асимптотическое поведение aj(Н(п,к,р)) в так называемом разреженном случае, когда р = сД^-j) и параметр с > 0 зависит только от к и j. Основным результатом первой главы диссертации является получение аналога результата П. Эрдеша и Б. Боллобаша [8] о концентрации значений числа j-независимости в двух соседних числах при правильном выборе функции р = р(п).

Вторая глава посвящена изучению предельного поведения j-хромати-чес-ких чпсел случайного гиперграфа в модели Н(п, к,р) в разреженном случае (р = сп/{&))• Ро,скра,скои f множества вершин гиперграфа в г цветов является отображение f : V ^ {1,..., г}. Для раскраски f вводятся множества Vi = f ~1(г) i = 1,..., г, образующие разбиение V. Они называются цветовыми классами рас-

краски /. Раскраска гиперграфа Н называется правильной, если в ней каждый цветовой класс является независимым множеством в Н (т.е. не содержит полных рёбер внутри себя). Наименьшее число цветов, при котором можно построить правильную раскраску гиперграфа Н, называется хроматическим числом гиперграфа и обозначается х(Н)• Для гиперграфа также можно ввести целую серию ^'-правильных раскрасок, параметризуемую натуральной величиной А именно, для ] > 0 раскраска множества вершин гиперграфа Н = (V, Е) в г цветов называется ^правильной, если в ней каждый цветовой класс является ^'-независимым множеством. Минимальное число цветов г, необходимое для ^'-правильного раскрашивания вершин гиперграфа Н, называется числом Н и обозначается через \з (Н)■

Исследования асимптотического поведения хроматического числа случайного графа С(п,р) начались еще в 70-е года прошлого века. В 1988 году для случая постоянного р в работе Б. Боллобаша [15] был доказан "закон больших чисел" для хроматического числа случайного графа. Позднее, в 1991 году в работе [16] был доказан аналогичный результат для случая не слишком быстро убывающей р = р(п). Более подробно история результатов для случайного графа описывается во второй главе данной работы. Что касается хроматических чисел случайного гиперграфа Н(п,к,р)7 то здесь наиболее общий результат был получен в работе М. Кривелевича и Б. Судакова [12]. Он даёт "закон больших чисел" для ]-хроматического числа случайного гиперграфа, а также результат о концентрации ^'-хроматического числа в ограниченном числе значений для разреженного случая. Дальнейшие продвижения в вопросе концентрации ^'-хроматического числа были сделаны в классическом случае ^ = к — 1, т.е. для обычного хроматического числа. Здесь следует отметить работы М. Дайера, А. Фриза и К. Гринхилл [17], П. Эйра, А. Койя-Оглана, К. Гринхилл [18] и Д. Шабанова [19]. В общем случае, когда ] < к — 1, концентрация ^'-хроматического числа изучалась, в основном, для разреженного случая. В работе [20] исследовалась пороговая вероятность ^'-правильной г-раскрашиваемости случайного гиперграфа Н(п,в ситуации, когда к ^ г. В этой работе не был получен результат о концентрации ^'-хроматического числа, но были даны очень точные оценки пороговых вероятностей для свойства ]-правильной г-раскрашиваемости при больших к.

Целью второй главы диссертации было получение оценок пороговых вероятностей для свойства ^'-правильной г-раскрашиваемости при обратном соотношении между параметрами: когда параметр однородности^ фиксирован, а параметр г может быть сколь угодно большим. Единственный подобный результат был ранее получен также А. Семеновым и Д. Шабановым в [21] для случая ^ = к — 2. Во второй главе диссертации получено полное обобщение результата из [21] для общей ситуации, когда к/2 ^ ] < к — 2. В качестве следствия обоснован результат о концентрации значений ^'-хроматического числа.

Наконец, в третьей главе диссертации изучается вопрос о концентрации хроматических чисел в неразреженном случае, когда среднее число ребер растет быстрее чем число вершин п. Для модели Н(п,к,р) подобный результат известен только в классическом случае т.е. для хроматического чтжа,Хк_1(Н(п, к,р)). А именно, в работе [22] было доказано, что при не слишком медленно убывающей функции р(п) хроматическое число случайного гиперграфа сконцентрировано в двух соседних значениях, а также были найдены эти значения в определенных случаях. В диссертации доказан новый результат о концентрации всех ^'-хроматических чисел случайного гиперграфа Н(п, к, т) при не слишком быстро растущей функции т = т(п).

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

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

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

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

3. изучение феномена концентрации ^'-хроматических чисел случайного ^-однородного гиперграфа Н(п, к,т) в неразреженном случае.

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

Основные результаты работы являются новыми и состоят в следующем:

1. Доказана концентрация значений чисел ^'-независимости случайного гиперграфа Н(п, к,р) в ограниченном множестве значений при определенных ограничениях на функцию р = р(п).

2. Получены новые оценки пороговой вероятности наличия свойства^'-правильной г-раскра-

шиваемости в случайном гиперграфе Н(п,к,р) в разреженном случае при к/2 < з <к _

3. Доказана предельная концентрация значений ^'-хроматических чисел случайного гиперграфа Н(п, к,р) в одном или двух соседних значениях в разреженном случае при к/2 ^ ] < к —

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

Теоретическая и практическая ценность полученных результатов

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

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

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

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

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

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

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

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

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

Публикации

Результаты диссертации опубликованы в работах [D1^D3]. Всего по теме опубликованы три работы, из них две в соавторстве. Все работы опубликованы в журналах из списка RSCI. Работы [D1],[D2] опубликованы в изданиях, индексируемых также Scopus и Web of Science. Все результаты диссертации, включая результаты, опубликованные в совместных работах, были получены автором диссертации самостоятельно.

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

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

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

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

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

Глава 1

Концентрация чисел независимости случайного гиперграфа

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

Р(Н (п,к,р) = Н') = р1Е'1(1 _ р)(^_1Е\

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

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

Обзор литературы мы начнем с известных результатов относительно числа независимости случайного графа С(п,р), которое активно изучается с 70-х годов прошлого века. Первые результаты были получены в работах Д. Матулы [6], Дж. Гримметта и К. МакДиармида [7], П. Эрдеша и Б. Боллобаша [8] для случая посто-

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

Теорема 1. (П. Эрдеш, Б. Боллобаш, [8]) Пусть р € (0,1) фиксировано, Ь = (1 — р)—1. Для положительного е > 0 введем

к+£ = к+£ (п) = [2 п — 2 п + 2 2 + 1+ £1,

к—£ = к—£(п) = |_2 п — 2 п + 2 2 + 1 — е\.

Тогда, для любого фиксированного е > 0 выполнено

Р(к—£ ^ а(С(п,р)) ^ к+£ — 1) —> 1 при п ^

Заметим, что при малых £ € (0,1/22) величины к+£ж к—£ отличаются не более чем на 2, тем самым, значение а(С(п,р)) действительно хорошо сконцентрировано.

В случае убывающей функции р = р(п) ^ 0 известны следующие результаты. Если р = о(1), но пр = ^(1), то, как было показано А. Фризом [23], выполняется следующее соотношение: для любого положительного £ > 0

Р

( а(С(п,р)) — ~(1п(пр) — 1п1п(пр) — 1п2 + 1) ^ - ] V Р Р у

£ .

> 1 при п ^

р;

Оно же остается верным и при пр ^ ^(е) для некоторого положительного ^(е). Наконец, при фиксированном произведении пр = с > 0 М. Бойяти, Д. Гамарник и П. Тетали [24] доказали, что существует такая 7(с) € (0,1), что

а(С(п,с/п)) р

--у 7 (с) пр и п ^

п

В недавно вышедшей статье Т. Бохмана [25] доказана концентрация числа независимости случайного графа С(п,р) в двух соседних значениях для п—2/3+£ < р ^ 1,е > 0. Вопрос о порядке "разброса значений" числа независимости в области ш(1/п) < р ^ п—2/3 остается открытым.

Числа независимости случайного гиперграфа Н(п, к,р) изучались с 80-х годов прошлого века, но в основном в связи с исследованиями по хроматическим числам. В работах Дж. Шмидт, Э. Шамира с соавторами [9—11] были получены некоторые оценки чисел ^'-независимости Н(п, к,р) для получения асимптотик ]-хроматических чисел случайных гиперграфов. Наиболее полное исследование в

этом направлении было проведено М. Кривелевичем и Б. Судаковым [12], которые обосновали следующий результат (см. следствие 1 в [12]). Для 1 ^ ] ^ к — 1 введем обозначение ^) = к—|)Р- Тогда существует такая величина (10 =

(к,]) > 0, что ее ли $) > и одновреме нно = о(тР), то с вероятностью, стремящейся к 1, число ^'-независимости случайного гиперграфа Н(п,к,р) удовлетворяет следующим неравенствам:

( d^ ( 1 \\—1/j Ч(J + 1)Ъ*i) v + 1 ^ aj(н(щ к,р)) ^

( d,® \-1/J ^ Ч (j + 1)ln d(j))

(1.1)

Из приведенных оценок следует, что при растущем параметре d^\ т.е. при р =

< ^ к\ ( dü) \-1/j ш(п1 число независимости имеет асимптотикуп ( ln dIij) ) , однако и промежуток значений весьма велик. Вопрос о концентрации значений в приведенных работах не поднимался. В работах A.C. Семенова и Д.А. Шабанова [13, 14] изучалось асимптотическое поведение aj(Н(п,к,р)) в так называемом разреженном случае, когда р = и параметр с > 0 зависит только от к и j. Ими был

найден предел сходимости по вероятности aj(Н(п, к,р))/п при с ^ 1/(к — 1), а также доказано существование предела при j = к — 1 и произвольпом с> 0.

1.2 Смежные задачи

Задача о поиске числа независимости случайных графов изучается не только в классической модели С(п,р), но и для ряда других специальных классов графов с некоторыми дополнительными ограничениями на структуру. Одним из примеров являются дистанционные графы (см [26], [27]),у которых вершины являются точками пространства, а ребра — парами точек, находящихся на заданном расстоянии друг от друга. В общем случае, оценки для числа независимости случайных дистанционных графов были получены в работах [28—37].

Следует также отметить класс простых гиперграфов — в таких гиперграфах каждые два ребра имеют не более одной общей вершины (как в графе). В работе [38] исследовались экстремальные задачи о числе ^независимых множеств в таких гиперграфах.

1.3 Новые результаты

Основным результатом данной работы является полный аналог теоремы 1, который показывает концентрацию значений числа ^'-независимости случайного

гиперграфа Н(п,к,р) в двух соседних числах при правильном выборе функции р = р(п). Мы сформулируем две отдельных теоремы — для случая ] = к — 1, обычного числа независимости, и для ] < к — 1. Начнем с классического случая 3 = к — 1.

Теорема 2. Пусть к ^ 2 и р € (0,1) фиксированы. Обозначим к = /(х) =

(х — 1)... (х — к + 1), и для любого фиксиро ванного е > 0 введем, величины

Ь+£ = Ь-г =

¡4 к\ ^ п —

к!

$ М п —

к — 1 к! к- 1

п + к\ 1ogh

п +

(к\)1/(к—1) е

(к \ )1/(к—1)

+ £

— £

Тогда,

Р(Ь-£ ^ ак—1 (Н(п, к,р) ^ Ь+£ — 1) —> 1 при п ^

Следующая теорема показывает концентрацию числа ^'-независимости при 3 < к — 1.

Теорема 3. Пусть к ^ 3 1 ^ 3 < ^ — 1 фиксированы, а функция р = р(п) такова, что величина (1 = (щут (к^Р положительна и удовлетворяет, следующим двум условиям:

А = о(1пп), А ^ (1пп)1 -2+5

для некоторой, фиксированной величины 5 € (0,1^. Введем также функцию /(х) = (х — 1)... (х — ]) для х > ]. Для е > 0 положим

Ь+£ =

Ь-Р =

/

/

, 1п п — 11п1п п + 11п + 1 + £

—1 / _I_I_

, 1п п — 11п1п п + 11п + 1 — £

1

А

Тогда, для любого фиксированного е > 0 вы,полнено

Р (Ь-£ ^ а^(Н(п, к,р) ^ Ь+е — 1) —> 1 при п ^ Прокомментируем результаты теорем 2 и 3.

1. Функция /(х) строго монотонна и непрерывна для х > ] + 1, а потому обратная к ней корректно определена. Более того, обратная функция/—1(у) имеет ограниченную производную при всех достаточно больших у и, следовательно, равномерно непрерывна.

е

2. Для случая обычного числа независимости, ] = к — 1 (теорема 2), концентрация имеет место при фиксированном р € (0,1), в точности как в теореме 1. Более того, в силу свойств функции /—1 при малых £ величины Ь—£ и Ь+£ отличаются не более чем на 2.

3. При ] < к — 1 (теорема 3) концентрация происходит уже в нетривиальном режиме, когда р стремится к нулю и имеет порядок п^+1—к+°(1). Величина А = <Э(рпк-1—) должна и не слишком быстро расти, и не слишком быстро убывать к нулю. В случае, когда ё, ограничено снизу некоторой константой, мы получаем тот же результат, что и в теореме 2: число ^'-независимости сконцентрировано в двух соседних значениях. При ё, ^ 0 мы получаем концентрацию в 0(1/(1) последовательных значениях, что также уточняет результат (1.1) Кривелевича и Судакова.

4. Отметим, что верхнее ограничение ё, = о(1п п) в некотором смысле оптимально. При больших р число ^'-независимости также имеет концентрацию в ограниченном числе значений, но ситуация тривиальна. Совсем легко проверить, что при р = ш(т?+1—к 1п п) число ^'-независимости просто равно ] с вероятностью, стремящейся к 1. Действительно, вероятность найти набор из ] + 1 вершины, которые не входят хотя бы в одно общее ребро Н(п, к,р), не превосходит

(1 — р)(к—--э) —у 0 пр ип —> Тем самым, нельзя найти ^'-независимое множество размера даже ] + 1 и

Р(а,(Н(п,к,р))= з) -^ 1.

В следующем разделе мы приведем доказательство теоремы 3.

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

Доказательство теоремы использует метод второго момента и следует схеме доказательства теоремы 1.

Докажем правое неравенство. Обозначим через Хп(Ь) числ о ^'-независимых множеств размера & в случайном гиперграфе Н(п, к,р). Тогда

Хп(Ь) = ^^ !{.] — ^'-независимо в Н(п,к,р)}, Л СК:|Л \=Ъ

где 1{А} обозначает индикатор события А. Напомним, что подмножество является ^'-независимым в гиперграфе Н тогда и только тогда, когда оно не содержит

ребер, пересекающихся с ним по хотя бы по ] + 1 вершинам. Для выбранного 3 мощности Ь в полном ¿^-однородном гиперграфе на ив ершинах количество ребер, удовлетворяющих этому свойству, равно 0 {—-г) •> поэтому математическое

ожидание Хп(Ь) равно

= ^—р^,» (Ж?).

Поймем асимптотику данного выражения в условиях теоремы при подстановке Ь = Ь±£, т.е. при Ь = 0((^)1/'•*).

1. Обозначим т := О и пРовеРим5 чт0 тр2 = °(1) Действительно,

£ оо=-( £

1=з+1 4 7 4 7 Кк—з—1/ /

- (¿555-)

= +1

т.к. Ьк(I2 = о(п) (при соблюдении условий теоремы на^).

Заметим также, что сумма слагаемых для т за исключением слагаемого с

( ■ Л \1+2/А

I = ] + 1 дает величину порядка О I nк_^_2( ) ):

|2 ос*—:)—2 ^ —2( ^ гад) •

поэтому

тр = (* — ^ = 0 + 0 (к — --J,P + 0(1) =

( Ь \ {к- 1-п) / ь \ / , ^ (Ь

~2_

+ о(1) = Ь • /(Ь)й + о(1).

В итоге, получаем, что

(1 — р)т = ехр(т 1п(1 — р)) = ехр (—тр + О(тр2))

){<+ ОФ

С/ + 1)м + 0(1)= . , 1 + о - и + 1)\<л+

= ехр(—Ь• /(Ь)й + о(1)).

2. Из того, что Ь±£ = о(/п) следует (П) ~ Пл~ Кроме того, по формуле Стирлинга получаем, что Ы ~ /2пЬТаким образом,

^ = ехр(Ь(1пп — 1пЬ + 1 + о(1))). (1.3)

3. Наконец, при Ь = Ь±£ справедливо представление Ь = (1 + о(1)) (1пп/<Л)1/^ поэтому

1пЬ = 11п1пп — 11пй + о(1). (1.4)

С учетом соотношений (1.2), (1.3) и (1.4) имеем

ЕХп(Ь) = (1 — ©И = ехр(Ь(1пп — 1пЬ + 1 — /(Ь)й + о{1))) =

= ехр ^ Ь (\пп — 11п1пп + 11пс1 + 1 — /(Ь)<Л + °(1))) . Теперь заметим, что

И

_ , 1пп — 1 1п1пп + 1 1пс1+ 1 + £

Пь+£) 3 3

поэтому

БХп(Ь+£) ^ ехр ^Ь+£ (\пп — 11п1пп + 1 \п(1 + 1 —

(1пп — 1 1п1пп + 1 1пб?+1+£\

(—г—г-у1+о(1)

= ехр(Ь+£(—£ + о(1))) —^ 0.

Аналогично,

1пп — 1 1п1пп + 1 1пй + 1 — £

ЯЬ—е) ^ /

-1 / з з

И

поэтому

БХп(Ь—£) ^ ехр ^Ь—£ (\пп — 11п1пп + 11пс1 + 1 —

[\пП — 1 1п1пп + 1 1пс1+ 1 — £ \ (-г-12-) ^^

= ехр (Ъ—£(£ + о(1))) —>

Первая часть утверждения теоремы следует из метода первого момента:

Р (а3(Н(п,к,р)) ^ Ь+£) ^ ЕХ-(Ь+£) 0,

с вероятностью, стремящейся к 1, ^'-независимых множеств размера Ь+£ в случайном гиперграфе не найдется.

Для доказательства второй части утверждения вычислим асимптотику второго момента случайной величины Хп(Ь) при Ь = Ь-£. Заметим, что

Х2п(Ь) = ^^ —2 — ^'-независимы в Н(п, к,р)},

2 п

Ш,Ш=Ъ

поэтому

ЕХ-(Ь) = ^^ Р ( -]_, —2 — ^'-независимы в Н(п,к,р)).

Ш,Ш=Ъ

Количествопар подмножеств ( —, —2) пересекающихся ровно по I вершинам, равно (-) (I) (П~е)- Изучаемое событие эквивалентно отсутствию в случайном гиперграфе ребер, пересекающихся с —1 или —2 более чем по ] вершинам. При |П—2\ = I мощность Б множества ребер, одновременно пересекающихся с и —2 более чем по ] вершинам, может быть представлена следующим образом:

- е С—%)(;•——;!.)■

(х,у,г)€к 4 У ЧУ/ 4 У У

где А = {(х,у, х) € М : х + у ^ ] + 1, у + г ^ ] + 1,х + у + г величины

х,у,х,к — х — у — х равны мощностям пересечений ребер с множествами \ —2, П —2, —2 \—1,Уп \ (—1 и —2)., соответственно. Тогда

^=£ С)(!)(Г16)(1 ■е;=>+1 (Ж1:Я—3. (1-6)

Упростим асимптотически выражения для слагаемых в (1.6). Для этого сумму (1.5) в выражении для Б разобьем на две части:

• в первой будет слагаемое с х +у+х=]+1 (это условие в силу свойств множества А эквивалентно равенствам х = г = 0,у = ] + 1) и выражение равно Б = ,)(-—£?),

• во второй остаются слагаемые с х + у + г > ^ + 1 и выражение Б2 = Б — Б1.

В силу условия теоремы р = 0(п^+1 кё), а величина Б имеет порядок пк ^ \ поэтому Бр2 ^ 0 и, кроме того,

^=^ е д С—% :—,)=^ • =о(Л/П).

х+у+х^3+2

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

(1 — р)~51 = е1п(1 —р) = е(р+°(р2))51 = ер(Л Ж-^+^И. (1-7)

Теперь заметим, что квадрат БХп( Ь) может быть представлен в виде:

^„.т2 = ((£ акт)2 =

=± с )0(г:) • ^

Таким образом, дисперсия случайной величины Хп(Ь) равна

ъхп(ь)=£ )(;)(;—;) • (1—,)2 ^ с)(Й)—5

6 'П\(Ъ\(П — ^ (1— п)2 ^ (Ь)(П-Ь) 5 —

Л \и\Ь — 1

1=0

£ в ) • ^ Еи юю)=

1=о \ / \ / \ /

=§ С )С)(г?) • ^ ^ ^«^г1).

Из (1.6) и (1.7) получаем следующее выражение для отношения дисперсии к квадрату первого момента:

ОХп (Ь) {{1_рГ 5_

((1—5 — 1))

(^ЛЬ))2 {¿=0 („)

3 (Ь\(п-Ъ\ Ъ (Ь\(п-Ъ\

1=0 (ь) 1=3+1 ^

Обозначим первую сумму в равенстве (1.8) заЕ1? а вторую за Е2. Покажем, что каждая из них стремится к нулю.

1) С Е1 разобраться очень просто:

з (ь\(п_ ь\ з (ь\(п_ ь\

\и\ъ-и /„ошп) х^\е)\ъ-е)

^ = Е ^^(е0{ЛЧп) _ 1) = ^^ • °((1Ь/п) = °((1Ь/п) ^ 0

1=0 \ЬУ 1=0 Ш

с ростом п.

2) Оценивать Е2 заметно сложнее.

Ь /6\ (п_Ь\ ь

£2 = ^ ^(ер(А)(ХГ*)+0^п) _ ^ ^ ^ р,

1=3+1 1=3+1

ь\ (п-Ъ\

ер(з+1)( к-з-1 )+1. Найдем в данной сумме максимальное слагаемое.

где Г£ = (Ъ)((}еЪ) ер(з+О^-А^Н1

(ъ)

Для этого рассмотрим отношение Р^ к Р^+1.

(Ъ\(п—Ь\ р(.+1)(пГ2Ъ+е) +1

(1 + 1)(п _2ь +1 + ^ 1)(п-4ь-+/)_(5+1)(п--Ъ+Г)) (Ь — I)2 '

Поймем, что из себя представляет выражение в экспоненте. Вспоминая, чтор = I ^ Ь и Ь = °((^ )1/у), получаем

(к-3-1)

л(з+1У- ^ £ ^^ ъЬ = п(

(( I \(п _ 2 Ь + Л [£ + 1\[п _ 2Ь + I + 1 Чи + Л к_.]_ 1) \.] + 1Л к — э — 1 ,

= Ф' + 1)\[[ , М (1 + °(Ь/п)) — (I + 1) (1 + °(Ь/п))) =

3 + 1) \3 + 1,

=—ъ+ъО+° (—) а-»

Отсюда при I = ] + 1 имеем:

Р+1 = Ц + 2)(п _ 2Ь + ] + 2)р-«+1)Щ+1)+о(^) р+2 (Ь _]_ 1)2 '

что равно О (п1+о(1^) в условиях нашей теоремы, ведь (1 = о(1пп), т.е. оно значительно больше 1 при всех достаточно больших п.

Далее, обозначим через 10 = ш\п{£ : Яц ^ Я1+1}. Из представления (1.9) следует, что 10 — (1пп/(<Л(] + 1)))1/^ и имеет порядок О(Ь). Тогда при 10 < I < л/Ь + 10 отношение Я1+1 будет также меньше 1. Действительно,

Я (Ь — £0)2(п — 2Ъ + £ + 1)(1 + 1) _ л^Щ10)— г1и+1У.(^++°()

Р+1 Р0+1 (Ь — £)2(п — 2Ь + £0 + 1)(£0 + 1) ¿(¿-¡-1 \\(1\ I . „ / 1

10 л^п)—щ+ъО и + о — < 1

Р1п+1 \ \у/Ь,

в силу того, что Я£0 ^ Я£0+1, а велнчпна + 1)!(— й(] + 1)!(1) ^ — (!(.] + < 0 отрицательна и имеет порядок db^_1 = ш(Ь~1/2). Отметим, что соотношение б,V—1 = ш(Ь~1/2) сразу следует из условия теоремы и соотношения Ь = в((1пп/б)1/^):

¿V—1/2 = П (1пп)1—^ П ((1пп)+ж. Наконец, при £ > л/Ь + £0 имеем

Рг = (Ь — £0)2(п — 2Ь + £ + 1)(£ + 1) ^+1)!(ту¿(^(1)+0(1) Я+1 Я£о+1 (Ь — £)2(п — 2Ъ + £0 + 1)(£0 + 1) ' ' '

= 0{ • Ь2 • е^1)1 ОУ^+1)[йЛ ^ О (Ь2 • е^1)1 ОУ^+1)!(1п+^

Я

¿0+1

О ^ 1)2 • е-¿0+1^еП-1/Ъ(1+0(1)^ = 0 ^е-с1^+1^£П-1/Ь(1+о(1))+21пЬ^ =

0 ^ е~П(Зг Ьз-1/2)+21пЬ^ = е-П((1пп)2 )+°(1п1пп)

Полученное выражение стремится к нулю с ростом п. Таким образом, последовательность Яц (£ = ] + 1,... ,Ь) сначала убывает (до £ = £0), а затем возрастает. Значит, < Fj+1 + Яь для всех £ = ] + 1,... ,Ь и

£2 < ¿Я, < Ь^+1 +РЪ) = Ь +№ ^ А-&П+1 + ±-)е<(+О^?1)+^ .

Первое слагаемое в полученной сумме имеет порядок

/ Ь2(1+1)

е(з+1)!^^ = 0 ^е-(з+1)1пп+о(1пп)^ = 0(1).

V Ш+1

Второе же слагаемое очень похоже па (ЕХп(Ь))—1. Действительно,

'П\ (Ъ\(п-Ъ\ /п\ ЛЬ )( п-Ь

ЕХп(Ь) = (1—р)^+1 (^ - 1)(^П--1)

Мы уже знаем, что при Ь = Ь-£ ЕХп(Ь) ^ еъ(£+о(1) ^ +ж при п ^ ж. В итоге, мы доказали, что при Ь = Ь-£ выполнено

ОХп{Ь) ^ ^ ^ + -> 0 при п ^ Ж.

(ЕХп{Ь))2

Согласно методу второго момента это означает, что

Р(Х"< ^ ) = 0) < (йет - 0

Значит, с вероятностью, стремящейся к 1, Хп(Ь-£) > 0 и а^(Н(п,к,р)) ^ Ь-£. Теорема 3 доказана.

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

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

Снова обозначим через Хп(Ь) число независимых множеств размера Ь в случайном гиперграфе Н(п,к,р). Напомним, что подмножество вершин 3 является независимым в гиперграфе Н тогда и только тогда, когда оно не содержит полных ребер. Таких ребер ровно штук. Поэтому математическое ожидание Хп(Ь) равно

ЕХп(Ь]=(") (1 — рр.

По формуле Стирлинга, получаем:

ЕХп( »= (П)(1 -р)Ю - ^И» — ^^(г) =

= нъ (1о^п-1°ёк е—4т1-+°(1))_

Далее, при Ь = Ь±£ выполнено Ь — (к! \oghn)1/(k-1\ поэтому логарифм Ь имеет вид:

\oghb = (к!^п) + о(1) = \oghn + + о(1).

Тогда при Ь = Ь±£ получаем

( )

^ п - ^ Ь + ^ е -

!

= п - ^ п + к! + 6 -

= +

Л Ь+е) ^ f ^I—1 п _ п + к\ ^ 1) + £

к! е

= к\ ^ п _ ^ п + к\ 1о§ь + £.

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

п

(Ь+ ) = Кк—1о^ 1о&ип+ к-г 1оёк к^^ие-Щ^+о(1))

^ КЬ + ( _ к + *(1)).

Теперь первая часть утверждения следует из метода первого момента:

Р (а(Н(п,к,р)) > Ь+Е) ^ ЕХп(Ь+Е) 0.

Для доказательства второй части утверждения оценим первые два момента случайной величины Хп(Ь-£). Из полученных представлений имеем следующую оценку первого момента:

ЕХп( М ^ еь-(к+о(1)) ^ +ж. =

общей формуле (1.6), которая при ] = к — 1 может быть существенно упрощена:

С другой стороны,

™2=|Ъ (")©("—?

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

о о (г:

I—к

и

шк=£ (к(к> _ 1) < е ^^=£ (1.Ю)

(ЕЛп(0)) е=к и; е=к и; е=к

Точно также, как это было проделано в доказательстве теоремы 3, устанавливается, что последовательность Г (£ = к,... ,Ь) сначала убывает (до некоторого а затем возрастает. Следовательно, Г < + Гъ для I = к,... ,Ь. Отсюда,

¿Г < (ь- к№ + Гъ) = (ь - + .

Первое слагаемое в сумме имеет порядок роста

^ = 0 (((^п)1/(к-1))2к ) = /1) . пк \ пк ) \Ь /

Второе слагаемое есть в точности ё^Ь)- При Ь = Ъ-£ выполнено

ЕХп(Ь)

Ькь( е+о(1)) —у 0 при п ^ ж.

В итоге, мы получили, что при Ь = Ъ-£ выполнено (^"(ЬЬ)2 ^ 0 ПРИ п ^ ж. Согласно методу второго момента это означает, что

Следовательно, Р(а(Н(п,к,р) ^ Ь-£)) ^ 1 при п ^ ж.

1.6 Случайный гиперграф в динамике

ных гиперграфов Н(п, к, р) фактически как случайный процесс, считая, чтоН(п+ 1 , , ) Н( п, , )

ем случайных ребер через нее. Получающийся в пределе бесконечный случайный гиперграф обозначим через Н(М,&, р).

Зафиксируем 0 < 5 < Для каждого фиксированного г введем случайную величину Хп(г) — число независимых множеств размера г в момент времени п, т.е. в Н(п,к,р). Тогда, как мы помним,

ЕХп(г)=(^) (1 - рр.

Положим также

пг = тах{п : ЕХп(г) ^ г-(1+^}, п'г = шт{п : ЕХп(г) ^ г1+6}.

Несложно найти асимптотические соотношения для пг и п'г непосредственно из их

гАЛ . гАЛ пг — - К г , пг — - К г .

Кроме того, в силу того, что К > 1, для всех достаточно больших г будет выполнено соотношение пг <п'г < пг+1.

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

Лемма 1. С вероятностью 1 последовательность гиперграфов Н(М,к,р) удо-

а(Н(п,к,р)) =г для всех п £ [п'г,пг+11.

Доказательство. В силу определения п'г параметр г есть 0((1oghn'r)). Из доказательства теоремы 2 следует, что

р(«( Н(пГ,к,р)) < г) < Ех^г)Т ^ Е ^

г 1=к

где величины определены в (1.10) (с переобозначениями п = п'г) Ь = г). В рамках доказательства теоремы 2 было установлено, что величины по I сначала убывают, а потом — возрастают, поэтому

Р(а(Н(пГ, к,р)) < г) + Яг + (г — к — 1)(Як+1 + Я—) ^

{г2к\ 1 (п(г2к+2\ гпГК ( к 1) ^ °{кк) + Ёхплг) +Г[°{^кТ1) + ЕХп/ (г)

Далее, заметим, что величина п'г растет очень быстро (сверхэкспоненциально) по

™2к ™2&+3

!_ + г__^ г_(1+5)_

П!к /у* ^

Далее, к(г- 1) растет по г заметно быстрее, чем п'г7 поэтому для всех достаточно

гп'ГК_(Гк 1) < 1. Кроме того, ЕХп' (г) ^ г1+5 , следовательно,

Р(а(Н(п'г, к,р)) < г) = 0 (г1+6) .

С другой стороны,

Р(а(Н(пг+1,к,р)) ^г + 1) ^ ЕХпг+1 (г) ^ г-(1+3).

Гиперграф Н(п, к, р) вложен в Н(п +1, к, р), поэтому для любого г получаем неравенство

Р(3п е К,пг+1] : а(Н(п,к,р) = г) = О (г-(1+6)) .

Ряд г-(1+^ сходится. Согласно лемме Бореля-Кантелли получаем, что с вероятностью 1 среди подобных событий будет выполнено лишь конечное число, что и доказывает утверждение леммы. □

Глава 2

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

Данная глава посвящена раскраскам случайных гиперграфов. Результаты этой главы опубликованы в работе [Г)2].

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

Рассмотрим ^-однородный гиперграф Н = (V, Е). Раскраской множества вершин / гиперграфа в г цветов является отображение / : V ^ {1,..., г}. Для раскраски / вводятся множества V = I = 1,... ,г, образующие разбиение

V. Они называются цветовыми классами раскраски /. В теории графов известно понятие правильной раскраски графа - в такой раскраске любые две смежные вершины имеют разные цвета. Это определение неоднозначно переносится на

параметризуемую натуральной величиной А именно, для ] > 0 раскраска множества вершин гиперграфа Н = (V, Е) в г цветов называется ]-правильной, если

Например, при ] = 1 это означает, что все вершины ребра должны иметь раз-

1 ^ ] ^ к - 1, иначе любая раскраска будет ^'-правильной.

Н Н

ся через Xj (Н). Отметим, что для графов (2-однородных гиперграфов) параметр

матического числа гиперграфа, х(Н), введенному Эрдешем и Хайналом, соответствует ситуация ] = к - 1.

В этой главе исследуется ^'-хроматическое число случайного ^-однородного гиперграфа в биномиальной модели Н(п, к,р)7 где п > к ^ 2, р £ (0,1). В рамках этой главы мы предполагаем, что к > 2 и 1 ^ j ^ к — 1 фиксированы, п стремится к бесконечности и р = р(п) £ (0,1) является функцией от п.

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

Исследования асимптотического поведения хроматического числа случайного графа С(п, р) = Н (п, 2, р) начались еще в 70-е года прошлого века. Здесь стоит отметить работы Дж. Гримметта, К. Макдиармида [7], Б. Боллобаша [15], Т. Лу-чака [16, 39], И. Алона и М. Кривелевича [40]. Из работ [39, 40] в частности, следовало, что при достаточно быстро стремящейся к нулю функциир(п) (например, р(п) ^ п_1/2_£ для некоторого фиксированного £ > 0 х(^(п,Р)) с вероятностью, стремящейся к 1 с ростом п, принадлежит множеству из двух соседних значений {К, К + 1} для некоторой неизвестной функции К = К(п,р). В дальнейшем поиску данной функции были посвящены работы Д. Аклиоптаса, А. Наора [41], А. Койя-Оглана, К. Панайоту, А. Штегер [42], С. Каргальцева, Д. Шабанова и Т.

К

разреженном случае, когда среднее число ребер линейно по числу вершин, т.е. когда р(п) = сп/ (п^ для с > 0, не зависящего от п. А именно, если с > 1 задано и гс = шт{г £ N : с < г1пг}, то при р = сп/^

Р (х(С(п, р)) £ {гс, гс + 1}) —> 1 при п ^ +ж.

Тем не менее, оказалось, что в разреженном случае для большинства значений

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

цветов при г ^ 3, ее наилучшие текущие оценки были получены в работах [44, 45].

Хроматические числа случайного гиперграфа Н(п,к, р) стали активно изучаться с 1980-х. В работах Дж. Шмидт, Э. Шамира и Э. Упфола [11, 46, 47] было найдено асимптотическое поведение Хз(Н(п, к,р)) при определенных условиях па величину р = р(п). В дальнейшем наиболее общий результат был получен в работе М. Кривелевича и Б. Судакова [12]. Для его формулировки введем величину й = р(п—равную математическому ожиданию степени вершины в Н(п,к,р), и положим ^ = 1л)с1. Если рпк_1 ^ ж и ртк_1— ^ 0, то для ^'-хроматического числа случайного гиперграфа выполнена следующая сходимость по вероятности:

Хз(Н(n, k,р)) • 1)1па ) Ь 1 при п ^ ж.

Авторами [12] также было доказано, что в разреженном случае, когда снова сред-

кого числа в ограниченном числе значений. А именно, если параметр dj фиксирован, но достаточно велик, то с вероятностью, стремящейся к 1 при п — то, выполнены следующие неравенства

()1Й < X-(НылР)) < () )1й. (2.1)

ла были сделаны в классическом случае ] = к - 1, т.е. для обычного хроматического числа. Нам снова будет удобно ввести параметр с, отвечающий пропорции среднего числа ребер по отношению к числу вершин, т.е. пусть р = сп/(1)-

п

(2.1) ограничено, но можно гораздо более точно указать его значения. Обозначим гс = шт{г е N : с < гк-11пг}. Тогда, конечно, с е [(гс - 1)к-11п(гс - 1), гк-11п гс),

равно ^ши гс + 1. А именно, в работах М. Дайера, А. Фриза и К. Гринхилл [17], П. Эйра, А. Койя-Оглана, К. Гринхилл [18] и Д. Шабанова [19] было доказано,

ито

• если с > г]-11п гс - 2 1п гс, то

Р (хк-1(Н(п, к,р)) = гс + 1) —> 1 при п — то;

• если с < г^к-11пгс - 11п гс - ф(к, г), где ф(к, г) — некоторая ограниченная функция, которую можно выбрать равной ф(к, г) = + Ок,г(1) и которую можно уменьшить до ф(к, г) = 1п2 + Ок,г(1) при г > г0(к)7 то

Р (хк-1(Н(п, к,р)) = гс) —> 1 при п —У ж. Внутри же небольшого отрезка [г]к-11пгс - 2 1пгс - г^(к, г), г'к-11пгс - 2 1пгс] из-

с

или гс +1. Концентрация Хк-1(Н(п, к,р)) в неразреженном случае изучалась в работе [22], где было доказано, что при не слишком медленно убывающей функции ( п)

двух соседних значениях, а также были найдены эти два значения в определенных случаях.

В общем случае, когда ] < к - 1, концентрация ^'-хроматического числа изучалась, помимо уже упомянутого результата (2.1), в основном, в разреженном случае (неразреженный случай рассмотрен в работе автора [БЗ] и обсуждается в сле-

г-раскрашиваемости случайного гиперграфа Н(п,в ситуации, когда к ^ г. Для будущего сравнения результатов приведем точную формулировку теоремы из 201.

Теорема 4. (А. Семенов, Д. Шабанов, [20]) Пусть Н(п,к, р) — случайный к-однородный гиперграф на п вершинах, гдер = сп/ и с = (к,], г) > 0 не зависит от п. Для любого г > 2 существуют такие положительные числа С, = С, (г), Си = Си(г) и ко = ко(г), что при к > ко и 1 < к - ] < к1/4 выполнено следующее: 1) если

1п 1п

^Т^—ТТИГ,-— - —+ Си + •г-, (2.2)

гк 11пг 1пг /к

ЙХМ^-^- "2"+ и Л^1

то с вероятностью, стремящейся к 1 прип — то7 Xj (Н (п,к,р)) > г. 2) если

с < --^ -с, • &(2.3)

ЕкЗ-1 (к) (г -1) * 2 ' '

то с вероятностью, стремящейся к 1 прип — то7 Xj (Н (п,к,р)) ^ г.

Отметим несколько моментов относительно этой теоремы. Во-первых, параметр ] должен быть примерно равен ^ ~ но, все-таки, ] должно быть меньше к - 1. Во-вторых, зазор между оценками (2.2) и (2.3) стремится к пулю с ростом к. В третьих, параметр г, отвечающий за ограничение панхроматическое число, должен быть заметно меньше к. Тем самым, данная теорема не позволяет сделать выводы о концентрации хроматического числа, но дает очень точные оценки

Целью настоящей главы было получение схожих результатов, но для обратного случая, когда параметр однородности к фиксирован, а параметр г может быть сколь угодно большим. Единственный подобный результат был ранее получен также А. Семеновым и Д. Шабановым в [21] для случая ] = к - 2. Авторами [21] было показано, что если р = сп/^, с > 0 не зависит от п, к ^ 9 и г > г0(к), то при

1пг = Гк-1 1п Г 1п Г (, 2-к) /9 Л\

с> - = кг- к+ 1 - ~Т + и(кг X

выполнено Р(хк-2(Н(п, к,р)) > г) — 1 при п — то, а при

к-1 1п 1п 1

с < -------—-г-+ 0(к2г-к/31пг), (2.5)

кг-к + 1 2 к(г - 1) + 1

выполнено Р(хк-2(Н(п,к,р)) ^ г) — 1 при п — то. Тем самым, при фиксированном к и растущем г, получается зазор порядка 1/к + ог(1). В данной главе предлагаются аналоги результатов (2.4)-(2.5) для общей ситуации, когда&/2 ^ ] < к-2.

2.3 Новые результаты

Основные результаты этой главы дополняют результаты (2.2)—(2.5) и дают

у случайного гиперграфа Н(п, к, р) в ранее не рассмотренных областях изменений параметров. Первая теорема дополняет (2.2) и (2.4).

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

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

[1] P. Erdos, A. Renyi, "On random graphs I", Publicationes Mathematicae Debrecen 6 (1959), 290^297.

[2] P. Erdos, A. Renyi, "On the evolution of random graphs", Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5:1-2 (1960), 17— 61.

[3] B. Bollobas, Random graphs, Cambridge: Cambridge University Press, 2001.

[4] S. Jansen, T. Luczak, A. Rucinski, Random graphs, New York: Wiley-Interscience, 2000.

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

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

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

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

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

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

[11] E. Shamir, "Chromatic number of random hypergraphs and associated graphs", Adv. Com/put. Res. 5 (1989), 127^142.

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

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

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

[15] В. Bollobas, "The chromatic number of random graphs", Combinatorica 8 (1988), 49 56.

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

[17] M. Dyer, A. Frieze, C. Greenhill, "On the chromatic number of a random hypergraph", Journal of Combinatorial Theory, Series В 113 (2015), 68—122.

[18] P. Ayre, A. Coja-Oghlan, C. Greenhill, "Hypergraph coloring up to condensation", Random Structures and Algorithms 54 (2019), 615—652.

[19] D.A. Shabanov, "Estimating the r-colorability threshold for a random hypergraph", Discrete Applied Mathematics 282 (2020), 168^183.

[20] A.C. Семенов, Д.А. Шабанов, "Оценки пороговых вероятностей для свойств раскрасок случайных гиперграфов", Проблемы передачи информации 58 (2022), 72—101.

[21] A. Semenov, D. Shabanov, "On the weak chromatic number of random hypergraphs", Discrete Applied Mathematics 276 (2020), 134 154.

[22] Ю.А. Демидович, Д.А. Шабанов, "О двух предельных значениях хроматического числа случайного гиперграфа", Теория вероятностей и ее применения 67 (2022), 223 246.

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

[24] 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.

[25] Tom Bohman, Jakob Hofstad, "Two-Point Concentration of the Independence Number of the Random Graph", arXw:2208.00117 (2022).

[26] P. Brass, W. Moser, J. Pach, "Research problems in discrete geometry", Springer (2005).

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

[28] H.M. Деревянко, С.Г. Киселев, "Числа независимости случайных подграфов некоторых дистанционных графов", Проблемы передачи информации 206:10 (2017), 307—318.

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

[30] B. Bollobas, B.P. Narayanan, A.M. Raigorodskii, "On the stability of the Erd"os-Ko-Rado theorem", J. Comb. Th. Ser. A (2015).

[31] P. Devlin, J. Kahni, ""On the "stability" in the Erd"os-Ko-Rado theorem", SIAM J. Discrete Math. 30:2 (2016), 1283^1289.

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

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

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

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

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

[37] М. Pyaderkin,A.M. Raigorodskii, "О случайных подграфах кнезеровского графа и его обобщений", Доклады РАН 470:4 (2016), 384^386.

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

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

[40] N. Alon, M. Krivelevich, "The concentration of the chromatic number of random graphs", Combinatorica 17:3 (1997), 303^313.

[41] D. Achlioptas, A. Naor, "The two possible values of the chromatic number of a random graph", Annals of Ma,them,a,tics 162:3 (2005), 1335—1351.

[42] A. Coja-Oghlan, K. Panagiotou, A. Steger, "On the chromatic number of random graphs", Journal of Combinatorial Theory Series В 98 (2008), 980^993.

[43] S.A. Kargaltsev, D.A. Shabanov, T.M. Shaikheeva, "Two values of the chromatic number of a sparse random graph", Acta Mathematica Universitatis Comenianae 88:3 (2019), 849 854.

[44] A. Coja-Oghlan, D. Vilenchik, "The chromatic number of random graphs for most average degrees", International Mathematics Research Notices 2016:19 (2015), 5801—5859.

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

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

[47] J. P. Schmidt, "Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number", Discrete Mathematics 66 (1987), 258^277.

[48] Т.Г. Матвеева, А.Э. Хузиева, Д.А. Шабанов, "О сильном хроматическом числе случайных гиперграфов", Доклады Российской академии наук. Математика, информатика, процессы управления 502 (2022), 37 41.

[49] Н. Hatami, М. Molloy, "Sharp thresholds for constraint satisfaction problems and homomorphisms", Random Structures and Algorithms 33 (2008), 310^332.

[50] E. Shamir , J. Spencer, "Sharp concentration of the chromatic number on random graphs G(n,p)", Combinatorica 7 (1987), 124 129.

[51] A.E. Balobanov, D.A. Shabanov, "On the strong chromatic number of a random 3-uniform hypergraph", Discrete Mathematics 344:3, 112231 (2021).

[52] A.C. Семенов, "Двухцветные раскраски случайного гиперграфа", Теория вероятностей и ее применения 64 (2019), 75^97.

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

[Б1] И.О. Денисов, Д.А. Шабанов, "О концентрации значений чисел независимости случайных гиперграфов", Дискретная математика 33 (2021), 32 40.

чисел случайных гиперграфов", Доклады российской академии наук, Математика, информатика, процессы управления 509 (2023), 28^35.

[БЗ] И.О. Денисов, "О предельной концентрации значений хроматических чисел случайных гиперграфов", Труды, МФТИ 15:2 (2023), 60^68.