О размере и сложности компонент связности случайного гиперграфа

1.    Введение и история задачи

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

1.1.    Определения и модели

В рамках работы мы следуем базовым понятиям теории графов (см., например [1]). Одной из классических моделей случайных графов является знаменитая биномиальная модель случайного графа G(n,p), также известной как модель Эрдеша - Реньи. В данной модели имеется множество из п вершин, а ребра между ними проводятся по схеме Бернулли: случайно и независимо друг от друга каждая пара вершин соединяется ребром с вероятностью р.

Естественным обобщением модели G(n,p) является биномиальная модель случайного к-однородного гиперграфа Н(п,к,р) Напомним, что в к-однородном гиперграфе ребрами являются к-подмиожеетва вершин, а не пары, как в графе. В модели Н(п,к,р) снова имеется п вершин. II уже каждое к-подмножество включается в качестве ребра в Н(п,к,р) независимо от других с вероятностью р. Модели G(п,p) и Н(п,к,р) — это центральные объекты изучения теории случайных графов и гиперграфов.

Нам также понадобятся понятия, связанные с компонентами связности в графах и гиперграфах. В графах они хорошо известны (см. [1]), определим в гиперграфах их естественные обобщения. Путем в гиперграфе, соединяющим вершины пин, называется такая чередующаяся последовательность вершин и ребер (vi, Ai,..., Vk-i, Ak-i, Vk ), что vi = v, Vk = п іі для любого г = 1,..., к — 1 обе вщішішы нг 11 нг+i содержатся в ребре Аг. Вершины пин называются связанными в гиперграфе, если в нем есть путь, соединяющий эти вершины. Понятие связанности, очевидно, является отношением эквивалентности (считаем, что вершина связана сама с собой), и, стало быть, вершиным гиперграфа разбиваются на классы эквивалентности — компоненты связности. Наконец, напомним понятие сложности компоненты связности. Если С — это компонента связности в к-однородном гиперграфе, имеющая t вершин и І ребер, то ее сложностью называется величина

Tk (С ) = (к — 1)І — t + 1.

Тем самым, например, в графе ( к = 2) древесная компонента имеет нулевую сложность, а унициклическая — единичную. В к-однородном гиперграфе нулевую сложность будут иметь компоненты, являющиеся гипердеревьями.

Нам также понадобятся некоторые определения из теории случайных процессов. Пусть (B_t,t > 0) — случайный процесс с непрерывными траекториями. Определим для него неотрицательный процесс с непрерывными траекториями: B'_t = B_t — min_s<_t B_s, t > 0. Заметим, что B'_t = 0 тогда и только тогда, когда процесс B_t достиг своего минимума на отрезке [0, t] в точке t. Теперь рассмотрим все такие пары чисел ( І і ,т і), для которых выполняются следующие свойства:

• 1)    ^Іі < Тг-

• 2)    B'‘_t = B'_rг = 0;

• 3)    для всех І і < т <  т выполняется неравенство B'_m >  0.

Упорядочим множество пар ( І і ,Т і), г Е N, по невозрастанию длин. Полученная последовательность называется последовательностью экскурсий процесса B_t.

Далее, для указанного выше процесса B_t определим также точечный процесс (N_t, t > 0), как считающий процесс с условием, что процесс N_t — J0 B'_sds является мартингалом. Наконец, обозначим через 6г число точек процесса N_t на от резке ( І і ,т і ).

1.2.    Известные результаты

Размеры и сложности компонент случайного графа G(п,p) достаточно хорошо изучены. Безусловно, ответ сильно зависит от того, как ведет себя функция р = р(п). Феномен фазового перехода в структуре компонент G(п,p) был открыт еще П. Эрдешем и А. Реньи [2].

Они показали, что здесь пороговым является значение 1/п. Обозначим через C j (п) j-й по величине размер компоненты случайного графа G(n,p), а через ст j (п) — еложность j-й по размеру компоненты. В данных обозначениях классические результаты из работ [2], [3], [4] и монографий [5], [6] можно суммировать следующим образом.

• 1)    Если p = о(1/п), то C₁(n) = op (lnп), а все компоненты с вероятностью, стремящейся

