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

• Пядеркин Михаил Михайлович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Пядеркин Михаил Михайлович

1.1 Граф G(n, 3,1)

1.2 Случайные графы в модели Эрдеша-Реньи

1.3 Формулировки результатов

1.4 Числа независимости

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

1.4.2 Нижняя оценка

1.4.3 Оптимальная верхняя оценка

1.5 Хроматическое число

1.5.1 Блоки и раскраски блоков

1.5.2 Раскраска троек, пересекающих множества I и J

1.5.3 Разделяй и властвуй

2 Число независимости и хроматическое число случайного подграфа G(n,r,s)

2.1 Введение и формулировки результатов

2.2 Числа независимости

2.2.1 Верхняя оценка с помощью стандартного метода

2.2.2 Граф G(n, 2,1)

2.2.3 Кнезеровский граф G(n,r, 0)

2.2.4 Общая теорема о числе независимости

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

2.3 Хроматическое число случайного графа G\/2(n,r,s)

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

3 Устойчивость независимых множеств

3.1 Введение и формулировки результатов

3.2 Устойчивость в графе G\/2(n,r, < s)

3.3 Устойчивость независимых множеств G(n,r, 1)

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

3.3.2 Предварительные определения для теорем 3.1.8 и

3.3.3 Устойчивость в графе С(и,г, 1), г >

3.3.4 Устойчивость в графе С(и,г, 1), г =

3.3.5 Доказательство вспомогательных лемм

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

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

Заключение

Введение

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

Рассмотрение дистанционных графов мотивировано знаменитой задачей комбинаторной геометрии — задачей Нельсона-Эрдеша-Хадвигера о хроматическом числе пространства Rn: минимальном числе цветов, в которые можно раскрасить n-мерное евклидово пространство так, чтобы не было одноцветных точек, отстоящих друг от друга на расстояние 1 (см. [1], [2], [3], [4]). С точки зрения теории графов, рассматривается задача о хроматическом числе бесконечного графа, вершинами которого являются все точки пространства Rn, а ребро проводится между точками на расстоянии 1. Теорема Эрдеша-де Брейна утверждает, что бесконечный граф можно раскрасить в k цветов тогда и только тогда, когда в k цветов можно раскрасить каждый его конечный подграф (см. [5]). Тем самым, достаточно изучить хроматические числа конечных дистанционных графов — вершины дистанционного графа представляют собой конечное множество точек пространства Rn, а ребро проводится в том случае, если точки находятся на некотором фиксированном расстоянии друг от друга.

Одно из первых продвижений в задаче Нельсона-Эрдеша-Хадвигера было наблюдение Лармана и Роджерса (см. [6]). В своей работе они рассматривали дистанционный граф G(n, r, s), вершины которого суть вершины булева куба {0,1}n, которые содержат ровно r единиц, а ребро проводится в том случае, если скалярное произведение соответствующих вершин равно s. Ларман и Роджерс заметили, что хроматическое число пространства Rn, которое мы будем обозначать x(Rn), уж никак не меньше хроматического числа графа G(n, 3,1), что давало рекордную на тот момент оценку x(Rn) > c• n2. Впоследствии именно с помощью дистанционных графов Франкл и Уилсон установили, что x(Rn) > (1.207... + o(1))n — таким образом, они показали, что хроматическое число пространства растет экспоненциально с ростом n (см. [7]). Для этого им понадобились графы G(n,r,s) с r ~ 2~2~2 n и s ~ 2 .В 1991 году Дж. Кан и Г. Калаи использовали результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том, что всякое ограниченное неодноточечное множество в Rn может быть разбито на n + 1 часть меньшего диаметра (см. [1], [8], [9]). Неудивительно, что с исследованием дистанционных графов связаны одни из самых широко изучаемых разделов

комбинаторной геометрии (см. [1], [2], [10]).

Впервые же дистанционные графы были упомянуты в работе Надя (см. [11]), где граф С(п, 3,1) был использован для построения графа с маленьким размером максимальной клики и маленьким размером максимального независимого множества — классической задачи теории Рамсея. Числом Рамсея г(п) называется минимальное натуральное число такое, что в любом графе из г(п) вершин найдется либо клика размера п, либо независимое множество размера п. Надь показал, что в графе С(п, 3,1) порядка п3 вершин, а размер максимальной клики и максимального независимого множества не превосходят п. Таким образом, была получена на тот момент наилучшая конструктивная оценка г(п) > с • п3. Позже Франкл и Уилсон в своей работе [7] привели сверхполиномиальную оценку, также полученную с помощью дистанционных графов (см. также [12]).

Следует также упомянуть, что дистанционные графы связаны с исследованием равновесных кодов с запрещенными расстояниями (см. [13], [14], [15]), а клики в графе С(п,п/2,п/4) при п, делящемся на 4, фактически являются строками матрицы Адамара.

