Настоящая работа посвящена исследованию некоторых свойств случайных графов. Существует множество различных моделей таких графов, наиболее распространенная из них — классическая модель Эрдеша-Реньи, в которой граф G(n,p) на n вершинах строится следующим образом: все ребра проводятся независимо друг от друга с вероятностью p Е (0,1). Изучению свойств таких графов посвящено большое количество работ (см., например, [1, 2, 3]).

Однако в последнее время появилась потребность моделировать различные реальные структуры, свойства которых существенно отличаются от свойств случайных графов в модели Эрдеша–Реньи. Особенно важно создать модель, наиболее точно представляющую Интернет. Пусть вершинами графа будут сайты или страницы Интернета, а ребрами — гиперссылки между ними. Получим некоторый граф. Хочется иметь модель, отражающую основные его свойства. Например, в отличие от G(n,p), граф, представляющий Интернет, обладает степенным распределением степеней вершин. Именно это свойство положено в основу различных моделей случайных графов. Некоторые из них изначально обладают нужным распределением, для других это свойство доказывается. Обзор различных моделей и основных результатов можно найти в работе [4].

Наиболее распространенная модель Интернета была впервые описана Барабаши и Альберт (см. [5]), а позже уточнена Боллобашем и Риорданом. Определенную ими модель мы и будем рассматривать в настоящей работе. Опишем, как строится граф в этой модели. Обычно для него используется обозначение G ⁿ _m , где n — число вершин, m — фиксированный параметр. Сперва по индукции строится G ₁ ⁿ . Граф G ¹ ₁ состоит из одной вершины и одной петли. Граф G ^t ₁ получается из G ^t ₁ ^{- 1} посредством добавления вершины t и одного ребра между вершинами t и i, где i выбирается случайно следующим образом:

P(i = s) =

f <^- 1 (s)/(2t — 1),

I1/(2t - 1),

если 1 ^ s ^ t — 1, если s = t.

Настоящая работа выполнена при финансовой поддержке гранта РФФИ № 12-01-00683 и гранта Президента РФ № MD-666.2012.1.

Здесь d _G t (s) - степень вершины s в графе G ^ . Иными словами, чем больше степень вершины в графе G t ^{- 1} , тем больше вероятность того, что следующая вершина будет соединена с ней. Поэтому такие графы еще называют «графами предпочтительного присоединения». Граф G m (m > 1) строится на основе G mn . Первые m вершин G mn составляют первую вершину нового графа, следующие m — вторую, и так далее. Ребра в некотором смысле сохраняются, а именно: если в G mn ребро соединяло вершины i и j, то в полученном графе G ⁿ _m это ребро соединяет те группы вершин, в которые попали i и j . Тем самым в графе могут возникнуть кратные ребра и кратные петли. Построенные таким образом графы G ⁿ _m образуют вероятностное пространство G ⁿ _m .

Итак, в основу построения графа G ⁿ _m положен принцип предпочтительного присоединения. Это вполне соответствует цели получить модель Интернета, ведь вновь появившийся сайт скорее предпочтет сослаться на ту страницу, которая уже «популярна». Тот факт, что граф G ⁿ _m обладает степенным распределением степеней вершин, был доказан Болло-башем и Риорданом в работе [6]. Кроме того, в статье [7] они показали, что диаметр G ⁿ _m при m ^ 2 асимптотически равен ‘ nnn . Точная формулировка этого результата будет дана в следующем разделе. В настоящей работе будет дано обобщение понятия диаметра графа и доказан соответствующий результат.

В разделе 2 будут введены основные понятия и сформулированы теоремы, которые будут доказаны в разделах 3 и 4.

2.    Введение обозначений и формулировка результата

Пусть имеется некоторый граф G = (V, E). Его диаметром называется следующая величина:

diam(G) = max p(i,j), i,jev i=j где p(i,j) — длина кратчайшего пути между вершинами i и j в графе G.

Введем некоторое обобщение понятия диаметра — r -диаметр:

diam r (G) =

Р(М).

max min A c V i,j e A ^|A| =r

Иными словами, теперь мы рассматриваем не пары вершин, а подмножества мощности r. В каждом таком подмножестве мы находим две вершины на наименьшем расстоянии друг от друга. И нас интересует максимум этого расстояния по всем подмножествам. Заметим, что при r = 2 имеем в точности обычный диаметр графа G. В этой работе всегда будем полагать, что r ^ 2, чтобы понятие r-диаметра имело смысл.

