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

• Буркин Антон Валерьевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Буркин Антон Валерьевич

Содержание

Введение

1 Малые подгафы и планарность случайных подграфов дистан-

ционного графа с постоянными r, s

1.1 Введение

1.2 Малые подграфы

1.2.1 Введение

1.2.2 Описание модели и новые результаты

1.2.3 Вспомогательные утверждения

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

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

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

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

1.3 Планарность

1.3.1 Введение и новые результаты

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

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

2 Малые подграфы и их расширения в случайном подграфе сим-

метричного дистанционного графа

2.1 Введение

2.2 Описание модели и новые результаты

2.3 Вспомогательные утверждения

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

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

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

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

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

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

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

3 Малые подграфы и их расширения в семействе случайных под-

графов плотных дистанционных графов

3.1 Описание модели и новые результаты

3.1.1 Основные понятия и формулировки теорем

3.1.2 Формулировки основных лемм

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

3.2.1 Дополнительные определения и предварительные замечания

3.2.2 Вспомогательные утверждения

2

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

Заключение

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

3

Введение

Диссертация посвящена изучению распределения малых подграфов и смеж-

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

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

В данной работе исследуются случайные подграфы широкого класса ди-

станционных графов, определенного ниже. Их изучение мотивировано зада-

чами дискретной (комбинаторной) геометрии, наиболее известными из кото-

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

(см. [1–13]). В частности, графы, рассмотренные в первой главе, позволяют по-

лучать хорошие оценки хроматического числа в малых размерностях, а с помо-

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

того, что хроматическое число евклидового пространства растет экспоненци-

ально как функция от размерности.

Рассматриваемые дистанционные графы G(n, r, s) = (V (n, r), E(n, r, s)) (где

V (n, r) � множество вершин, а E(n, r, s) � множество ребер) определяются

следующим образом:

V (n, r) = {x = (x1 , . . . , xn ) : xi 2 {0, 1}, x1 + . . . + xn = r},

E(n, r, s) = {{x, y} : hx, yi = s},

где hx, yi � евклидово скалярное произведение. Название этих графов объяс-

няется тем, что две вершины графа смежны тогда и только тогда, когда они

находятсяpна определенном расстоянии друг от друга, в данном случае на рас-

стоянии 2(r s).

Графы G(n, r, s) можно определить и другим образом. Пусть F � некоторое

множество мощности n. Тогда вершинами нашего графа будут все r-элементные

подмножества F, а два подмножества будут соединены ребром тогда и только

тогда, когда они пересекаются ровно по s элементам, т.е.

✓ ◆

F

V (n, r) = , E(n, r, s) = {{A, B} : A, B 2 V (n, r), |A \ B| = s}.

r

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

пересекающихся множеств.

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

Пусть у нас есть фиксированный неориентированный граф без петель G, тогда

его случайным подграфом Gp будет граф, в котором каждое ребро исходного

графа проводится с вероятностью p независимо от остальных ребер (или, что

то же самое, каждое ребро удаляется с вероятностью 1 p). Наиболее изучен-

ная модель случайного подграфа � случайный граф Эрдеша–Реньи, в котором

4

исходный граф G представляет собой полный граф на n вершинах. После того,

как модель была впервые представлена в статьях П. Эрдеша и А. Реньи [14,15],

она интенсивно изучалась рядом авторов. Подробное изложение существующих

результатов по теории случайных графов представлено в [16–19].

Многие работы посвящены изучению асимптотических свойств случайного

графа. Формально под свойством графов для некоторого n понимается любое

подмножество множества всех неориентированных графов на n вершинах. При-

мерами таких свойств являются свойство содержать некоторый фиксирован-

ный граф в качестве подграфа, свойство графа быть связным, свойство графа

иметь хроматическое число, равное пяти. Оказывается, для многих графовых

свойств существует некоторая пороговая вероятность p⇤ = p⇤ (n) (как функция

от числа вершин n), такая, что для вероятности ребра p = o(p⇤ ) случайный

граф определенным свойством с вероятностью, стремящейся к 1, не облада-

ет, а при p = w(p⇤ ), напротив, обладает (или наоборот). Здесь f (n) = o(g(n))

(f (n) = w(g(n))) означает, что для любого C > 0 существует n0 > 0, такое, что

для любого n > n0 выполнено |f (n)| < C|g(n)| (C|g(n)| < |f (n)|). Для этих от-

ношений мы также будем использовать обозначения f (n) ⌧ g(n) и f (n) g(n)

соответственно. Например, для свойства графа “быть связным” пороговой будет

функция p⇤ = ln n/n. Более того, известно, что пороговые вероятности суще-

ствуют для любых монотонных свойств, то есть таких свойств A, что если

произвольный подграф H ✓ G удовлетворяет свойству A, то и граф G этому

свойству удовлетворяет.

Отметим некоторые работы, посвященные асимптотическим свойствам слу-

чайного графа в классической модели. Так, изучением малых подграфов зани-

мались П. Эрдеш, А. Реньи (см. [14, 15, 20]), К. Шургер [21], Б. Боллобаш [22],

З. Палка [23], А. Д. Барбур [24]. Древесным компонентам случайного графа по-

священы те же работы П. Эрдеша и А.Реньи, результаты которых уточнены в

более поздней статье Б. Боллобаша [25]. Феномен гигантской компоненты по-