Изучение же случайных графов началось после того, как П. Эрдеш установил, что «вероятностный метод» (см. [16], [17], [18]) помогает решать многие задачи экстремальной теории графов. С использованием этого метода Эрдеш доказал, что для любых натуральных чисел д > 3 и к > 3 существует граф с хроматическим числом к и обхватом д, где обхватом графа называется длина наименьшего цикла. Другим классическим примером использования вероятностного метода является построение нижних оценок для чисел Рамсея. Наблюдение, что детерминированные утверждения могут быть доказаны с помощью теории вероятностей, позволило доказать или опровергнуть и многие другие замечательные утверждения из комбинаторики, теории чисел и теории информации.

Случайный граф в модели Эрдеша-Реньи — это случайный элемент со значениями во множестве всех неориентированных графов на п вершинах Уп = {1,... , п} без петель и кратных ребер, имеющий биномиальное распределение, то есть

Р(Ср(п) = (К,£)) = Р|Е|(1 - р)сП-|Е|.

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

Случайным графам посвящено множество работ (см. [16], [19]). Хорошо изучены классические для графов свойства, такие как, например, связность ([20], П. Эрдеш, А. Реньи, Б. Боллобаш и др.) или гамильтоновость ([21], Дж. Комлош, Дж. Мун, Е. Райт и др.). Изучены также многие экстремальные характеристики случайного графа, в том числе длина максимального пути ([22], М. Айтаи, Е. Семереди и др.), распределение диаметра ([23], Ф. Чанг, О. Риордан и др.)

или размер максимальной клики ([24], Т. Лучак, Б. Боллобаш и др.). Случайные бинарные деревья находят свое применение, в частности, для построения эффективных структур данных (см. [25]).

Одно из естественных обобщений модели Эрдеша-Реньи устроено следующим образом. Пусть дана некоторая последовательность графов Hn = (Vn, En), в которой "Vn" ^ го при n ^ го (здесь n не обязано быть числом вершин). Определим случайный граф G (Hn ,p) как случайный элемент со значениями во множестве всех остовных подграфов G = (Vn,E) графа Hn и с биномиальным распределением, т.е.

P [G(Hn,p) = (Vn,E)] = p|E"(1 - p)|E«|-|EI.

Таким образом, в случайный подграф включается каждое ребро исходного графа с вероятностью p, независимо от остальных ребер. Данная модель является обобщением классической модели Эрдеша-Реньи, в том смысле, что Gp(n) = G(Kn,p), где Kn — полный граф на n вершинах. Данная модель хорошо изучена для многих классов графов. К примеру, подробно изучен случай Hn = Qn, где Qn — это n-мерный куб, т.е. граф, вершины которого суть все (0,1)-векторы, а ребра — это пары вершин, различающихся ровно в одной координате (образующих ребро куба). В частности, размер максимального независимого подмножества случайного подграфа куба a(G(Qn,p)) исследовался в работе [26], где доказано, что если p — любая функция от n, с которой pn ^ го при n ^ го, то с асимптотической вероятностью 1 выполнено a(G(Qn,p)) ~ 2n-1. В работе мы будем рассматривать случайные подграфы дистанционного графа G(n,r,s), уже упомянутого выше. Для удобства мы будем обозначать случайный подграф этого графа как Gp(n,r, s) = G (G(n,r, s),p).

Другим естественным обобщением модели Эрдеша-Реньи является случайный регулярный граф. А именно, если r € {1, 2,...,n} и rn четно, то пусть Qr (n) обозначает множество всех r-регулярных графов на множестве вершин Vn. Тогда случайным регулярным графом называется случайный элемент с равномерным распределением на множестве (n). Для данной модели получено множество результатов, в том числе для свойств связности и двусвязности, а также различные оценки, к примеру, на диаметр случайного регулярного графа. Однако, данная модель менее изучена, чем Gp (n), так как уже оценка количества регулярных графов является трудной задачей. Изучением случайных регулярных графов занимались, в частности, Н. Вормальд, А. Фриз (см. [27]).

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

Цель работы.

Цель работы состоит в изучении структуры независимых множеств в дистанционных графах G(n,r,s) и их случайных подграфах, а также установления асимптотического поведения числа независимости и хроматического числа данных графов; исследование устойчивости и асимптотической устойчивости независимых

множеств и, где возможно, нахождение пороговой вероятности для устойчивости.

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

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

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

Для доказательства основных результатов диссертации мы использовали разнообразную технику. Мы воспользовались классическими результатами из теории случайных графов, такими как теорема о хроматическом числе и числе независимости случайного графа, см. [18]. Также были использованы классические комбинаторные результаты о задаче Эрдеша-Ко-Радо и структуре ¿-пересекающихся совокупностей, см. [28], [29]. В работе мы воспользовались различными неравенствами для биномиальных коэффициентов, а также методом моментов. Для доказательства оценки хроматического числа мы воспользовались жадным алгоритмом раскраски, для которого были доказаны оценки вероятности.

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

В диссертации получены новые результаты, которые состоят в следующем:

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

2. Найден порядок роста числа независимости и хроматического числа для случайного графа С1/2(п, г, й).

3. Доказана асимптотическая устойчивость независимого множества в случайном графе С1/2(п, г, й) при г > 2й + 1.