к 1, являются деревьями.

Если p = с/п и с — фиксироваиное число из (0,1), то

Ci(n) p               1

—--> а(с) =-----------, п ^ то.

Кроме того, с вероятностью, стремящейся к 1, компонент сложности более 1 в G(n,p) нет, а унициклические компоненты имеют общий размер Op (1) (как следствие, получаем, что оДп) = 0).

• 3)    Если p = с/п и с — фиксироваиное число из (1, +то), то

  С1(п) p

  —   -^ 3(с),

  п

  
  

С2(п) p               1

п ^ то,

■ -^ а(с) = с - ln с - 1 , где 3(с) — это единственное решение уравнения 3+е-^с = 1 на интервале (0,1). Кроме того, с вероятностью, стремящейся к 1, все компоненты, кроме самой большой, имеют сложность не более 1, а унициклические компоненты — снова общий размер Op(1) (как следствие, получаем, что С2(п) = 0).

• 4)    Если p = 1/п, то

С1(п) = Өp (п2/3).

Кроме того, максимальная сложность компонент ограничена по вероятности, а древесные компоненты в среднем занимают п - О(п^2/3) вершин.

• 5)    Если np - ln п ^ +то, то с вероятностью, стремящейся к 1, случайный граф является связным.

Перечисленные результаты многократно усиливались, исследователей интересовали точные предельные распределения перечисленных величин, а не только их асимптотическое поведение. Например, в работе В.Е. Степанова [3] была доказана асимптотическая нормальность Ci (п)

Теорема 1. (Д. Олдос, [7]). Пусти pn = 1 + ап

^1/3 для фиксированного а Е R. Пусти

(Wt, t > 0) — стандартное броуновское движение. Положим t2

Bt = Wt + at - — и введем носледователиности (^j,5j, j Е N) — носледователиности экскурсий этого процесса вместе с числами точек соответствующего точечного процесса. Тогда для любого т Е N выполнена следующая сходимости по распределению:

О" 2 3 •^Cjліщ ^(п)),j<^т^ -A ^((|7j Vdj^),j<^т).

Размеры и сложности компонент связности случайного гиперграфа Н(n,k,p') изучены заметно хуже. Первыми эволюцию случайного гиперграфа подробно исследовали Дж. Шмидт-Прузан и Э. Шамир [8], которые показали, что фазовый переход в модели Н (п, k,p) происходит при p = c/((fc - 1)(_fc-1)), г де с > 0 не зависит от п. Обозначим через C* (п), j > 1 — последовательность размеров компонент Н(n,k,p), отсортированных по убыванию. Тогда авторы в [8] показали, что

• 1)    если с < 1, то с вероятностью, стремящейся к 1, СІ^п) = О(1пп), а все компоненты имеют сложность не более 1;

• 2)    если с = 1, то C,^)(п) = Ор (п^2/3);

• 3)    если с >  1, то существует такая величина а = а(с) > 0, что с вероятностью, стремящейся к 1. C^(fc) (п) > а • п.

Тем самым снова при переходе некоторой границы максимальный размер компоненты Н(п,к,р) меняется с логарифмического порядка на линейный, а в граничном значении имеет порядок п^2/3. Однако никаких точных распределений авторами [8] не было найдено. В работе [9] была доказана асимптотическая нормальность С^Чп) в третьем случае при с >  1. Более простое доказательство этого же результата было предложено в работе Б. Боллобаша и О. Риордана [10]. Авторы [10] получили частичное обобщение теоремы 1 на случай модели Н (п, к,р), в которой было найдено предельное совместное распределение самых больших m размеров компонент в ситуации, когда мы находимся внутри фазового перехода.

Теорема 2. (Б. Боллобаш, О. Риордан, [10]). Пусть р = Л _п х , где А = А(п) удо-^(к-1)⁽к-1⁾

влетворяет соотношению (А — 1)³п ^ (к — 1)²а³ при п ^ то для фиксированного а Е R.

Пусть (W_t,t > 0) — стандартное броуновское движение. Положим

Bt = Wt + at — —, и пусть (^j, j Е N) — последовательность экскурсий этого процесса. Тогда для любого m Е N выполнена следующая сходимость по распределению:

((к — 1)^1/3п^-2/3 • Cj^k\n),j —^ (hj|, j< m).

Однако вопрос сложности компонент в работе [10] не обсуждался. Целью настоящей работы является закрытие данного пробела.

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

Основной результат настоящей работы состоит в усилении теоремы 2 и получении полного обобщения теоремы 1. Обозначим через Vj (п) сложность j-й по размеру компоненты случайного гиперграфа Н(п,к,р)

(А

Теорема 3. Пусть р

Л (^к—1)(_к-1)

где А = А(п) удовлетворяет соотношению

— 1)³п ^ (к — 1)²а³ п}ш п ^ то для фиксированного а Е R. Пустъ (W_t,t > 0) —

стандартное броуновское движение. Положим

Bt = Wt + at — —, и введем последовательность (^j,5j ,j Е N) — последовательность экскурсий этого процесса вместе с числами точек соответствующего точечного процесса. Тогда для любого m Е N выполнена следующая сходимость по распределению:

(^{((к — 1)1/3п}-^2/3 • ^Cj^kЧ^n),Vj ^(п)),^j< ^m) —^ ^((|7j|Л^),j< ^m).

В теореме 3 найдено, тем самым, не только предельное распределение сложности компонент, но и совместное распределение первых m по размеру компонент вместе с их сложностями. Перейдем к доказательству теоремы 3, которое будет разбито на несколько частей.

2.    Алгоритм BFS

Доказательство теоремы 3 следует идеям из работы [7]. В силу того, что Боллобаш и Риордан дали доказательство теоремы 2 весьма кратко, иногда просто ссылаясь на доказательство теоремы 1 из [7] без деталей, мы приведем доказательство сходимости по распределению и для размеров компонент.

В основе доказательства [7] лежит рассмотрение алгоритма BPS набора компонент связности случайного графа, который затем можно хорошо аппроксимировать случайным процессом с непрерывным временем. Для каждого момента времени t Е Z+ рассмотрим последовательность троек (U_t,Q_t,O_t) множеств вершин гиперграфа. Они преобразуются по следующему правилу.

• •    В начальный момент времени множество Uo нус то, Qo состоит из одной вершины, а Oo — из всех остальных вершин гиперграфа.

• •    Если Q_t непусто, то берем из него вершину г и рассматриваем все ребра, которые полностью лежат в Q_t UO_t и содержат г. Пусть их объединение дает множество Et+i-

• . Тогда Ut+i = Ut U {г}, Qt+i = Qt \ {г} U (Et+i П Ot), Ot+i = Ot \ Et+i.

• •    Если же Q_t пусто, то мы б ерем вершину г из O_t, Et+i определяем аналогично, после чего полагаем Ut+i = Ut U {г}, Qt+i = Et+i П Ot, Ot+i = Ot \ Et+i.

Определим также C_t как количество компонент связности, полностью лежащих внутри U_t. Суть множеств, тем самым, проста. Множество Q_t — это очередь вершин, из которых мы еще не осуществляли поиск, U_t — уже рассмотренные вершины, a O_t — еще неактивные вершины. Отметим простые свойства алгоритма BFS.

• 1)    |Ut| = t.

• 2)    |Qt | = 0 тогда и только тогда, когда мы обошли очередную компоненту связности.

• 3)    Пусть Т = Т(п) = O(n³/⁴). Тогда с вероятностью q = 1 — o(1) любая пара ребер, рассмотренная для перехода от t к t + 1 пр и t <Т пересекается лишь по вершине г. Действительно, посчитаем математическое ожидание пар ребер, которые пересекаются по еще какой-нибудь вершине. На t-м шаге оно не превосходит

п^ ^П 2^ р2(п) <  п^2к-3р²(п) = O ^—^ .

Тогда суммарное среднее число таких пар по t < Т не превосходит O(T/n) = O(n^-i/4). По неравенству Маркова 1 — q = O(n^-i/4).

• 4)    Пусть X_t = |Qt | — C_t. Тогда Xt+i — X_t = ■qt+i — 1, где qt+i — количество вершин, добавленных в очередь на шаге t.