дробно изучали, помимо П. Эрдеша, А. Реньи и Б. Боллобаша, такие авторы,

как Т. Лучак, С. Янсон, Д. Кнут, Б. Питтель, Дж. Вирман и др. (см. [26–29]).

Связностью случайного графа занимались Е. Н. Гильберт [30], Т. Л. Остин [31],

П. Эрдеш, А. Реньи [14, 32], Б. Боллобаш [33], В. Е. Степанов [34–36], И. Н. Ко-

валенко [37], Г. И. Ивченко [38] и др.

Предмет нашего исследования � случайные подграфы дистанционных гра-

фов G(n, r, s), которые мы будем для краткости называть случайными дистан-

ционными графами Gp (n, r, s). Нас, в первую очередь, будет интересовать свой-

ство случайного дистанционного графа содержать некоторый фиксированный

граф в качестве подграфа. Примером такого свойства будет, например, свойство

графа содержать треугольник. Такие свойства хорошо изучены для классиче-

ской модели Эрдеша–Реньи, но почти не были исследованы в случае графов

5

Gp (n, r, s), за исключением случая r = n/2, s = n/4, частично рассмотренного

М. Е. Жуковским в [39].

В первой главе рассмотрен случай графов Gp (n, r, s) с постоянными r, s, не

зависящими от n. В этой ситуации, как легко видеть, число вершин графа и его

степень (граф регулярный) растут как степенные функции от размерности n. В

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

тесно связанным с разложением этих графов на компоненты двусвязности. В

качестве следствия полученных результатов удается описать множество поро-

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

Задача о планарности случайного графа Эрдеша–Реньи изучалась, как и

задача о малых подграфах, еще в статьях П. Эрдеша и А. Реньи [14, 15]. В

классической модели функция p⇤ = 1/n является пороговой вероятностью для

свойства планарности случайного графа. А. Фризом и М. Кривелевичем было

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

мальной степенью t ! 1 пороговая вероятность есть функция p⇤ = 1/t.

Будем рассматривать далее случайные подграфы регулярных подграфов G

на N вершинах со степенью N1 ! 1. Мы доказываем лемму, утверждаю-

щую, что в случае, когда N14 N , пороговая вероятность для планарности

не может быть меньше (в смысле “о малого”), чем p = 1/N1 . Вместе с теоре-

мой Кривелевича–Фриза, это утверждение однозначно определяет для таких

графов пороговую вероятность для планарности p⇤ = 1/N1 . Более того, эта по-

роговая вероятность является точной, т.е. граф Gp планарен при p ⇠ cp⇤ , если

c < 1, и непланарен при p ⇠ cp⇤ , если c > 1. Здесь и далее f (n) ⇠ g(n) озна-

чает, что для любого " > 0 найдется такое N , что для всех n > N выполнено

(1 ")g(n) 6 f (n) 6 (1 + ")g(n).

В случае же, когда N14 ⌧ N , мы доказываем, что пороговая вероятность

может лежать в промежутке

" ✓ ◆1/9 #

4

1 N1

,

N1 N N1

Оказывается, что нижняя оценка достигается, причем достигается на случай-

ных дистанционных графах Gp (n, r, s) с s > 3r/4.

Вторая глава посвящена случайному подграфу симметричного дистанцион-

ного графа G(n, n/2, n/4). Обобщены и усилены результаты, полученные М. Е.

Жуковским в [39]. Ранее была доказана теорема о пороговой вероятности для

свойства содержать строго сбалансированный граф. В настоящей работе мы

распространяем это утверждение на произвольные графы и исследуем “кри-

тический” случай, когда вероятность асимптотически равна пороговой. В си-

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

также теорему о пороговых вероятностях для так называемых свойств расши-

рений. Будучи своего рода обобщениями свойств содержать малые подграфы,

6

для классической модели Эрдеша–Реньи они были рассмотрены Дж. Спенсером

в [40]. В третьей главе эти результаты распространяются на случай семейства

графов Gp (n, ↵n, ↵2 n). Из доказанных утверждений следует, что дистанцион-

ные графы G(n, ↵n, ↵2 n) являются в определенном смысле псевдослучайными.

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

Цель работы

Цель диссертации заключается в изучении класса случайных дистанционных

графов с точки зрения их фиксированных подграфов. В частности, решаются

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

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

подграфов в окрестности пороговой вероятности.

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

В работе используются методы теории вероятностей, комбинаторики и тео-

рии графов.

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

Все основные результаты являются новыми.

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

Диссертация носит теоретический характер. Полученные результаты полез-

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

чайных подграфов регулярных графов.

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

1. Получены утверждения, описывающие распределение малых подграфов в

случайных подграфах дистанционных графов G(n, r, s) с постоянными r, s.

2. Найдена пороговая вероятность для планарности случайного подграфа

G(n, r, s) с постоянными r, s.

3. Найдена пороговая вероятность для свойства содержать произвольный фик-

сированный подграф в случайном подграфе G(n, n/2, n/4) и исследовано

распределение количества подграфов в точке пороговой вероятности, а так-

же найдены пороговые вероятности для свойств расширений; последние

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

4. Те же результаты распространены на семейство графов G(n, ↵n, ↵2 n).

7

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

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

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

и конференциях:

� Семинар �Вероятностные и алгебраические методы в комбинаторике� на