4. Найдена пороговая вероятность для асимптотической устойчивости независимого множества в случайном графе Ср(п, г, й) при г > 2й + 1.

5. Описано устройство больших независимых множеств графа С(п,г, 1) при г > 4.

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

7. Доказана устойчивость независимого множества в случайном графе ^1/2(п,г, < й).

Степень достоверности и апробация результатов

Все результаты строго доказаны.

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

— Научный семинар «Вероятностные методы в комбинаторике» на кафедре математической статистики механико-математического факультета МГУ, под руководством профессора А.М. Райгородского (2014-2015 гг., неоднократно).

— Научный семинар «Дискретная геометрия» в МГУ, под руководством д.ф.-м.н. Мощевитина Н.Г. (2015г.).

Результаты диссертации докладывались на следующих конференциях:

— «Random Structures and Algorithms 2013» (Познань, Польша, 2013)

— «Ломоносов-2015» (Москва, 2015)

— «Random Structures and Algorithms 2015» (Питтсбург, США, 2015)

— «Workshop on extremal graph theory» (Москва, 2016)

Публикации

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

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

Автор признателен профессору Андрею Михайловичу Райгородскому за постановку задачи и неоценимую помощь в работе.

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

В первой главе рассматривается граф С(п, 3,1), для которого Надь нашел число независимости, а совсем недавно в совместной работе Балога, Косточки и Рай-городского было найдено хроматическое число. В главе будут рассмотрены результаты, касающиеся случайных подграфов графа С(п, 3,1), для которых нам будет необходимо выделить особый класс множеств, среди которых с высокой вероятностью найдется независимое множество большого размера («блоки»). Будет показано, что всякое достаточное большое независимое множество должно иметь вид, похожий на блок, а также то, что из блоков можно получить раскраску случайного подграфа. Таким образом, использование блоков приведет к отысканию асимптотики числа независимости и хроматического числа.

Во второй главе рассматривается более общий граф С(п,г, й), число независимости которого было изучено Франклом и Фюреди. В главе будут рассмотрены важные частные случаи, такие, как кнезеровский граф С(п, г, 0) и граф С(п, 2,1), и будет показано, что случай г > 2й + 1 принципиально отличается от случая г < 2й + 1 с точки зрения исследуемых экстремальных характеристик. В обоих случаях будет найден порядок роста числа независимости: для этого будет использован метод «плотной конструкции», которая с высокой вероятностью не может являться независимым множеством. Будет показано, что любое слишком большое независимое множество обязано содержать плотную конструкцию, откуда и будет следовать требуемая оценка на размер максимального независимого множества. Для отыскания хроматического числа будет доказана специальная теорема общего вида, которая позволяет оценить количество цветов, используемых жадным алгоритмом при раскраске случайного графа.

Третья глава будет посвящена удивительному свойству устойчивости независимых множеств: к примеру, будет доказано, что даже если удалить каждое ребро кнезеровского графа с вероятностью 1/2, то размер максимального независимого множества не изменится. Данный результат будет доказан для графов С(п, г, < й), являющихся обобщением кнезеровских, а также для графов С(п,г, 1), принципиально отличающихся от них — для этого будет доказана теорема об устройстве независимых множеств в этом графе. В главе будет также изучена устойчивость независимых множеств в общем случае для случайного графа Ср(п,г, й): будет найдена пороговая вероятность для асимптотической устойчивости числа независимости этого графа.

Глава 1

Число независимости и хроматическое число случайного подграфа G(n, 3,1)

В данной главе мы дадим определение дистанционного графа G(n, 3,1), а также сформулируем основные результаты, касающиеся числа независимости и хроматического числа этого графа. Мы перейдем к рассмотрению случайных подграфов и докажем теорему 1.3.1 об асимптотическом поведении числа независимости случайного подграфа G(n, 3,1), а также теорему 1.3.2 об асимптотическом поведении хроматического числа. Результаты данной главы опубликованы в работах [53], [54], [55], [60].

1.1 Граф G(n, 3,1)

Отправной точкой для нашего исследования служит граф G(n, 3, 1) с множеством вершин V(n, 3) и множеством ребер E(n, 3,1), где

V(n, 3) = {x = (xi,..., Xn) : хг € {0,1}, xi + ... + Xn = 3},

E(n, 3,1) = {{x, y} : (x, y) = 1},

и (x, y) — скалярное произведение векторов в евклидовом пространстве. Иными словами, вершины графа G(n, 3,1) — (0,1)-векторы с ровно тремя единицами, а ребра — пары вершин, имеющих в точности одну общую единицу. В евклидовом пространстве имеет место равенство ||x — y||2 = ||x||2 + ||y||2 — 2(x,y), а так как все вершины графа имеют одинаковую норму д/3, то условие того, что скалярное произведение равно 1, в точности равносильно тому, что вершины находятся на расстоянии 2 друг от друга. Ввиду последнего обстоятельства граф G(n, 3,1) является дистанционным, т.е. его вершины — точки пространства, а ребра между вершинами проводятся в том случае, если точки находятся на определенном расстоянии (см. [30]).