3.    Свойства процесса Xt

Обсудим свойства процесса X_t. Обозначим через (X_t,t > 0) фильтрацию, порожденную

((Ut, Qt, Ot, Ct), t > 0). Вычислим E(^+і|ТД. Обозпачим ot = |Ot|. если Qt neny<-to ii |Ot| — 1 / 71 — t — 2 \ в противном случае. Тогда E(qt+i|ТД = ot(1 — (1 — р)( k—2 )), откуда получаем п — t — 2Х ^/2/п — t — 2Х 2\\

^E(^_t+^i|T_t⁾= °, Ң _к — 2 )+Д^р( _к — 2 ) Д =

opa—jg+y

п

(1 + O(п-1)).

ла_t+ у, —2

Положим a_t+i = ----„----• Тогда для Dt+i = Е(q_t+i — 1|E_t) имеем представление

^Dt+i = ^at+i⁽ⁿ — t — Xt — ^Ct+i + ^{O(1)) —} 1.

Также определим A_t+i = X_t+i — X_t — Dt+i- Нетрудно видеть, что A_t+i измерима относительно E+i, a E(At+i|Et) = 0.

После подстановки получаем, что

Xt+i = (1 — a   X + at+i(n — t) — 1 + At+i — aCt+i + Rt+i, где Rt+i = O(n-1). Теперь определим последовательность xt рекурсивным образом:

xt+i = (1 — at+i)xt + at+i(n — t) — 1, xo = 0.

Рассмотрим теперь X_t+₁ — x_t+₁ = (1 — a_t+₁)(X_t — x_t) + A_t+₁ — a_t+₁C_t+₁ + R_t+₁. Применяя эту формулу рекурсивно, получим явное представление для X_t — x_t:

^t Q

^Xt ^{— x}t = У^ TT^{(Ai — a}i^Ci ^{+ R}i),                          (1)

i=1 Q где Qt = П^і(1 — ai). Нам пригодится следующее простое утверждение.

Утверждение 1. Пусть St = ^^t=₁ ^ Ai, Xt = xt + QtSt- Toгда |Xt — Xt| = O (^).

Доказательство. Очевидно из (1), ведь ai = O(1/n), а величины Ci возрастают:

|Xt — X =

S QT ^(—ai^Ci ^{+ R}i) i=1 ^Q

"('")■

□

Положим y_t = x_t — n + t. тогда будет верно соотношение y_t+i = (1 — a_t+i)y_t. откуда y_t = —nQ_t. a x_t = n — t — Q_tn. Вычислим теперь асимптотику величины Q_t:

t                            t

In Qt = ^ ln(1 — ai) = ^ —ai — O i=1                i=1

(s') ■

= "^ Ё (1

i=1 x

-

г + 2

n

)“2 — O(t„-2)

= — I S «*"*'^{+ +O(< 1+2)2))} — O(t"-²) = ⁿ i=1

I

-

t

∑︁

n

e

(k-2)(i+) n

+o

((*?)’)

— O(tn ²) =

i=1

- 2fe-4 t

Ie ⁿ            (к-2)¹

=--2__, e n  + O(t3n 3 + tn ) = n    i=1

_ 3k — 6         _ (k — 2)t

Ie n 1 — e n

-

n

k —2

+ O(t3n-3 + tn-2) =

— e

n