кафедре математической статистики механико-математического факульте-

та МГУ под руководством профессора А. М. Райгородского (2014 г.)

� Семинар �Современные проблемы теории чисел� под руководством про-

фессоров С. В. Конягина и И. Д. Шкредова (2014 г.)

� Семинар кафедры теории чисел механико-математического факультета МГУ

под руководством профессора Н. Г. Мощевитина (2014 г.)

� Конференция �Summit:240� (Будапешт, Венгрия, 2014 г.)

� Конференция �Ломоносов-2015� (Москва, 2015 г.)

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

культета МГУ (2018 г.)

Публикации

По теме диссертации опубликованы работы [41–44] в рецензируемых жур-

налах из перечня ВАК. Все результаты диссертации были получены автором

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

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

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

становку задач, поддержку и неоценимую помощь в работе. Автор также бла-

годарен д.ф.-м.-н. Максиму Евгеньевичу Жуковскому за полезные замечания.

8

1 Малые подгафы и планарность случайных подграфов

дистанционного графа с постоянными r, s

1.1 Введение

Как уже было упомянуто выше, в 1959 г. П. Эрдешем и А. Реньи была пред-

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

роятностью p независимо от остальных ребер (см., например, [15]). Более фор-

мально, пусть n � натуральное число и 0 6 p 6 1. Случайным графом G(n, p)

называется случайный элемент со значениями во множестве ⌦n и распределени-

ем Pn,p на Fn , где ⌦n � множество всех неориентированных графов G = (Vn , E)

без петель и кратных ребер с множеством вершин Vn = {1, . . . , n}, Fn = 2⌦n ,

2

Pn,p (G) = p|E| (1 p)Cn |E| .

Напомним, что плотностью графа F с k вершинами и l ребрами называ-

ется отношение ⇢(F ) = l/k. Граф F � сбалансированный (строго сбалансиро-

ванный), если для любого его собственного непустого подграфа H выполнено

⇢(H) 6 ⇢(F ) (⇢(H) < ⇢(F )).

1.2 Малые подграфы

1.2.1 Введение

В данном разделе мы сформулируем основные классические теоремы, опи-

сывающие распределение малых подграфов в случайном графе Эрдеша–Реньи.

П. Эрдеш и А. Реньи в [15] доказали следующую теорему о пороговой веро-

ятности для свойства содержать копию фиксированного графа.

Теорема 1.1 (П. Эрдеш, А. Реньи). Пусть F � связный сбалансированный

граф с k вершинами и l ребрами. Тогда вероятность p = n k/l является поро-

говой для свойства содержать копию F .

Для данного графа F обозначим X = XF число подграфов G(n, p), изо-

морфных F . Б. Боллобашем в [22] была доказана теорема о распределении X

для строго сбалансированных графов F при p ⇠ cn k/l , c > 0.

Теорема 1.2 (Б. Боллобаш). Пусть F � строго сбалансированный граф с

k вершинами и l ребрами и a � количество автоморфизмов F . Пусть p ⇠

cn k/l , c > 0. Тогда распределение величины X сходится к пуассоновскому с

параметром = cl /a.

Следующая теорема, доказанная также Б. Боллобашем, представляет собой

центральную предельную теорему для случайного графа G(n, p).

9

Теорема 1.3 (Б. Боллобаш). Пусть F � строго сбалансированный граф с k

вершинами и l ребрами, и a � количество его автоморфизмов. Пусть функция

p = p(n) такая, что pnk/l ! 1 и pnk/l " ! 0 для любого " > 0. Тогда

X n d

p ! N (0, 1),

n

где n = nk pl /a.

Тем же автором, наряду с А. Ручински, Э. Винсом (см. [45]) и др., было

получено обобщение теоремы 1.1 на случай произвольного графа. Напомним,

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

⇢max (F ) = max{⇢(H) : H ⇢ F }.

Теорема формулируется следующим образом.

Теорема 1.4 (Б. Боллобаш; А. Ручински, Э. Винс). Пусть F � произвольный

фиксированный граф с максимальной плотностью ⇢max > 0. Тогда вероят-

max

ность p = n 1/⇢ является пороговой для свойства содержать копию F .

1.2.2 Описание модели и новые результаты

Напомним, что в настоящей работе рассматривается класс дистанционных

графов G(n, r, s) = (V (n, r), E(n, r, s)), в которых

V (n, r) = {x = (x1 , . . . , xn ) : xi 2 {0, 1}, x1 + . . . + xn = r},

E(n, r, s) = {{x, y} : hx, yi = s}.

Количество вершин G(n, r, s) будем обозначать N . Ясно, что N = |V (n, r)| =

Cnr .Кроме того, граф G(n, r, s) � регулярный степени N1 = Crs Cnr sr .

Как уже было сказано ранее, предметом нашего изучения является слу-

чайный дистанционный граф Gp (n, r, s), т.е. случайный элемент со значени-

ями в ⌦n,r,s и распределением Pn,r,s,p на Fn,r,s , где ⌦n,r,s � множество всех

остовных подграфов G = (V (n, r), E) полного дистанционного графа G(n, r, s),

Fn,r,s = 2⌦n,r,s , Pn,r,s,p (G) = p|E| (1 p)|E(n,r,s)| |E| .

М. Е. Жуковским в [39] была доказана следующая теорема для r = n/2 и