Граф G(n, 3,1) впервые появился в работе Ж. Надя 1972 года (см. [11]), где он был использован для отыскания конструктивных оценок числа Рамсея (см. [31]).

Другое важное применение этот граф нашел в статье [6] Д. Лармана и К.А. Роджерса, которая вышла в том же 1972 году и посвящена классическому объекту комбинаторной геометрии — хроматическому числу x(Rn) евклидова пространства Rn:

x(Rn) = min{x : Rn = Vi U ... U Vx, V i V x, y e V |x - y| = 1}.

Иначе говоря, хроматическое число пространства — это минимальное количество цветов, в которые можно так покрасить все точки Rn, чтобы между одноцветными точками не было расстояния 1.

Суть наблюдения Лармана и Роджерса состояла в том, что, очевидно, x(Rn) > x(G(n, 3,1)), где x(G) — обычное хроматическое число графа G, равное наименьшему количеству цветов, в которые можно так покрасить все вершины графа, чтобы вершины одного цвета не были соединены ребром. Таким образом, задача отыскания нижней оценки хроматического числа пространства была сведена к оценке хроматического числа конечного графа.

Одна из наиболее стандартных нижних оценок хроматического числа абстрактного графа G = (V, E) имеет вид x(G) > -Ощ. Здесь a(G) — число независимости графа G, равное максимальному числу вершин графа, которые попарно не соединены ребрами:

a(G) = max{|W| : Vx,y e W {x,y} £ E}.

Ж. Надь доказал следующую теорему. Теорема 1.1.1. (Надь) Справедлива формула

{n, если n = 0 (mod 4), n — 1, если n = 1 (mod 4), n — 2, если n = 2,3 (mod 4).

Из этой теоремы сразу вытекала рекордная на тот момент оценка

C3 n2

x(r») > x(G(n,31» > O(G(c:M)) ^ т

В принципе могло статься, что оценка, найденная с помощью числа независимости, подлежит улучшению. Однако совсем недавно в совместной работе Й. Балога, А.В. Косточки и А.М. Райгородского (см. [32]) была доказана

Теорема 1.1.2. (Балог, Косточка, Райгородский)

Если n = 2k, то x(G(n, 3,1)) = (n—1)6(n—2). В любом случае x(G(n, 3,1)) = n2 + O(n).

Таким образом, для графа G(n, 3,1) известно и число независимости, и хроматическое число.

1.2 Случайные графы в модели Эрдеша—Реньи

В 1959 году П. Эрдеш и А. Реньи предложили модель случайного графа, которая к настоящему времени очень глубоко изучена (см. [16], [18], [33]). Случайный граф Ор(п) в этой модели — это случайный элемент со значениями во множестве всех графов на п вершинах Уп = {1,... ,п} без петель, кратных ребер и ориентации, имеющий биномиальное распределение, т.е.

Р [Ср(п) = (Уп,£ )]= р1Е |(1 - р)сП—|Е |.

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

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

Р [|д(Ср(п)) - /(п)| <р(п)] ^ 1, п у го.

Теорема 1.2.1. (Боллобаш) Пусть р — это либо константа, либо произвольная функция, которая стремится к нулю при п ^ го, но при этом ограничена снизу величиной с, где с > 1. Положим 1 = т1-. Тогда с асимптотической

& п' 1—р

вероятностью 1 выполнены соотношения

п

а(Ср(п)) - 2logd(np), Х(^р(п))

21°ёй(пр)'

В случае постоянного р теорема была доказана в работе Б. Боллобаша 1988 года (см. [34]), а в случае меньших вероятностей ребра утверждение теоремы принадлежит Т. Лучаку, который установил его в 1991 году (см. [35]). Многочисленные результаты, уточняющие теорему 3, можно найти в книгах [18], [33].

Естественное обобщение модели Эрдеша-Реньи устроено следующим образом. Пусть дана некоторая последовательность графов НП = (УП, ЕП), в которой | У„] ^ то при п ^ то. Заметим, что здесь п не обязано быть числом вершин. Например, вполне годится Нп = С(п, 3,1), в которой (п, 3)| = СП. Определим случайный граф 0(НП,р) как случайный элемент со значениями во множестве всех остовных подграфов С = (УП,Е) графа НП и с биномиальным распределением, т.е.

Р (Нп,р) = (К,£)] = р|Е 1(1 - р)|Е«|-|Е I.

Понятно, что Ср(п) = 0(КП,р), где КП — полный граф на п вершинах. В работе нас будут интересовать характеристики случайных подграфов дистанционных графов Ср(п, г, й) = 0 (С(п, г, з),р).

1.3 Формулировки результатов

Результатами данной главы являются две теоремы:

Теорема 1.3.1. С асимптотической вероятностью 1 справедливо равенство

а (С^(п, 3,1)) = (1 + о(1))2пп.

Таким образом, теорема 1.3.1 утверждает, что асимптотической вероятностью 1 в случайном подграфе графа С(п, 3,1) найдется независимое множество размера порядка 2п п. Отметим, что данную оценку можно записать в виде

а(С1/2(п, 3,1)) = 0 (а(С(п, 3,1)) • V(п, 3)|)),