В работе [7] Боллобаш и Риордан доказали следующую теорему.

Теорема 1. Для любого е >  0 и любого натурального m ^ 2

lim P f (1 - е )      <  diam(G n ) <  (1 + е ) rly n-) = 1.

n >^ v lnln n           ^m          lnln n/

В настоящей работе будет доказано подобное утверждение для r-диаметра. А именно

Теорема 2. Пусть е > 0 и натуральное m ^ 2 фиксированы. Далее, пусть r(n) — произвольная последовательность целых чисел, лежащих в пределах от 2 до п. Тогда lim P (       ; n < diamr(Gn) < (1 + ")‘n n - ‘n r) = 1.

n ^^  \       lnln n                  m           lnln n у

Как и ожидалось, чем больше вершин в рассматриваемых множествах, тем меньше r-диаметр. Отметим, что если для любого а >  0 выполнено r(n) = o (n ^a ), т.е. r(n) = n ^{o (1)} , то результаты теорем 1 и 2, по существу, идентичны. Если же, например, r(n) = n ^a , а >  0, то константа в асимптотике из теоремы 2 принципиально другая: 1 ± е превращается в 1 — а ± е . Если, наконец, r(n) = n ^{1 -o (1)} , то асимптотики в теореме 2 нет.

Доказательство теоремы 2 естественно разбивается на два шага — оценка снизу и оценка сверху. Нижняя оценка будет доказана в разделе 3, верхняя — в разделе 4. При этом мы существенно будем опираться на работу [7], особенно в разделе 4.

3.    Оценка снизу 3.1.    Формулировка результата и вспомогательных лемм

Будем говорить, что событие происходит с асимптотической вероятностью 1, если его вероятность стремится к 1 при n ^ то .

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

Теорема 3. Пусть m ^ 1 фиксировано, тогда diam r (G m ) ^ i lnn—Jnr ) — 1 с асимптотической вероятностью 1.

Ясно, что требуемая оценка сразу следует из этой теоремы.

Разобьем r(n) на две подпоследовательности. В одной из них r(n) ^ р^-—, в другой r(n) <  ү^-- . Заметим, что для первой подпоследовательности оценка снизу тривиальна — для достаточно больших n там просто стоит отрицательное число. Поэтому далее считаем, n что r <  _{ln n} .

Для доказательства нам потребуется несколько вспомогательных лемм. Во-первых, нас будет интересовать вероятность того, что граф G n содержит некоторый подграф S . Под событием { S С G n } понимаем, что граф G^rn содержит в точности граф S , а не изоморфный ему подграф. Иными словами, если в S проведено ребро ij, то в G^T n должно быть ребро между вершинами с теми же номерами. В работе [7] доказано следующее утверждение.

Лемма 1. Пусть S = (V, E) — некоторый граф с множеством вершин V = {1,..., n}, у которого нет петель и каждая вершина соединена не более чем с одной из вершин с меньшими номерами. Пусть далее e(S) = |E|, а A(S) — максимальная степень вершины в графе S . Тогда

1 ^√ ij ^.

P(S С G n ) <  2 ^{e ( S )(A( S )+2)} Ц ij G E(S)

Далее нам понадобится следующая конструкция. Пусть ( ij (i < j , 1 <  i,j <  n) — индикаторные случайные величины на каком-то вероятностном пространстве, то есть с некоторой вероятностью p ij E [0,1] величина ( ij принимает значение 1, а с вероятностью 1 — p ij принимает значение 0. Про зависимость между ( ij ничего не говорится. Пусть, кроме того, Q n — множество всех графов на вершинах 1,...,n без петель и кратных ребер, F _n = 2 ^Q n — стандартная сигма-алгебра, состоящая из всех подмножеств Q n , а вероятностная мера задается следующим образом: для любого G = (V, E) E Q n

P , (G) = P( {V ij E E (G) : ( ij = 1 }n{V ij / E (G) : ( ij = 0 } ).

Рассмотрим теперь вероятностное пространство G (n,( j ) = (Q _n , F _n , P n^ j ). Для таким образом определенного случайного графа будет доказана следующая лемма.

Лемма 2. Пусть r <  _ln ⁿ_n . Пусть, кроме того, для индикаторных случайных величин ^ ij (i < j, 1 C i,j C n) выполнено: P(£ j = 1) = O (-p— ) • Тогда с асимптотической вероятностью 1 в графе G Е G ([n/2"],£_{> i}j ) есть независимое множество размера хотя бы r.

В последующих двух параграфах этого раздела будет сначала доказана лемма 2, а затем непосредственно оценка снизу.

• 3.2.    Доказательство леммы 2

Заметим, что количество ребер в графе G с асимптотической вероятностью 1 не пре- n ²

восходит _{10 r} :

p ⁽ е ₍ g )| >  nL ) с M EG = ^{10 r}Cp^{o (1)} = o₍1).

10 r           n ²               n ² r

Доказательство леммы проведем методом от противного. Допустим, что в любом подграфе G на r вершинах проведено хотя бы одно ребро. Пусть A 1 — независимое множество в графе G максимального размера. Тогда | A 1 | < r и, кроме того, из любой вершины V(G) \ A 1 ведет ребро в хотя бы одну вершину A 1 (иначе A 1 не максимальное). Далее, пусть A 2 — максимальное независимое множество в подграфе на вершинах V(G) \ A 1 . Тогда | A ₂ | < r и из любой вершины V(G) \ A 1 \ A 2 ведет ребро хотя бы в одну вершину A 2 . Аналогичную операцию будем проводить до тех пор, пока не кончатся вершины графа G. В итоге придем к последовательности множеств A 1 , A 2 , . . . , A l . Теперь можем оценить количество ребер снизу:

^{| E(G) |} ^ ^{([n/2] — | A}1D + ^{([n/2] — |} A 1 ^{| — |} A 2 ^{| )} + ... + ^{([n/2] —} | A i | ^— ... ^{— | A}iD —

= l ^[n^{/2] -} l ^{| A} 1 | ^{- (}l ^{- 1) | A} 2 ^{| —} ... ^{— | A} lb

Легко заметить, что если при фиксированной сумме | A 1 | + ... + | A / | — [n/2] мы хотим минимизировать полученное выражение, мы должны взять максимально возможным | A ₁ | , затем | A 2 | , и так далее, сколько получится. В итоге получим

IE (G) | >  ([n/2] — r) + ([n/2] — 2r) + ... + ([n/2] — [ 2 - ] r) — [n/2] [ 2 - ] — 2 [ 2 - ] ([ 2 - ] + 1 ) = 222

= ^ (1 + o(1)) — n: (1 + o(1)) = n: (1 + o(1)).

Получили, что с одной стороны, |E(G)| C 10"^ с асимптотической вероятностью 1, а с 2r другой стороны, |E(G)| ^ 8-(1 + о(1)). Таким образом, предположение неверно. Лемма доказана.

Заметим, что проведенное выше рассуждение — это один из способов доказательства известной теоремы Турана в экстремальной теории графов (см. [8]). Мы воспроизвели его прежде всего ради большей замкнутости работы.

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

Положим L = , ^ln n —гт ^-т — 1 . Рассмотрим множество вершин A = {T n/2 1 +1,...,n } ln(17 m ² ln n )

графа G m . Заметим, что | A | = [n/2]. Докажем, что для любых вершин i,j Е A

^p(p(i,j) ^с L) = о (-A-n) .

Рассмотрим две вершины i, j ∈ A. Оценим вероятность того, что между этими двумя вершинами найдется путь длины 1 С l С L. Пусть путь между этими вершинами в Gm следующий: Vo = i, v1, v2,..., Vi-1, vi = j. Рассмотрим какой-нибудь граф Gmn, из которого получен граф Gnm с нужным свойством. Тот факт, что в графе Gnm соединены вершины vt

= v t ^и |"wm 1""| = v t+1 . ^ПР^и

^u m ^t

и vt+1, обозначает то, что в G1mn есть ребро utwt+1 , причем данных u0, . . . , ul и w1 , . . . , wl+1 вероятность того, что в графе Gnm проведены ребра ut wt+1

(0 С t С l — 1), по лемме 1 не превосходит l-1                       l-1

l - 1

t=1

2 4l ТТ          <  2 4l ТТ = 2 4l 4

_{t =0} ^u t ^w t+1        _{t =0} ^v t ^v t+1          i

Посмотрим, сколько всего есть графов, из которых получается Gnm с данным конкретным путем длины l. Каждое ребро между vt и vt+1 может быть получено m2 способами: m возможностей выбрать вершину ut и m возможностей выбрать вершину wt+1. Ребер всего l, в итоге получаем m2l графов. Итак, вероятность содержать конкретный путь длины l не превосходит l-1

(^lU t=1

Суммируем по всем возможным v 1 , ..., v l - 1 , получаем, что вероятность того, что вершины i и j соединены путем длины l, не превосходит (для достаточно больших n)

(4 m ) ^{2 l √} ij

l - 1

Е П v t

1 ^ V 1 ,...,V l- 1 ^ n t=1

2(4 m ) ^{2 l}

< -n-

( 1⁺ 2 ⁺...⁺ 1 )    ^С

2(17 m ² ) (ln n ) ^{l- 1} n

В первом неравенстве воспользовались тем, что мы рассматриваем вершины с номерами, большими n/2. Просуммируем по всем l ^ L:

2 n ln n

L

E^ (17m2 In n)l l=1

<

2(17 m ² ln n ) ^{L +1} n ln n

<

2(17 m ² ln n )

ln n - ln r ln(17m² ln n)

n ln n

=o( L r ln n

Что и требовалось.

Итак, для любых двух вершин из A вероятность того, что они соединены путем длины r l1n n . Обратимся

не более L, равна O

теперь к лемме 2. Рассмотрим граф G на множе- стве вершин A. Проведем ребро между двумя вершинами в графе G, если эти вершины соединены путем длины не больше L в Gnm. Из леммы 2 следует, что с асимптотической вероятностью 1 в множестве A найдется независимое подмножество размера г. Иными словами, найдутся такие r вершин в графе Gnm , что расстояние между любыми двумя из них больше L. Теорема доказана.

4.    Оценка сверху 4.1.    Формулировка результата и описание модели

Справедлива

(1 + ε ) ln n - ln r

Теорема 4. Пусть 6 > 0, тогда diamr (Gm) С ----j-j------ с асимптотической веро ятностью 1.

При доказательстве теоремы 4 мы будем использовать другое, эквивалентное определение модели G ⁿ _m — хордовую диаграмму, которая была описана в работе [7]. Для большей замкнутости данной работы мы приводим здесь полное описание этой модели.

Положим N = mn. Рассмотрим числа от 1 до 2N и разобьем их на пары. Как нетрудно видеть, всего таких разбиений (2N)!/(N!2 ^N ). Теперь выберем одно из разбиений случайным образом (вероятность выбрать каждое равна N !2 N /(2N)!). Представим, что точки от 1 до 2 N расположены на прямой, и соединим хордами пары точек, на которые мы разбили наше множество. Получили N хорд. Сформируем граф. Из всех правых концов хорд выберем один с наименьшим номером. Пусть это число r 1 . Тогда объединим точки 1,..., r 1 в первую вершину. Далее, точки r 1 + 1,..., r ₂ , где r ₂ — следующий правый конец, образуют вторую вершину. И так далее. Получим N вершин. А каждой хорде соответствует ребро. Ребро соединяет вершины i и j (i ^ j ), если имеется хорда между r и одной из точек r i - 1 + 1,..., r i — 1 (считаем r ₀ = 0).

Покажем, что такое определение графа эквивалентно обычному определению G ₁ ^N . Будем рассматривать правые концы хорд слева направо. Рассмотрим первый правый конец. Из этой точки идет одна хорда, и она соответствует петле в первой вершине. Далее, пусть каким-либо образом проведены хорды из правых концов r 1 ,...,r i . Рассмотрим i + 1-й правый конец. Вероятность того, что из вершины i + 1 ведет ребро в вершину t, пропорциональна количеству отрезков, на которые в данный момент разбит отрезок [r _{t- 1} ,r _t ], ведь ровно столько есть соответствующих разбиений на пары. А количество отрезков, как нетрудно видеть, это степень вершины t в данный момент. Итак, получили ровно то же построение модели.

Преобразуем полученное определение в еще одно эквивалентное. Возьмем отрезок [0 , 1] и случайные величины x ₁ , x ₂ , . . . , x _{2 N} — независимые и равномерно распределенные на этом отрезке. Пары теперь — это вершины x 2i - 1 и x 2i . Каждый порядок расположения точек равновероятен. При этом одному и тому же паросочетанию соответствует ровно 2 ^N различных взаимных расположений точек. Таким образом, все паросочетания равновероятны. Положим L i = min { x _{2 i- 1} , x _{2 i} } , R i = max { x _{2 i- 1} , x _{2 i} } . Тот же результат получим, если рассмотрим случайные величины R _i — независимые с плотностью 2 x на отрезке [0 , 1] каждая. И при фиксированных R i возьмем L i равномерно распределенными на [0, R i ]. Аналогично тому, как делали это ранее, соединяем хордами L i с соответствующими R i . Считаем, что в графе проведено ребро ij (i ^ j ), если в полученной диаграмме проведена хорда, соединяющая R _i и L _i , где L _i лежит между R j _{- 1} и R j (полагаем R ₀ = 0). С этим определением и будем работать далее.

Граф G m получаем из G N обычным образом. Положим W i = R _mi — нас интересуют именно эти правые концы, когда мы рассматриваем G m . И пусть w i = W i — W i - 1 (считаем W 0 = 0).

Пусть a — наименьшее целое число, для которого s = 2 a > ln ⁷ n, b — наибольшее целое число, для которого 2 b < 2n/3. Положим I t = [2 t + 1, 2 ^{t +1} ] для a ^ t < b. Нам потребуется следующая лемма (см. [7]):

Лемма 3. Фиксируем m ^ 2. Введем несколько событий:

Ei = I W — Ji" <  i1 \Д, ¹ i V n 10 V n ’

E2 = ^It содержит хотя бы 2t-1 вершин i для всех s ^ i ^ n} ,

с Wi ^   1=, для всех a < t < b> , i    ioVin,                      )

Е з = {w i >  ln nn , для

всех i < n ^{1 / 5} ,

E 4 = {w i C n 4 / 5, для всех i >  і n }•

Тогда вероятность каждого из этих событий стремится к 1 при n → ∞ .

Далее будем считать, что правые концы R ₁ , . . . , R _N фиксированы. Величины L _i независимы и равномерно распределены на [0, R _i ]. Но мы для простоты будем полагать, что L m( _{i- 1})+j (1 C i C n, 1 C j C m) равномерно распределены на [0, W i ]. Такое допущение просто увеличит вероятность петли в каждой из вершин и, следовательно, не уменьшит r-диаметр. Теперь заметим, что можно рассматривать только m = 2. Случай m > 2 сводится к этому удалением лишних ребер, что только увеличивает r-диаметр.

Итак, определили случайный граф G, с которым будем работать. Везде далее W ₁ , . . . ,

Wn фиксированы и выполняются события E1 , . . . , E4. Из каждой вершины i в вершины с меньшими номерами идет два независимых ребра — в вершины li,1 и li,2 (поскольку m = 2), причем P(lij = k) = WW для k C i.

В последующих двух параграфах мы сперва докажем некоторую техническую лемму, а затем и саму теорему 4.

4.2. Техническая лемма

Лемма 4. Пусть е >  0, r >  ln ¹⁰ n, K = 1 (1 + ^£ .) ln n —ln r 2      ln ln n

-

1 . Далее, пусть f ₀ , f ₁ , . . .

последовательность действительных чисел с f ₀ >  (ln ² n) /n и

min{2 log ₂ ( f k n/ ln n ) - 31 ,b

- a - 1} f k

f ^{k +}1 >                 1000

для всех k >  0. Тогда при достаточно большом n величина l = min { k : f _k >  4ln u/Vrn} существует и не превосходит K .

Доказательство. Заметим, что b - a - 1 и 2 log2(f0n/ ln n) - 31 — растущие с ростом n функции. Значит, при достаточно большом n выполняется неравенство min{2 log2(f0n/ lnn) - 31, b - a - 1} 1000

> 2.

В таком случае fi > 2fo. Далее, очевидно, fk+1 > 2fk (ведь fk > fo). В итоге fk > 2kf0 и I существует.

Поскольку b — a — 1 ^ log2 n — 8log2 ln n для достаточно больших n, то неравенство 2log2(fkn/ lnn) — 31 > b — a — 1 выполняется лишь при fk > ^і 3 1^ ^n. Последнее выражение больше, чем требуемое нам 4 ln n/ r n, при достаточно больших n. Из этого следует, что для k < l минимум равен первому члену. Таким образом, при достаточно больших n fk+1 ^

log ₂ ( f k n/ ln n ) 500

-

¹⁶ f k >

log ₂ (2 ^k f 0 n/ ln n ) - 16      log ₂ (2 ^k ln ² n/ ln n ) - 16

500          ^{f k} ^           500          ^{f k}

k + log ₂ ln n -500

^l 50 ^- 0 e ^{1       f} 0 ^.

16 _

-f k >  f k (k + 1)/500.

Отсюда f > (£—22! f > l-1     500l-1 0

Поскольку f l - 1 C 4ln n/Vrn, то

/ 1 — 1 y^{- 1}     4 yn

£500eJ    ^C 7 T ln n •

Отсюда при больших n имеем

(l — 1) ln (l — 1) — (l — 1) ln 500e C ln 4 + ln V n — ln V r — ln ln n.

1 + ε/ 2 - log _n r ln n

Докажем, что с некоторого n имеем l — 1 C ------2------inInn' Если величина l огра ничена с ростом n, то все очевидно. Иначе предположим противное: для бесконечной 1 + ε/2 - logn r lnn последовательности значений n выполнено l — 1 > ------=------;—= . Тогда (по той же

2 ln ln n последовательности значений n, начиная с некоторого момента)

(l — 1) ln (l — 1) — (l — 1) ln500e — ln4 = (l — 1) ln(l — 1)(1 + o(1)) >

• > 1 + e/ 2 ^— log n r inn Л 1 + e/ 2 ^— log n r ₊lnln n — _lnlnln A ^ + 0(1)) =

2 ln ln n              2

= 1 + e/22 log n r ln n (1 + 0(1)) = ^ (1 + е/ 2) ln V n — ln V r ) (1 + o(1)) > ln V n — ln V r — ln ln n.

1 + ε/ 2 - log _n r

Воспользовались тем, что ln------2------ = o(lnln n), поскольку 0 C logn r C 1. Итак, мы пришли к противоречию, а значит, при достаточно больших n имеем l-

1 C

1 + e/2 — log n r in n = 1 (1 + e/ 2)ln n — in r

2 ln ln n 2 ln ln n

— 1.

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

• 4.3. Доказательство теоремы 4

Наконец, можем приступить к доказательству оценки сверху. Опять разобьем r(n) на две подпоследовательности. В одной из них r(n) < ln ¹⁰ n, в другой r(n) ^ ln ¹⁰ n. Заметим, что в первом случае ln r = o(ln n) и нам фактически нужно доказать, что для любого (1 + ε ) ln n

Е >  0 выполнено diam r (G m ) C —р^  с асимптотической вероятностью 1. Но в работе [7] показано, что путь требуемой длины существует между любыми двумя вершинами графа. Поэтому далее можем считать, что r(n) ^ ln ¹⁰ n.

Назовем вершину i полезной, если i C n/ ln ⁵ n и w i ^ (ln ² n) /n. Воспользуемся леммой из работы [7].

Лемма 5. Вероятность того, что каждая вершина v графа G соединена путем длины не более 8lnln n с какой-нибудь полезной вершиной, равна 1 — o(1) при n ^ то .

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

Лемма 6. Рассматриваем граф G, определенный выше. Число е > 0 — фиксировано. Возь мем некоторую полезную вершину v. Тогда с вероятностью 1 — o(n 1) существует путь

₁ (1 + ε ) ln n -ln r длины не более

2      ln ln n

между этой вершиной и одной из вершин 1,..., r — 1.

Доказательство. Нас будет интересовать то, как растет количество вершин, до которых можно добраться от данной вершины не более чем за k шагов с ростом k. Из каждой вершины i в вершины с меньшими номерами идет два ребра — в вершины l i,1 и l i,2 . В процессе доказательства эти ребра будем рассматривать отдельно. Назовем вершину i хорошей , если w i ^ —1= . Определим множества Г ₀ , Г 1 ,... следующим образом. Положим Г ₀ = { v } . 10 in

Далее, пусть для k ^ 1 множество Гк состоит из таких вершин j £ [s+1, 2ь]\(ГоU... иГк-1), что j — хорошая и либо lj,2 ∈ Γk-1, либо найдется такая вершина i ∈ Γk-1, что li,1 = j . Положим также Nk = Γ0 ∪ . . . ∪ Γk .

Будем рассматривать поведение следующей величины:

Поскольку для всех к >  1 множество Г к состоит только из хороших вершин, вес Г к (то есть i ∈ Γ k w i ) не меньше f k /10. Чтобы это выполнялось и для Γ 0 , положим f 0 = ln ² n /n.

Назовем интервал I t полным на шаге к + 1, если | N _{k +1} П I t | >  2 t - 2 .

Воспользуемся результатом Боллобаша и Риордана (см. [7]).

Лемма 7. Пусть Γ0, . . . , Γk фиксированы, тогда с вероятностью 1 - O(n-6/5) либо какой-то из It полный на шаге k + 1, либо min{2 log2(fkn/ ln n) - 31,b - a - 1} fk+1 >                 1000                fk•

Итак, Γ0 = {v}. Строим множества Γ1 , Γ2, . . . , ΓK, где K — наименьший номер k, для которого либо /к > 4 in n/Vrn, либо fk+1 <

min{2 log ₂ ( f k n/ ln n )

- 31 , b - a - 1} f k ^.

₁ (1 + ε ) ln n - ln r

Лемма 4 говорит нам о том, что K ^ -т----:—:-------

2 ln ln n

-

Если ни на каком шаге (до K) никакой интервал не становится полным, тогда (из леммы 7) при каждом фиксированном k с вероятностью 1 - O(n-6/5) выполняется min{2 log2(fkn/ ln n) - 31,b - a - 1}

^{/ к} +1 >                  1000                 f k •

Вероятность того, что это неравенство выполняется на каждом шаге до K , будет равна

1 - O ( n ^{- 6 / 5} ln n ) = 1 - o ( n ^{- 1} )

(поскольку K ^ in n). Следовательно, / _к >  4 in пД/rn с вероятностью 1 — o(n ^{- 1} ).

Пусть на некотором шаге 1 ^ к ^ K какой-то из интервалов I t стал полным. Тогда в множестве N k \{ v } имеем хотя бы 2 ^{t - 2} - 1 хорошую вершину, лежащую в I t . Поэтому

f i + • • • + f K >

2 t - 2 — 1 >  V2 t >  Vs >  ln ³ n ^√ 2 t +1 n    12 ^√ n    12 ^√ n    12 ^√ n ^.

Поскольку для всех k < K выполнено fk < 4 ln n/ r n, отсюда следует, что для достаточно больших n неравенство ln3 n    4 ln2 n    4 ln n

>■

12 n rn rn

f K ">

справедливо и в этом случае тоже.

Итак, для любой вершины i ∈ Γ _K имеем

P(l i,i <  r — 1 | Г_Ъ..„Г к ) = WW 1 >  10 y r ^{- 1} • 11 ^ n >  у 4і .

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

неравенств

п ( 1 ^—V^ ri ) ^ exp f- ^ V li) = exp (- f ^K 2rn ) ^ exp^{( —} 2ⁱⁿ n) =n i ∈ Γ K                            i ∈ Γ K

- 2 _.

Отсюда следует, что с вероятностью 1 — o(n 1 ) вершина v соединена путем длины не

более K + 1

< 1(1+ е ) ln n — ln r 2 In In n

с одной из вершин 1,.

., r — 1. Лемма доказана.

Итак, у нас есть r вершин. По лемме 5 с вероятностью 1 — o(1) каждая вершина G соединена путем длины не более 8 ln ln n с полезной вершиной. Если вдруг для каких-нибудь из наших вершин эти полезные вершины совпали, то доказывать нечего. Иначе есть r полезных вершин. По лемме 6 (в качестве е берем е/2) с вероятностью 1 — o(1) каждая 1(1+ e/2)ln n — ln r полезная вершина соединена путем длины не более ^-------с одной из вершин

• 1, ..., r — 1. Значит, для каких-то двух из наших r полезных вершин искомая вершина из 1,... ,r — 1 совпадет. Следовательно, с вероятностью 1 — o(1) среди любых r вершин найдутся две, расстояние между которыми не превосходит (для достаточно больших n )

  mil । ^{(1 + e/ 2)ln n}

  16 ln ln n +--:—:----

  ln ln n

  
  

  _-

  
  

  ln r <  (1 + е ) ln n — ln r ln ln n ^.

  
  

В определении графа G мы предполагали, что события E 1 , . . . , E 4 выполнены. А в нашем графе G m они происходят с асимптотической вероятностью 1. Таким образом, теорема 4 доказана.