s = n/4.

Теорема 1.5 (М. Е. Жуковский). Пусть r = n/2 и s = n/4. Пусть N обозна-

чает количество вершин графа G(n, r, s) при таких r и s. Пусть F � строго

сбалансированный граф с k вершинами и l ребрами. Тогда функция

k/l

p

p=N ln N

является пороговой вероятностью для свойства содержать копию графа F .

10

 В данной главе мы исследуем случай, когда r и s постоянны, и доказываем

аналогичные результаты.

Далее мы будем использовать обозначение X = X(F ) и для количества

подграфов, изоморфных F , в Gp (n, r, s).

Теорема 1.6. Пусть r 2 N и s 2 N [ {0} фиксированы. Пусть F � связный

сбалансированный граф c k вершинами и l ребрами. Тогда функция

kr (k 1)s

p=n l

является пороговой вероятностью для свойства содержать граф F .

kr (k 1)s

Кроме того, при p n l имеет место закон больших чисел, т.е.

для любого " > 0 ✓ ◆

X

P 1 < " ! 1.

EX

Теорема 1.6 будет доказана в п. 1.2.4.

Напомним, что связный граф называется двусвязным, если при удалении лю-

бой его вершины и всех инцидентных ей ребер граф остается связным (см., на-

пример, [46]). Компонентами двусвязности связного графа F называются его

максимальные двусвязные индуцированные подграфы. Будем называть нетри-

виальными компоненты двусвязности с числом вершин, большим двух. Извест-

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

Точки, по которым пересекаются нетривиальные компоненты, назовем точка-

ми касания. Пусть в графе F последние образуют множество {c1 , c2 , . . . , cj }.

Кратностью точки касания k(ci ) будем называть количество

Pj нетривиальных

компонент, пересекающихся по ней. Обозначим h сумму i=1 (k(cj ) 1).

Теорема 1.7. Пусть r 2 N и s 2 N [ {0} фиксированы. Пусть F � связ-

ный сбалансированный граф с k вершинами и l ребрами. Пусть F содержит

b нетривиальных компонент двусвязности и число вершин, лежащих в них,

равно d. Пусть h, как и выше, � число точек касания. Кроме того, a � ко-

kr (k 1)s

личество автоморфизмов F . Пусть p ⇠ cn l , n ! 1, где c > 0. Тогда

распределение величины X сходится к пуассоновскому с параметром

cl

= (Crs )k d+2b h 1

.

ar!((r s)!)k 1

Теорема 1.7 будет доказана в п. 1.2.5.

Теорема 1.8. Пусть r 2 N и s 2 N [ {0} фиксированы. Пусть F � связный

сбалансированный граф с k вершинами и l ребрами и b, d, h, a определены так

kr (k 1)s

же, как в теореме 1.7. Пусть функция p = p(n) такая, что pn l !1и

kr (k 1)s

pn l "

! 0 для любого " > 0. Тогда

X d

p n ! N (0, 1),

n

11

где

l nkr (k 1)s

n = Mp , M ⇠ (Crs )k d+2b h 1

.

ar!((r s)!)k 1

Теорема 1.8 будет доказана в п. 1.2.6.

Будем обозначать v(H) и e(H) число вершин и число ребер графа H соот-

ветственно. Пусть также

⇢

v(H)r (v(H) 1)s

⌧ (F ) = min .

H⇢F e(H)

Теорема 1.9. Пусть r 2 N и s 2 N [ {0} фиксированы. Пусть F � произ-

вольный связный граф и

⇢ ⇢

v(H)r (v(H) 1)s v(H)r (v(H) 1)s

min = min . (1.1)

H⇢F e(H) H⇢F e(H)

H связен

Тогда функция

⌧ (F )

p=n

является пороговой вероятностью для свойства содержать граф F . Как и

для связных сбалансированных графов, при p n ⌧ (F ) выполняется закон

больших чисел: для любого " > 0

✓ ◆

X

P 1 < " ! 1.

EX

Теорема 1.9 будет доказана в п. 1.2.7.

Отметим, что при s = 0 условие (1.1) выполнено для любых связных F .

Этот случай соответствует случайным подграфам графов G(n, r, 0), известных

также как кнезеровские. Отметим также, что условие (1.1) при определенных

r и s не выполнено, например, для графа F , полученного объединением двух

копий K5 и пути из четырех вершин, соединяющего две вершины из разных

копий, и теорема 1.9 в этом случае неприменима.

Приведем пример, демонстрирующий кардинальное отличие случайного гра-

фа Gp (n, r, s) от классической модели G(n, p). Пусть граф F есть K4 , к вершине

которого присоединено еще одно ребро. Тогда в силу теоремы 1.9 при определен-

ных r, s существует такая функция p, что P (XK4 > 0) ! 1, но P (XF > 0) ! 0

при n ! 1. В модели случайного графа Эрдеша–Реньи такая ситуация невоз-

можна.

Доказательства теорем 1.6–1.9 опубликованы в статье [41].

1.2.3 Вспомогательные утверждения

Для любых смежных x, y 2 V (n, r) рассмотрим простые пути (x1 = x, x2 , . . .,

xk = y), x1 ⇠ x2 ⇠ . . . ⇠ xk . Здесь мы записываем x1 ⇠ x2 , если x1 и x2

12

соединены ребром. Обозначим Pk количество таких путей. Пусть также N2 �

число вершин, дополняющих произвольное ребро до треугольника. Ясно, что

N2 не зависит от выбора ребра и N2 ⇠ (r 1s)! nr s , n ! 1.

Лемма 1.1. Если k = const, то Pk ⇠ N2k 2 , n ! 1.

Доказательство. Несложно заметить, что количество вершин графа G(n, r, s),

соединенных с двумя вершинами z1 , z2 , зависит лишь от их скалярного произ-

ведения (z1 , z2 ). Таким образом, если x и y � концевые вершины простого пути

длины k, то, зная скалярное произведение вершин с номерами k 2 и k, мы од-

нозначно находим число таких вершин xk 1 , что xk 1 ⇠ xk 2 и xk 1 ⇠ xk . Для

произвольных z1 , z2 рассмотрим количество вершин, смежных с z1 , скалярное

произведение которых с z2 равно j. Ясно, что эта величина также зависит толь-

ко от скалярного произведения (z1 , z2 ) = i; будем обозначать ее Aji (Ass = N2 ).

Заметим, что поскольку x и y соединены ребром, то количество способов вы-

брать вершину x2 , смежную с x, скалярное произведение которой с y равно i1 ,

есть в точности Ais1 . Поэтому количество путей (возможно, с повторяющимися

вершинами) запишется в виде суммы

X

Ais1 · Aii21 · . . . · Asik 3 .

i1 ,i2 ,...,ik 3

Количество простых путей оценим следующим образом:

X

Ais1 · max Aii21 1, 0 · max Aii32 2, 0 · . . . · max Asik 3

k + 1, 0 6

i1 ,i2 ,...,ik 3

X

Pk 6 Ais1 · Aii21 · . . . · Asik 3 .

i1 ,i2 ,...,ik 3

Нам потребуются следующие асимптотики для Aji :

min{j,s}

X m s m r s (j m)

Ajs = Csm Crj s Cr s Cn r (r s) ⇣

m=max{s r+max{j,s},0}

8

>

<0, если j < 2s r;

nr s , если 2s r 6 j 6 s;

>

: r s (j

n s)

, если j > s,

min{i,s}

X

m 2 r s (s m)

Asi = Cim (Crs i ) Cn r (r i) ⇣

m=max{s r+max{i,s},0}

13

 8

>

<0, если i < 2s r;

nr s (s i)

, если 2s r 6 i 6 s;

>

: r s

n , если i > s,

при i < s

min{i,j}

X m s m r s (j m)

Aji = Cim Crj i Cr i Cn r (r i) ⇣

m=max{s r+max{i,j},0}

8

>

>

> 0, если j < s + i r;

>

< nr s , если s + i r 6 j 6 i;

>

>

> nr s (j i)

, если i < j 6 i + r s;

>

:0, если j > i + r s.

Здесь и далее f (n) ⇣ g(n) означает, что существуют такие c, C > 0, что для

всех n, начиная с некоторого n0 , выполнено cg(n) 6 f (n) 6 Cg(n).

Заметим, что если какое-либо из it отлично от s, то слагаемое, задаваемое

таким набором i1 , ..., ik 3 , есть o n(r s)(k 2) , поскольку в нем будет по крайней

мере один множитель Aji = o(nr s ). Таким образом, остается одно слагаемое

порядка n(r s)(k 2) с i1 = i2 = . . . = ik 3 = s, и оценка сверху величины Pk

асимптотически с этим слагаемым совпадает. Поскольку k фиксировано, ниж-

няя оценка также асимптотически равна этому слагаемому, и лемма доказа-

на.

Обозначим Ck число простых циклов длины k.

Лемма 1.2. Если k = const, то Ck ⇠ N N1 N2k 2 /2k, n ! 1.

Доказательство. Из леммы 1.1 следует, что количество простых путей с сов-

падающими первой и последней вершинами равно

fk = N N1 Pk ⇠ N N1 N k 2 .

C 2

Для того, чтобы получить утверждение леммы, нужно поделить эту величину

на количество автоморфизмов цикла длины k, то есть на 2k.

Последовательность реберно-независимых путей {P0 , . . . , Pm } называют раз-

ложением на уши (англ. ear decomposition) графа H, если P0 есть простой цикл,

P1 , . . . , Pm представляют собой простыеSпути или простые циклы, причем V (Pj )

j 1

для

Sm всех j 2 {1, . . . , m}

Smпересекается с i=0 V (Pi ) лишь по концевым вершинам,

i=1 V (Pi ) = V (H), а i=1 E(Pi ) = E(H). Разложение называется открытым,

если P1 , . . ., Pm являются простыми путями, т.е. концевые вершины Pj для каж-

дого j 2 {1, . . . , m} различны.

14

 Теорема Уитни из [47] утверждает, что граф H с v(H) > 2 является двусвяз-

ным тогда и только тогда, когда существует его открытое разложение на уши.

Более того, в качестве P0 можно взять любой простой цикл H.

Обозначим M = MF число подграфов дистанционного графа G(n, r, s), изо-

морфных F .

Лемма 1.3. Пусть F � связный граф с k вершинами и l ребрами. Пусть F

содержит b нетривиальных компонент двусвязности и число вершин, лежа-

щих в них, равно d. Пусть h � величина, определенная перед формулировкой

теоремы 1.7. Кроме того, a � количество автоморфизмов F . Тогда

1

M ⇠ N N1k d+2b h 1

N2d 2b+h

, n ! 1.

a

Доказательство. Если F � дерево, то утверждение леммы очевидно. Далее

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

ным способом вершины графа F , т.е. составим упорядоченное множество A,

содержащее все вершины графа, и в качестве нового индекса вершины возьмем

порядковый номер вершины в A. Для этого выберем произвольную нетриви-

альную компоненту двусвязности H1 и простой цикл C в ней. Вершины этого

цикла в том же порядке добавим в множество A. Рассмотрим разложение на

уши этой компоненты {P0 , . . . , Pm } с P0 = C. Для каждого j 2 {1, . . . , m}

добавим в A неконцевые вершины соответствующего пути, сохраняя порядок.

Пройдем далее по всем вершинам vi из V (H1 ). Пусть Ci , i 2 {1, . . . , |V (H1 )|},

� связные компоненты в (V (F ) \ A) [ {vi }, содержащие vi . Если Ci = {vi },

переходим к следующей вершине. Если Ci � дерево, добавим в A вершины Ci

в порядке, соответствующем нумерации в ширину (будем называть этот поря-

док стандартным), считая vi корнем. Если же Ci содержит цикл, то ее можно

представить в виде объединения дерева Ti с корнем vi и подграфов, содержащих

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

ется с Ti лишь по одной вершине и эта вершина лежит в одной из компонент.

Обозначим эти вершины xj , j 2 {1, . . . , k1 }. Добавим в множество A вершины

дерева Ti в стандартном порядке. Для каждой вершины xj найдем проходящий

через нее цикл в компоненте, содержащей xj , и добавим вершины этого цикла в

A, начиная с вершины, смежной с xj , и сохраняя порядок. Так же, как и выше,

используя разложение на уши, дополним A остальными вершинами компонен-

ты. Для каждой вершины последней проделаем то же самое. Таким образом

получим множество A, в котором содержится каждый элемент V (F ). Далее бу-

дем обозначать vi , i 2 {1, . . . , k}, вершины графа F , подразумевая построенную

нумерацию.

Пусть Mf � число последовательностей {x1 , . . . , xk } в V (n, r), таких, что

vi ⇠ vj ) xi ⇠ xj . Нетрудно видеть, что M = M f/a.

15

 В силу связности графа F для любого простого цикла C длины t в F спра-

ведливо неравенство M f 6 Cet N k t , где Cet � количество последовательностей

1

вершин {x1 , . . . , xt }, образующих (не обязательно индуцированный) цикл в гра-

фе G(n, r, s). В лемме 2 утверждается, что

1

Cet ⇠ N N1 N2t 2

⇠ ntr (t 1)s

⇠

s!((r s)!)t

Cns Cnr ss Cnr s r s

s (r s) . . . Cn s (t 1)(r s) ,

т.е. Cet асимптотически совпадает с числом последовательностей вершин-векто-

ров в G(n, r, s) с единицами на фиксированных s местах, образующих полный

подграф. То же верно и для количества простых путей. Поэтому при подсче-

те величины M f можно считать, что нетривиальные компоненты двусвязности

должны образовывать полные подграфы в G(n, r, s), все вершины каждого из

которых имеют единицы на фиксированных s позициях. Пусть компоненты име-

ют мощности t1 , . . . , tb . Тогда, группируя множители, соответствующие верши-

нам, не лежащим в компонентах, и их дополнению, получим

f ⇠ N N1 N t1 2 N12 N t2

M 2

. . . N12 N2tb 2 N1 h N1k d

=

2 2

P

ti 2b

N N12b 1 h+k d

N2 = N N12b 1 h+k d

N2d+h 2b

.

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

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

Пусть M = MF , как и в п. 1.2.3, � количество подграфов полного дистан-

ционного графа G(n, r, s), изоморфных графу F . Из леммы 1.3 следует, что

M ⇣ nkr (k 1)s . Обозначим F = {F1 , F2 , . . . , FM } множество всех таких под-

графов. Пусть для любого i 2 {1, 2, . . . , M } Xi � случайная величина, равная

1, если Fi присутствует в Gp (n, r, s), и 0 в противном случае.P Очевидно, что

количество копий F в Gp (n, r, s) представляется в виде суммы M i=1 Xi .

Легко видеть, что

XM

EX = EXi ⇣ nkr (k 1)s pl .

i=1

Далее разделим доказательство на две части.

Часть 1. Пусть

kr (k 1)s

p⌧n l .

Тогда EX ! 0, и из неравенства Маркова следует, что

P(X > 0) ! 0 при n ! 1.

16

Часть 2. Пусть теперь

kr (k 1)s

p=!·n l ,

где ! = !(n) ! 1 при n ! 1.

Ясно, что при таком условии EX ! 1. Оценим дисперсию X, для которой

верно равенство

M

X X

DX = D Xi + 2 cov(Xi , Xj ).

i=1 16i<j6M

Заметим, что число пар подграфов из F, множества вершин которых пересе-

каются по t элементам, составляет O(N N12k t 1 ). Действительно, эта величина

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

на 2k t вершинах в G(n, r, s). Используя сбалансированность F , получим, что

если у двух подграфов совпадают u ребер, то u 6 tl/k. Поэтому дисперсия

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

M

X k

X ⇣ tl

⌘

DX 6 EXi + O N N12k t 1 p2l k 6

i=1 t=2

k

X ⇣ tl

⌘

EX + n 2k(r s)+s 2l

p O n t(r s)

p k 6

t=2

k

X ⇣ ⌘

2 s( 1 t

)! tl

EX + (EX) O n k k = o (EX)2 .

t=2

Отсюда с помощью неравенства Чебышева получаем

DX

P(X = 0) = P( X > 0) 6 P(|EX X| > EX) 6 ! 0 при n ! 1.

(EX)2

Применим это же неравенство для доказательства закона больших чисел при

kr (k 1)s

p n l .

Для любого " > 0

✓ ◆

X DX

P 1 <" >1 P(|X EX| > "EX) > 1 ! 1.

EX "2 (EX)2

Таким образом, теорема полностью доказана.

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

Выпишем асимптотическое выражение для M :

17

 1

M ⇠ N N12b 1 h+k d

N2d+h 2b

⇠

a

✓ ◆2b 1 h+k d ✓ ◆d+h 2b

1 nr nr s

nr s

Crs ⇠

a r! (r s)! (r s)!

(Crs )k d+2b h 1

nkr (k 1)s

.

ar!((r s)!)k 1

Отсюда

M

X

EX = EXi = M pl ⇠ M1 cl = ,

i=1

где

(Crs )k d+2b h 1

M1 = .

ar!((r s)!)k 1

В силу теоремы 1.20 из [16] достаточно доказать сходимость факториальных

моментов

EX j = EX(X 1) . . . (X j + 1)

к j при n ! 1 для всех фиксированных натуральных j. Из этого будет сле-

довать утверждение теоремы.

Ясно, что EX j есть математическое ожидание числа упорядоченных набо-

ров копий графа F . Покажем, что эта величина асимптотически совпадает с

математическим ожиданием Yj � количества упорядоченных наборов копий F

с непересекающимися множествами вершин. Заметим, что

M M kN1k 1

... M (j 1)kN1k 1

pjl 6

EYj 6 M (M 1) . . . (M j + 1)pjl , (1.2)

откуда следует, что

EYj ⇠ M j pjl ⇠ j

.

Остается доказать, что EZj = o(1) при n ! 1, где Zj = X j Yj .

Напомним, что e(H) � количество ребер в графе H. Сначала отметим, что

для двух различных графов A и B, таких что B изоморфен F и в точности t

вершин графа B не принадлежат V (A), в силу сбалансированности F , eB (A \

B) 6 (k t)l/k (где eB (A \ B) � число ребер из B в индуцированном подграфе

B с множеством вершин V (A) \ V (B)), из чего следует, что

tl

e(A [ B) > e(A) + , если t > 0;

k (1.3)

e(A [ B) > e(A) + 1, если t = 0.

S

Пусть F1 , . . . , Fj � подграфы G(n, r, s), изоморфные F , с ji=1 V (Fi ) = t <

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

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

[1] P. Frankl and R. Wilson. Intersection theorems with geometric consequences.

Combinatorica, 1:357–368, 1981.

[2] J. Kahn and G. Kalai. A counterexample to borsuk’s conjecture. Bulletin (new

series) of the AMS, 29(1):60–62, 1993.

[3] P. Brass, W. O. J. Moser, and J. Pach. Research problems in discrete geometry.

Springer, 2005.

[4] А. М. Райгородский. Проблема Борсука для (0,1)-многогранников и кросс-

политопов. ДАН, 371:600–603, 2000.

[5] А. М. Райгородский. Проблема Борсука и хроматические числа некоторых

метрических пространств. УМН, 56(1):107–146, 2001.

[6] А. М. Райгородский. Проблема Борсука для целочисленных многогранни-

ков. Матем. сборник, 193(10):139–160, 2002.

[7] А. М. Райгородский. Проблема Эрдеша–Хадвигера и хроматические числа

конечных геометрических графов. Матем. сборник, 196(1):123–156, 2005.

[8] А. М. Райгородский. Проблемы Борсука и Грюнбаума для решетчатых

многогранников. Известия РАН. Серия математическая, 69(3):81–108,

2005.

[9] А. М. Райгородский. Линейно-алгебраический метод в комбинаторике.

МЦНМО, М., 2007.

[10] A. M. Raigorodskii. Three lectures on the borsuk partition problem. In Surveys

in Contemporary Mathematics, pages 202–247. Cambridge University Press,

Cambridge, 2007.

[11] A. M. Raigorodskii. Around borsuk’s conjecture. J. of Math. Sci., 154(4):604–

623, 2008.

[12] A. M. Raigorodskii. Coloring distance graphs and graphs of diameters. In Thirty

essays on geometric graph theory, pages 429–460. Springer, Berlin, 2013.

[13] A. M. Raigorodskii. On the chromatic numbers of spheres in Rn . Combinatorica,

32(1):111–123, 2012.

[14] P. Erdős and A. Rényi. On random graphs. I. Publ. Math. Debrecen, 6:290–297,

1959.

[15] P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad.

Mat. Kutató Int. Közl., 5:17–61, 1960.

68

[16] B. Bollobás. Random graphs, volume 73 of Cambridge Studies in Advanced

Mathematics. Cambridge University Press, Cambridge, second edition, 2001.

[17] S. Janson, T. Luczak, and A. Rucinski. Random graphs. Wiley-Interscience

Series in Discrete Mathematics and Optimization. Wiley-Interscience, New

York, 2000.

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

[19] В. Ф. Колчин. Случайные графы. Теория вероятностей и математическая

статистика. Физматлит, М., 2000.

[20] P. Erdős and A. Rényi. On the evolution of random graphs. Bull Inst. Int.

Statist. Tokyo, 38:343–347, 1961.

[21] K. Schürger. On the evolution of random graphs over expanding square lattices.

Acta Mathematica Academiae Scientiarum Hungarica, 27(3-4):281–292, 1976.

[22] B. Bollobás. Threshold functions for small subgraphs. Math. Proc. Cambridge

Philos. Soc., 90(2):197–206, 1981.

[23] Z. Palka. On the number of vertices of given degree in a random graph. Journal

of graph theory, 8(1):167–170, 1984.

[24] A. D. Barbour. Poisson convergence and random graphs. In Mathematical

Proceedings of the Cambridge Philosophical Society, volume 92, pages 349–359.

Cambridge University Press, 1982.

[25] B. Bollobás. The evolution of random graphs. Transactions of the American

Mathematical Society, 286(1):257–274, 1984.

[26] T. Luczak and J. C. Wierman. The chromatic number of random graphs at the

double-jump threshold. Combinatorica, 9(1):39–49, 1989.

[27] T. Luczak. Component behavior near the critical point of the random graph

process. Random Structures and Algorithms, 1(3):287–310, 1990.

[28] S. Janson, D. E. Knuth, T. Luczak, and B. Pittel. The birth of the giant

component. Random Structures and Algorithms, 4(3):233–358, 1993.

[29] T. Luczak, B. Pittel, and J. C. Wierman. The structure of a random graph at

the point of the phase transition. Trans. Amer. Math. Soc., 341(2):721–748,

1994.

[30] E. N. Gilbert. Random graphs. The Annals of Mathematical Statistics,

30(4):1141–1144, 1959.

69

[31] T. L. Austin, R. E. Fagen, W. F. Penney, and J. Riordan. The number of

components in random linear graphs. The Annals of Mathematical Statistics,

30(3):747–754, 1959.

[32] P. Erdős and A. Rényi. On the strength of connectedness of a random graph.

Acta Mathematica Hungarica, 12(1-2):261–267, 1961.

[33] B. Bollobás. Degree sequences of random graphs. Discrete Mathematics,

33(1):1–19, 1981.

[34] V. E. Stepanov. Combinatorial algebra and random graphs. Theory of

Probability and Its Applications, 14(3):373–399, 1969.

[35] V. E. Stepanov. Phase transitions in random graphs. Theory of Probability and

Its Applications, 15(2):187–203, 1970.

[36] V. E. Stepanov. On the probability of connectedness of a random graph g_m(t).

Theory of Probability and Its Applications, 15(1):55–67, 1970.

[37] I. N. Kovalenko. Theory of random graphs. Cybernetics, 7(4):575–579, 1971.

[38] G. I. Ivchenko. The strength of connectivity of a random graph. Theory of

Probability & Its Applications, 18(2):396–403, 1974.

[39] М. Е. Жуковский. О вероятности вхождения копии фиксированного графа

в случайный дистанционный граф. Матем. заметки, 92(6):844–855, 2012.

[40] J. Spencer. Threshold functions for extension statements. J. Combin. Theory

Ser. A, 53(2):286–305, 1990.

[41] А. В. Буркин. Малые подграфы в случайных дистанционных графах. Тео-

рия вероятн. и ее примен., 60(3):439–458, 2015.

[42] А. В. Буркин. О пороговой вероятности для свойства планарности случай-

ного подграфа регулярного графа. УМН, 70(6(426)):205–206, 2015.

[43] А. В. Буркин и М. Е. Жуковский. Малые подграфы и их расширения в

случайном дистанционном графе. Матем. сборник, 209(2):22–46, 2018.

[44] А. В. Буркин. Малые подграфы и расширения в семействе случайных под-

графов плотных дистанционных графов. Труды МФТИ, 11(1):5–19, 2019.

[45] A. Ruciński and A. Vince. Balanced graphs and the problem of subgraphs

of random graphs. In Proceedings of the sixteenth Southeastern international

conference on combinatorics, graph theory and computing, volume 49, pages

181–190, 1985.

[46] Ф. Харари. Теория графов. Эдиториал УРСС, М., 2003.

70

[47] H. Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc.,

34(2):339–362, 1932.

[48] A. Frieze and M. Krivelevich. On the non-planarity of a random subgraph.

Combin. Probab. Comput., 22(5):722–732, 2013.

[49] А. Р. Ярмухаметов. О связности случайных дистанционных графов специ-

ального вида. Чебышевский сб., 10(1):95–108, 2009.

[50] Н. Алон и Дж. Спенсер. Вероятностный метод. БИНОМ, М., 2007.

[51] R. M. Karp. The transitive closure of a random digraph. Random Structures

and Algorithms, 1(1):73–93, 1990.

[52] М. Е. Жуковский. Ослабленный закон нуля или единицы для последова-

тельностей случайных дистанционных графов. Матем. сборник, 203(7):95–

128, 2012.

71