где символ 0 означает, что равенство выполнено с точностью до положительных констант в верхней и нижней оценке. Этот результат хорошо согласуется с классической теоремой 1.2.1, поскольку там а(КП) = 1, а ^2(|УП|) = п: в обоих случаях число независимости случайного подграфа в логарифм от числа вершин раз больше, чем число независимости исходного подграфа.

Вторая теорема касается хроматического числа случайного подграфа:

Теорема 1.3.2. С асимптотической вероятностью 1 справедливо неравенство

2

( ) п2 X (С1/2(п,3, ГО = (1 + .

Данная теорема утверждает, что с асимптотической вероятностью 1 вершины

2

графа можно правильно раскрасить в ~ ^^ П цветов, что равносильно тому, что

3 2 2

все ~ вершин можно разбить на ~ ^^ П независимых множеств. Это является более сильным результатом, чем существование одного независимого множества размера ~ 2п log2 п, а также улучшает результат, упомянутый в [36].

1.4 Числа независимости

Для доказательства теоремы 1.3.1 нам необходимо установить асимптотическое равенство. Один из наиболее простых способов это сделать — установить два неравенства. Мы уже использовали выше терминологию «асимптотическое равенство выполнено с асимптотической вероятностью 1». В аналогичном смысле мы будем понимать и асимптотические неравенства, т.е. утверждение типа «выполнено g(G1/2(n, 3,1)) < (1 + o(1))f (n) с асимптотической вероятностью 1» (здесь всякий раз будет f (n) ^ го при n ^ го) означает существование такой функции p аргумента n, что p = o(1) при n ^ го и

P [д(Gi/2(n, 3,1)) < (1 + p(n))f (n)] ^ 1, n ^ го.

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

Теорема 1.4.1. С асимптотической вероятностью 1 справедливо неравенство

a(Gi/2(n, 3,1)) < (1+ o(1))4n log2 n.

Во второй части мы предъявим конструкцию, которая даст оптимальную оценку снизу.

Теорема 1.4.2. С асимптотической вероятностью 1 справедливо неравенство

a(Gi/2(n, 3,1)) > (1+ o(1))2n log2 n.

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

Теорема 1.4.3. С асимптотической вероятностью 1 справедливо неравенство

a(Gi/2(n, 3,1)) < (1+ o(1))2n log2 n.

Таким образом, найдена асимптотика числа независимости графа Gi/2(n, 3,1) или, в каком-то смысле, доказан закон больших чисел для случайной величины a (Gi/2(n, 3,1)). Кроме этого, доказательство последней теоремы укажет, что практически все большие независимые множества должны иметь вид, как в конструкции из теоремы 1.4.2.

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

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

Пусть Хк = Хк(С\/2(п, 3,1)) — это функция от случайного графа, равная количеству к-вершинных независимых множеств в нем (т.е. множеств, элементы которых попарно не соединены ребрами). Оценим ее математическое ожидание:

EXk P [A является независимым множеством в Gi/2(n, 3,1)] .

AcV(n,3), |A|=k

Для того, чтобы множество A являлось независимым в графе Gi/2(n,3,1), необходимо, чтобы все ребра графа G(n, 3,1) внутри множества A (то есть, ребра подграфа, порожденного множеством A) отсутствовали. Так как каждое ребро попадает в случайный подграф с вероятностью 1/2 независимо от остальных ребер, то мы получаем

EXk = ^ 2-|{{x,y}GE(n,3,i): x,yeA}|,

AcV(n,3), |A|=k

т.е. в показателе экспоненты стоит число ребер подграфа графа G(n, 3,1), порожденного конкретным множеством вершин A. Из классической теоремы Турана (см. [37]) следует, что если k > a(G(n, 3,1)), то мы не только можем гарантировать наличие ребер в таком подграфе, но и можем эффективно оценить снизу число этих ребер. Дабы записать оценку, напомним, что согласно теореме 1.1.1, размер максимального независимого множества a(G(n, 3, 1)) = (1 + o(1))n при

n ^ го, а значит, k ^ го при n ^ го. Поэтому, верно неравенство

k2 k2

|{{х, y} 6 Е(n,3,1) : X, y е A}| > (1 + o(1))2a(G(n, 3,1)) = (1 + .

Имея на руках такую оценку, получаем, что

_ 2 2

EXk < ^ 2-(i+o(i))In = Ckcl2-(i+o(i))In,

AcV(n,3), |A|=k

так как число слагаемых в сумме равно числу способов выбрать k вершин из всех C\ вершин графа G(n, 3,1). Хорошо известно, что Cba < (у) , где e — основание натурального логарифма. Следовательно,

/ n3 \k 2 2

EXk < l^J 2-(i+°(i)) In = 23k log2 n-k log2 k-(i+o(i))In .

Видно, что существует функция k = k(n), которая асимптотически ведет себя как 4n log2 n, и с которой EXk ^ 0 при n ^ го. Отсюда с учетом неравенства Маркова вытекает утверждение теоремы:

P [a BGi/2(n, 3,1)) < 4(1 + o(1))n log2 n] = P [Xk = 0] > 1 - EXk ^ 1, n ^ го. Теорема 1.4.1 доказана.

1.4.2 Нижняя оценка

Если рассуждение из предыдущего параграфа было вполне стандартным и никак не использовало специфику графа С(п, 3,1) (за исключением величины его числа независимости), то здесь мы в большей мере будем опираться на структуру нашего графа. Прежде всего введем ряд обозначений и терминов.

Пусть [п] = {1,..., п}. Каждой вершине х € V(п, 3) можно поставить в естественное соответствие тройку элементов из [п]: это просто номера координат, на которых у вектора х находятся единицы. Тогда ребро в графе С(п, 3) — это пара троек, пересекающихся ровно по одному элементу.

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

Для графа С(п, 3,1) любая клика — это набор троек в [п], попарные пересечения которых имеют мощность 1. Ясно, что ш(С(п, 3,1)) = (1 + о(1))П при п ^ то (фиксируется один элемент [п], а оставшаяся часть множества [п] разбивается на непересекающиеся пары).

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

Итак, положим т = 2 бьем [п] на части Л1 = [т

, где [х] — это обычная целая часть числа х. Разо-

2^2 п_

и Я2 = [п]\[т]. Сперва опишем построение одной клики Оь Для этого возьмем в Л1 непересекающиеся пары {1, 2}, {3,4}, {5,6},..., {т — 1, т} (благо т четное). К каждой из этих пар добавим элемент т + 1 € Я2. Это и есть искомая клика. Число вершин в ней Щ ~ ^^ п, п ^ то, т.е. оно отличается от максимально возможного лишь в примерно логарифм раз. Аналогично построим еще п — т — 1 клику О2,... , Оп—т, добавляя к каждой из наших пар в Л1 элемент т + 2 € Я2, элемент т + 3 € Я2 и так далее. Очевидно, что для любых 2,3, 2 = 3, и для любых х из О у из О ребра между х, у нет: эти тройки могут либо вовсе не пересекаться, либо пересекаться сразу по какой-то паре из Л1.

Как мы знаем, случайный граф С1/2(п, 3,1) получается из графа С(п, 3,1) в результате взаимно независимого выбора ребер из Е(п, 3,1) с одной и той же вероятностью |. Поэтому на кликах О1,..., Оп—т возникают независимые копии случайного графа Эрдеша-Реньи С1/2(т/2). Отметим, что эти копии независимы и с точки зрения теории вероятностей (как случайные элементы), и с точки зрения теории графов (между ними нет ребер).

При р = 2 теорема 1.2.1 говорит, что с асимптотической вероятностью 1 выполнено а(С1/2(т/2)) ~ 2^2 т при т ^ то, но т лишь в логарифм раз меньше

П

п, откуда а(С1/2(т/2)) ~ 2log2 п при п ^ то. Более того, скорость стремления вероятности к единице очень высока (см. [18]). Заведомо при правильно подобранной бесконечно малой и больших п верна оценка

Р [а(С1/2(т/2)) > 2(1 + о(1)) ^ п] > 1 — е-п.

А это значит, что при п ^ то

Р [V г = 1,..., п — т а(£ 1/2)) > 2(1 + о(1))^2 п] > (1 — е-п)П—т ^ 1.

Следовательно, с асимптотической вероятностью 1 в случайном графе С1/2(п, 3, 1) есть п — т независимых множеств размера 2(1 + о(1))^2 п, между которыми точно нет ребер. Вместе они составляют, тем самым, одно независимое множество размера 2(п — т)(1 + о(1)) п ~ 2п log2 п, что и требовалось доказать.

Отметим, что данная конструкция обладает интересным свойством. А именно, в предыдущем разделе была использована оценка на число ребер: по теореме Турана внутри множества вершин графа С(п, 3,1) размера к найдется хотя бы ~ 2П ребер. Для конструкции, описанной выше, имеем к ~ 2п log2 п, а число ребер равно сумме чисел ребер в каждой из клик, то есть, ~ пС|1о п ~ 2п log2 п,

что в точности соответствует оценке 2п. Таким образом, оценку на число ребер принципиально улучшить нельзя.

1.4.3 Оптимальная верхняя оценка

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

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

Для удобства введем дополнительные обозначения: пусть ё = |_(^2 п)2/5| и т = |_(^2 п)4/5_|. На самом деле, нам достаточно того, что ё2 = о(^2 п), а ёт = п), но выбор именно таких значений упрощает выкладки. Также,

если А — некоторое множество вершин графа С(п, 3,1), а г и 3 — два элемента из множества {1, 2,...,п}, то обозначим А(г,3) множество вершин-троек из А, содержащих элементы г и 3.

Будем говорить, что множество А является плотной конструкцией, если существуют такие ё +1 элементов и, г>1, -и2,..., что выполнены следующие условия:

1. |А(и,^)| = т, г = 1, 2,..., ё,

2. А = УА(и,-иг), то есть каждая тройка множества А содержит элемент и и какой-либо из элементов г>г,

3. А(п,г^) П А(п,у^) = 0 при % = з, то есть в множестве А не содержится троек вида (п,vi,vj).

Смысл данного определения заключается в том, что верно

Предложение 1.4.1. С асимптотической вероятностью 1 никакая плотная конструкция не является независимым множеством в графе С1/2(п, 3,1).

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

Пусть А — некоторое множество вершин. По множеству А построим вспомогательный граф Я(А): вершинами этого графа будут элементы {1, 2,..., п}, а ребро между двумя элементами % и ] проведем в том случае, если |А(%,])| > 1 + т. Рассмотрим тройки из множества А, содержащие некоторый элемент %. Данные тройки естественным образом разбиваются на четыре класса.