I(1 + O( ^ )) ^{t —} (^--ir- ^{+ O} (6) ^{n          1 + O} ( ^ )

+ O(t3n-3 + tn-2) =

= —I (T — (^—F) +O(t³n^-3 + tn^-2). In

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

x_t = n

-

t

-

тіе

А( "

(--2)t2

2п2

) +O(t3n

3+tn-2)

.

Введем функцию g(x) = 1

-

x

-

е

А(-

2' ^ж'). Тогда при t < Cn²/³ для некоторого фик-

сированного C > 0 имеем x_t

= ng („) + 0(1). Исследуем свойства функции g(x) через ее

производные:

g'(x) = А(1 — (к — 2)x)e

А ( ж

^А)

-

1,

откуда g‘(0) = А — 1. Аналогично.

g"(x) =

-

А2

(1 — (к — 2)x)²e

А ( ж

^--2^$2) — А(к — 2)

е

А ( ж

-2) ,

то есть g‘‘(0) =

—А(к — 2) — А2

. Отсюда получаем представление вида

g(x) = (А — 1)x

-

(А(к — 2) + A2)x2/2 + O(x3).

Для перехода в непрерывное время нам остается получить оценки хвостов распределений A, и S,.

Лемма 1. При всех достаточно больших n для любого г выполняется неравенство Р (A, > 2n^1/5) < е^-п1^/5.

Доказательство. Заметим, что D, + 1 = Е(^^-Д = о,-1(1 — р( --2 )) < 2 при всех достаточно больших n. Остается оценить X, — Х,—1 = ^, — 1:

Р (^ > кп^1/5) <  ^іР^

Ап1/5

< ---------Г- < е

(к — 1)n1/5n1/5!

-

п1/5

при всех достаточно больших п.

□

Лемма 2. Для фиксированного Т > 0 при всех доста точно больших п выполняется max      |S,| < Cn.

г<[(к-1)^-1^³п²^3Т ]

Доказательство. Очевидно в силу равномерной ограниченности (и равномерной же отделенности от 0) величин ^,, а также того, что

^ X, —X,—1 < 2.

1 < і < п

□

Лемма 3. Для некоторого C >  0 при всех tun выполняется соотношение

Е (maxS²) <  Ct. i

Доказательство. Из неравенств Дуба следует, что

Е (maxS,²) < 4Е|St|² = 4 ^ D^А =О ( ^^DA, ] = O(t). ⁱ<^t                   ,=1 ^,      \t1

□

4.    Переход в непрерывное время

В данном разделе осуществляется предельный переход от процесса X- к броуновскому движению. Наиболее удобно это сделать с помощью перехода в непрерывное время. А именно, определим для s > 0 процессы

X*(s) =

X[(fe-1)-1/3n2/3s] (к |г 3м 3

X * (s)

^X[(k-1)-¹/³n²/³s\ (k - 1)¹/³П¹/³ "

Из утверждения 1 следует, что |X*(s) — X*(s)| = O(s/n1/3).

^[(fe-1)-1/3n2/3s] (fe-1)l/3nl/3

Теперь 'заметим, что X*(s) = 3*(s)S*(s) +^*(s). где 3*(s) =

[(fe-1)-1/3n2/3s\

S *(s)

E > г=1       3г

.    ^ж\(к-1)^-1/3п^2/38\        п^2/3       Л(к — 1) ^1/3п^2/3s]

^{ж (s)} = (к — 1)1/3n1/3 = 3^3⁹ ------П------) ^{+ 0(1)} =

= (Л - 1)П^{1/3 ( к} - ^’п ¹ / ⁸ s - О(к — 2) + А²) ⁽* - ‘ш/* у + 0(1) =

(к — 1)1/3                          (к — 1)1/3 2

= «s —2" + о(1), где о(.) равномерно мало по всем s < sq.

Осталось показать, что процесс 3*(s)S*(s) сходится по распределению к броуновскому движению Ws. Это следует из следующей фундаментальной теоремы из теории мартингалов.

Теорема 4. Пусть М_п = (M_n(t),t > 0), n G N — последовательность локальных мартингалов с непрерывными справа траекториями и М_п (0) = 0. Пусть таксисе (A_n(t3t > 0) — последовательность процессов, обладающая следующими свойствами:

• 1)    A_n(t) п.н. возрастает при катодом п;

• 2)    lim_n^ Е (supt<_T |A_n(t) — A_n(t — 0)|) = 0;

• 3)    lim_n^ Е (supt<_T(M_n(t) — M_n(t — 0))²) = 0;

• 4)    M²(t) — A_n(t) — локальный мартингал;

ғ

• 5)    для любого t > 0 выполняется A_n(t) ^ c(t), г де c(t) — неубывающая функция.

Тогда М_п ^^- X, где X — это центрированный гауссовский процесс с дисперсией c(t).

Начнем с построения A_ra(t). Зафиксируем п и рассмотрим последовательность Ег = 32S² — 32-1S²-1. Преобразуем это выражение:

Т) г =3-S2 — 32-1S²-1 = (3гSг —

/                       г-1 д.

=  дг + (3г — 3г-1)

\                 1=1 ³¹

= Д2 + 23гSг-1Дг + (3^ — 3L1)SL1.

3г-1Sг-1)(3гSг + 3г-1Sг-1) =

/                   г-1 д.\

I дг + (3г + 3г-1)          I :

\                 1=1 ^3j /

Теперь вычислим Е(Вг\Тг-1):

Е (D іХ Т і-Д = Е(А²\Тг-1) + (32 - PL1)SL1 = D^T—J + (3^ - 32-1)S2—1.

Положим теперь Аг = Dг - Е(Dг\Тг-1) = Dг - D(r]i\Ti-1) - (3г — 3L1)SL1- Нетрудно видеть, что Аг образуют мартингальные разности. Стало быть, последовательность г                   г                   г                                                        г

Z, = £ А ₃ = £ D3 - £ E(D3\Е₃—1) = 3^г - £ ф^\E₃—i) + (9? - 3^-i)S^i)

3=1       3=1       3=1                           3=1

является мартингалом. Наконец, для данного зафиксированного п мы готовы определить A_n(t) следующим образом:

[(k-1)-1/3n2/3t]

■           '.   .       £ ^{D Т}       2 - /У^У).

Также для последующих выкладок нам понадобится определить

¹        7

^Z"^(t)    (к _ 1)2/3_п2/3 ^{Z[(k-1) 1/3} тбШУ

Заметим, что для каждого п выполняется тождество

(3*(t)S*(t))² = Z_n(t) + A_n(t).

Теперь начнем проверять условия теоремы 4. Мартингальность 3 * (t)S *(t) относительно фильтрации Т *(s) = Т[(к_-1)-і/з_га2/з₅] очевидна из определения величин А_г. Также по определению 3 *(0)S*(0) = 0. Как известно, квадрат мартингала является субмартингалом, поэтому E(D, \Т_г-1) > 0, и, следовательно, A_n(t) является монотонно возрастающей. Таким образом, свойство 1 доказано. Проверим свойство 2:

[(k-1) 1/3n2/3t]

^A„^{(t) - A} _n ^{(t - 0)} = (к - 1)2/з_п2/з     £     (^D(^^г\^Тг-1) ^{+ (32 - 3}г²-1Ж²-1) ^-

[(k-1)-1/3n2/3(t-e)]

- ■ ■. _{( к} - 1) 2/3 „ 2/3        ^£         "\^Т-1) + (3² _3²-₁)S²-₁) .

Заметим, что D(^i\Тг-1) = 0(1). поэтому sup\A„(t) -A„(t-)\< —--- 1,    ,       sup      \3г2 - 3L1\SL1 + О(п-2/3).

t(к ^{- 1)2}/³n²/³ г<(к-1)-¹/3тп²/3

В силу 3І - 32-1 < ^ имеем sup \An(t) - An(t-)\ < t

(k - 1)2/3„=/3 ,<(t_1)-P/3t„2/3 1-1

Остается заметить, что в силу леммы 2 математическое ожидание данного выражения стремится к 0.

Проверим теперь свойство 3 теоремы 4. Распишем разность 3*(^s)S*(s) - 3*(⁸-)8*(s-) чуть подробнее:

3*(s)S*(s) - 3*(s - 0)S*(s - 0) =

= 1im           .    .

емО (k - 1)1/3п1/3

( (3[_(k-1)-1/3n2/3s]

-

3[(k-1)-1/3n2/3(s-e)])S[(k-1)-1/3n2r3(s-e)] +

+A[(k-1)-1/3n2/3s]) .

Переходя к супремуму по t, получаем, что sup |3*(s)S*(s) - 3*(s-)S*(s-)| < t

sup       (3i - 3i-1)Si-1

i<[(k-1)-y3n2/3T ]

(^-ІДТзДуз

+

sup Аі i<[(k-1) —1/3n2/3T ]

(k - 1)1/³n1/³

откуда тривиально следует, что sup 13*(s)S*(s) -3*(s-)S*(s-)| < t

4 sup       Si-1

i<[(k-1)-1/³ n²/³T ] (k - 1)1/³n⁴/³

+

sup Аі i<[(k-1) — 1/3 П2/3Т ]

(k - ly/W³

Применяя лемму 2, получаем

sup |3*(s)S*(s) -3*(s-)S*(s-)| <       + t

sup Аі i<[(k- 1)-1/3n2/3T ] (k o- 3n- 3

Тогда

Esup |3*(s)S*(s) - 3*(s-)S*(s-)|² = E(sup |3*(s)S*(s) - 3*(s-)S*(s-)|)²<

t

t

sup      Аі i<[(k-1)-1/3n2/3T ]

(k - 1)1/3n1/3

sup      А_і

C²            i<[(k-1)^-ir³n²r³T ]

n2/3 +          (k - l)1/3n2/3

sup      А_і²

+ E

i<[(k-1)-1/3n2/3T ]

(k - 1)1/3n1/3

Первое слагаемое, очевидно, стремится к нулю, поэтому оценим второе и третье, опираясь на лемму 1. Имеем:

E

E

sup      Аі i<[(k-1)-1/3n2/3T ]

(k - 1)1/3n2/3

sup      А_і²

i<[(k-1)-1/3n2/3T ]

(k - 1)1/3n2/3

О (n^-2/3 • [n^1/5 + [(k - 1)^-1/3n^2/3T . n

О (n^-4/3 • [n^2/5 + [(k - 1)^-1/3n²/³T .      n²

O(1),

O(1),

что завершает обоснование третьего условия теоремы 4.

Проверим свойство 4. Оно очевидно из соотношения (3*(t)S*(t))2 = Zn(t) + An(t), а также мартингальности Zra(t).

Проверим, наконец, свойство 5 для c(t) = t. Сперва заметим, что

[(fe-1)-1/3n2/3t]

А 0

^^(t) - (k - 1)2/3_п2/3    Е    Ш№-1)

при п ^ то. Действительно, из леммы 3 следует, что Р(max S² > dlnn) ^ 0. Подставляя i1

d = [(k - 1)^-1/3n^2/3t] и вспоминая оценку \/3² — /3²-1\ < 4/n, получаем

[(fe-1) —1/3n2/3t]

d2 In n

(k - 1)²/³n²/3

^ 0,

Р

(k - 1)2/3n2/3      Е      \3i - 3i-1\Si-1 > откуда и вытекает утверждение выше. Осталось доказать, что

[(fe-1) ^—1/3n^2/3t]

(k - 1)2/3п2/3     Е     D⁽nⁱ\P^i-1) A L

Имеем

D(ni\Pi—1) = E(№-1) - Е²(щ\7ДД =

= oi (1 - (1 - p)(n——21)) + oi(oi - 1) (1 - 2(1 - p)^1^

C)/n — г —1\ ( - г — 2\\         _o /               /n—г—И\²

+ (1 - p) ( -—2 ) ( -—3 )J - (o’) ^1 - (1 - p)( -—2 'J =

= (o‘)²fⁿ - * - ²)p + o - ' - ^p + O(n^-1) =

\ k - 3 /      \ k - 2 /

= n2fn - ^ - 2)Р + п(П - ^ - 1)p + O(n 1/4) = X(k - 1) + O(n 1/4), \ k - 3 / k к - 2 / причем все O равномерны no t = O(n3/4). Суммируя по.тунеішый резутьтат по г. получаем необходимую сходимость.

5.    Сходимость размеров компонент связности

Подведем итоги рассуждений предыдущих параграфов. Из теоремы 4 следует, что процесс ^*(s)S*(s) сходится к броуновскому движению. Тогда в силу (2) мы получаем, что процесс X*(s) сходится к процессу B_s из условия нашей теоремы. Далее, заметим, что набор компоненты заканчивается в тот момент, когда X_s и, стало быть, X*(s), достигает своего очередного минимального значения. Значит, размеры компонент будут соответствовать экскурсиям процесса X*(s). Напрямую следуя общим рассуждениям Олдоса о слабой сходимости таких функционалов из работы [7] (см. параграф 2.3), мы получаем, что длины экскурсий X*(s) будут сходиться по распределепито к длинам экскурсий B_s. Остается заметить, что коэффициент сжатия времени составляет (k - 1)^-1/3п^-2/3, поэтому этот же коэффициент будет соответствовать правильной нормировке компонент:

((k - 1)^1/3п^-2/3 • C^^^(n),i <т) -^Э (|7j\,j< m).

6.    Сходимость сложностей компонент связности

Перейдем к обсуждению сложностей компонент. Сначала заметим, что по свойству 3 обхода в ширину в ходе первых п3/4 итераций обхода в ширину сложность может увеличиваться лишь за счет ребер, которые имеют нетривиальное пересечение с очередью Qi. Но в отличие от случая графов новое ребро может увеличить сложность компоненты более чем на единицу. Поймем, какие у нас есть варианты.

Оценим вероятность того, что новое ребро, проведенное на шаге г, пересекает множество Qi хотя бы по трем вершинам. Легко видеть, что такая условная вероятность этого события (относительно ^i-i) не превосходит

IQil³^——^— 3)p = °(IQiI3^n-3).

Мы знаем, что с вероятностью, стремящейся к 1, |Qi| = °(n2/3 lnn), поэтому в типичной ситуации эта условная вероятность равна °(ln3n/n). Суммируя по г < п3/4, получаем, что с вероятностью, стремящейся к 1, подобные ребра не дают вклад в сложность компонент.

Тем самым у нас остаются только ребра, которые пересекают множество Qi по одной или двум вершинам. Далее, мы следуем рассуждениям из [7]. На каждом шаге г работы BPS мы погрузим процесс набора новых ребер в компоненту в непрерывное время. А именно, для каждого ребра, выходящего из текущей вершины v и содержащегося в Qi U °i, рассмотрим независимую равномерную случайную величину на отрезке [г, г + 1], которую мы будем считать временем включения этого ребра в компоненту. Рассмотрим считающий процесс N_n(s), который ставит «метку» в тот момент времени, когда появляется ребро, повышающее сложность компоненты. Тогда при |Q^_sj| > 1

(n-LsJ-i) —(n

|^Ql_sj ^|+1-LsJ-1\ k-1       ) =

P (A_n(s) имеет точку на [s, s + As]|J"i_sj) = (1 — pAsp ^k-1

k-2

= (IQ_W| — 1) A~7 (1 + °(1/n))A« = ^{L J}       (k — 2)!

= |Q|s^JI----(1 + _О(1/_П))Д₅.

П

Рассмотрим и второй считающий процесс А(s), который ставит «метку» в тот момент времени, когда появляется ребро, повышающее сложность компоненты ровно на 1. Несложно понять, что верно такое утверждение:

Р« (s) имеет точку на

^[s, ^s + ^As]|J"l_sj) = ^(|Ql_sJ I ^— 1)

k-2

?P— (1 + °(1/n))As.

(k — 2)!

Далее, заметим, что

Тогда

max(|Q_s| — 1, 0) = X_s — minX_s. t

X*(n) — min A*(n) = (k — 1)^-1/3n^-1/3 t

(X

-

^minX^ =^{(k —} !) 3

-i/3n-i/3

max(|Qs| — 1, 0),

где s = [(k — 1) ^1/3п^2/3п]. Тогда

P (A(s) имеет точку на [(k — 1) ^1/3n^2/3n, (k — 1) ^1/3n^2/3(n + An)] И(_к-1)-і/з_п2/з_и) =

=  ^1)1/3n^1/3 /*(_n) — minX*(n)) П                  t

(1 + o(1))(k — 1)-1/3n2/3An =

( X •(«)

-

minX * t

(n))

(1 + o(1))An.

Согласно уже доказанному, процесс X*(n) — minX*(n) сходится по распределению к t

B'u = Вп — mint

(((^ — 1)^1/3п^-2/3 • C^(n),Vj(н)'),]< ///) -А ((Д,|,ф),]< rn).

Теорема 3 доказана.

Исследование выполнено за счет гранта Российского научного фонда № 22-21-00411.