1. К первому классу отнесем те тройки, которые содержат внутри себя хотя бы два ребра графа Я(А), то есть такие тройки (%,3,к), что среди трех пар элементов (%, 3), (%, к) и (3, к) найдутся хотя бы две, образующие в графе Я(А) ребро. Этот класс троек мы будем обозначать 1^(А).

2. Второй класс X(А) будет состоять из тех троек (%,3,к), которые содержат внутри себя ровно одно ребро графа Л (А), при этом не инцидентное элементу %, то есть ребро (3, к).

3. К третьему классу ^¿(А) отнесем те тройки, которые содержат внутри себя ровно одно ребро графа Л(А), но инцидентное вершине % (то есть либо ребро (%,3), либо ребро (%,к)).

4. Четвертый класс Zi(A) состоит из всех остальных троек, содержащих элемент %: тех, которые внутри себя не содержат ни одного ребра графа Л(А).

Введем также обозначения для размеров множеств:

^(А) = |^(А)|, уг(А) = |^(А)|, ¿¿(А) = |^(А)|, wг(A) = |^(А)|,

п п п п

х(А) = ^ ^¿(А), у(А) = ^ У ¿(А), ¿(А) = ^ ¿¿(А), W(A) = ^ w¿(A).

¿=1 ¿=1 ¿=1 ¿=1 Скажем, что множество вершин А содержит плотную конструкцию, если найдется подмножество В С А, являющееся плотной конструкцией. Оказывается, что размер множества А, а также число ребер внутри множества А может быть почти точно определен из характеристик Х(А) и ¿(А). Более конкретно, верны следующие предложения.

Предложение 1.4.2. Если множество А не содержит плотной конструкции, то его размер равен х(А) + ^^ + о(п п).

Предложение 1.4.3. Число ребер внутри множества А, которое не содержит плотной конструкции, не меньше (ж(А)+;г(А)) + 0 ((х(А) + ¿(А)) п).

Предложение 1.4.4. Пусть даны четыре набора чисел хг, уг, гг и йг (г =

п п п п

1, 2,..., п). Положим х = ^ у = Е У^, ) = ^ и й = ^ йг. Тогда число

г=1 г=1 г=1 г=1

способов выбрать множество А, которое не содержит плотной конструкции и для которого хг(А) = уг(А) = уг, гг(А) = и йг(А) = йг, не превосходит

2(1+о(1))(ж+.г) п+о(пlog2 п)

Отметим, что оценка, полученная с помощью классической теоремы Тура-на в первой части раздела, утверждает, что в любом множестве вершин графа С(п, 3,1), имеющем мощность к, найдется хотя бы (1 + о(1)) ^ ребер. Более того, во второй части раздела было показано, что эту оценку принципиально улучшить нельзя.

Однако для множеств А, не содержащих плотной конструкции, предложение 1.4.2 дает приближение к « х(А) + ^у^, а стало быть, оценка числа ребер из пред-

ложения 1.4.3 примерно равна величине (к+ , которая, несомненно, больше величины 2П2 при больших )(А).

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

Зафиксируем £ > 0. Нам необходимо оценить доказать стремление к нулю вероятности существования независимого множества А с V(п, 3) размера больше (2 + £)п п. Очевидно,

Р [а (£1/2(п, 3,1)) > (2 + £)пlog2 п] <

< Р [ЗА, |А| > (2 + £)пlog2 п : А независимо в С1/2(п, 3,1)] . Данную вероятность можно разбить на два слагаемых:

Р [ЗА, |А| > (2 + £)п log2 п, А содержит плотную конструкцию:А независимо] +

+Р [ЗА, |А| > (2 + £)п log2 п, А не содержит плотной конструкции:А независимо]

Первое слагаемое стремится к нулю при п ^ то в силу предложения 1.4.1, а значит, мы можем перейти к оценке второго слагаемого. Согласно предложению 1.4.2 из того, что А не содержит плотной конструкции и |А| > (2 + £)п п, следует, что х(А) + ^^ > (2 + £/2)п п при достаточно большом п. Так как

Список литературы диссертационного исследования кандидат наук Пядеркин Михаил Михайлович, 2019 год

Литература

[1] А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦ-НМО, Москва, 2007.

[2] А.М. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи Матем. Наук, 2001, 56(1): 107-146.

[3] A. Soifer, The Mathematical Coloring Book, Springer, 2009.

[4] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.

[5] P. Erdos, N.G. de Bruijn, A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951) 371-373

[6] D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

[7] P. Frankl, R. Wilson, Intersection theorems with geometric consequences , Combinatorica, 1 (1981), 357 - 368.

[8] V.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.

[9] A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202 - 248.

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

[11] Z. Nagy, A certain constructive estimate of the Ramsey number, Matematikai Lapok, 23 (1972), N 301-302, 26.

[12] L.A. Szekely, Erdos on unit distances and the Szemeredi-Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

[13] Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, М.: Радио и связь, 1979.

14] L. Bassalygo, G. Cohen, G. Zemor, Codes with forbidden distances, Discrete Mathematics, 213 (2000), 3 - 11.

15] A.M. Raigorodskii, Combinatorial geometry and coding theory, Fundamenta Informatica, 2015.

16| Н. Алон, Дж. Спенсер, Вероятностный метод, Москва, БИНОМ. Лаборатория знаний, 2007.

17] Н.Н. Кузюрин, Вероятностные приближенные алгоритмы в дискретной оптимизации, Дискретн. анализ и исслед. опер., сер. 2, 2002, 9(2): 97—114.

18] B. Bollobas, Random Graphs, 2nd Edition, Cambridge University Press, 2001.

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

20! Erdos P., Renyi A., On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17 - 61.

21] J. Komlos, E. Szemeredi, Hamilton cycles in random graphs. Colloq. Math. Soc. J. Bolyai, 10 (1975), 1003 - 1011.

22] M. Ajtai, J. Komlos and E. Szemeredi, The longest path in a random graph, Combinatorica 1 (1981), 1 - 12.

23] F. Chung and L. Lu, The diameter of sparse random graphs, Adv. in Appl. Math. 26 (2001), 257 - 279.

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

25] Seidel, Raimund, Aragon, Cecilia R. Randomized Search Trees, Algorithmica, 16 (1996), 464 - 497.

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

27] N.C. Wormald, Models of random regular graphs., Surveys in Combinatorics 1999, LMS Lecture Note Series 267 (1999), 239 - 298.

28] P. Frankl, Z. Fiiredi, Forbidding just one intersection, Journal Combin. Theory A, 39 (1985), 160 - 176.

29] Rudolf Ahlswede and Levon H. Khachatrian, The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets, J. Comb. Th. Ser. A 76 (1996), 121 - 138.

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

[31] R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, John Wily and Sons, NY, Second Edition, 1990.

[32] J. Balogh, A.V. Kostochka, A.M. Raigorodskii, Coloring some finite sets in Rn, Discussiones Mathematicae Graph Theory, 33 (2013), N1, 25 - 31.

[33] S. Janson, T. Luczak, A. Rucinski, Random graphs, Wiley, NY, 2000.

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

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

[36] А.С. Гусев, Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа, Матем. заметки, 97 (2015), N3, 342 - 349.

[37] Ф. Харари, Теория графов, Москва, "Мир", 1973.

[38] D.G. Larman, A note on the realization of distances within sets in Euclidean space, Comment. Math. Helvet., 53 (1978), 529 - 535.

[39] М. Холл, Комбинаторика, Москва, "Мир", 1970.

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

[41] J. Matousek, Using the Borsuk - Ulam theorem, Universitext, Springer, 2003.

[42] P. Erdos, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, 12 (1961), 313 - 320.

[43] M. Deza, P. Frankl, Erdos-Ko-Rado theorem — 22 years later, SIAM J. Alg. Disc. Methods, 4 (1983), 419 - 431.

[44] B. Bollobas, P. Erdos, Cliques in random graphs, Math. Proc. Cambridge Phil. Sot., 80 (1976), 419 - 427.

[45] R. Ahlswede, V.M. Blinovsky, Lectures on advances in combinatorics, Springer, 2008.

[46] R. Ahlswede, L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin., 18 (1997), 125 - 136.

[47] P. Frankl, On intersecting families of finite sets, Journal of Combinatorial Theory Ser. A, 24 (1978), 146 - 161.

[48] J. Balogh, T. Bohman, D. Mubayi, Erdos-Ko-Rado in random hypergraphs, Combin. Probab. Comput., 18 (2009), N5, 629 - 646.

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

[50] Jozsef Balogh, Bela Bollobas and Bhargav P. Narayanan. Transference for the Erdos-Ko-Rado theorem, Forum of Mathematics, Sigma (2015), Vol. 3, e23.

[51] S. Das and T. Tran, A simple removal lemma for large nearly-intersecting families, Electronic Notes in Discrete Mathematics 49 (2015), 93 - 99.

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

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

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

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

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

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

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

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

[60] М.М. Пядеркин, А.М. Райгородский, О хроматическом числе случайного подграфа некоторого дистанционного графа, Труды МФТИ. Т. 10 (2018), N4. 5 - 13.