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

Одним из классических объектов современной комбинаторики является граф G(п,г,s) = (V(п,г), Е(п,г, s)), у которого множеством вершин являются все г-элементные подмножества множества Е_п = {1, 2,..., п}, и между двумя вершинами проводится ребро тогда и только тогда, когда мощность пересечения соответсвующих г-элементных подмножеств равна s.

Отдельный интерес представляет из себя случай s = 0 — такие графы принято называть кнезеровскими. Легко видеть, что G(п, 1, 0) не что иное, как классический полный граф на п вершинах.

Вокруг графов G(^ r,s), в том числе кнезеровских графов, сформировано большое число исследовательских задач, среди которых важное место занимает изучение их случайных подграфов.

В 1959 году П. Эрдеш и А. Реньи предложили модель случайного графа, которая к настоящему времени очень глубоко изучена (см. [1], [2], [3], [4]). Случайный граф G(п,p) в этой модели — это случайный элемент со значениями во множестве всех графов на п

(С) Гусев А. С., 2026

• (с) Федеральное государственное автономное образовательное учреждение высшего образования «Московский физико-технический институт (национальный исследовательский университет)», 2026

вершинах VV = {1,... ,п} без петель, кратных ребер и ориентации, имеющий биномиальное распределение, т. е.

Р^(п,р) = (V_n,E )) = р^|Е|(1 - р)^с- -^1Е1.

Отметим, что р — вероятность ребра — это, вообще говоря, функция от п.

Одной из важнейших задач о случайных графах Эрдеша - Реньи является задача об отыскании их чисел независимости, хроматических чисел и кликовых чисел (см., например, [7], [5], [6], [8]).

Дабы сформулировать ниже результаты об асимптотическом поведении кликовых чисел, договоримся о некоторой терминологии. Во-первых, если Л — это какое-то свойство графа (например, свойство связности), то будем писать P(G(n,p) G Л) или, при отсутствии разночтений, просто Р(Л), имея в виду вероятность, с которой случайный граф G(n,p) обладает этим свойством. Заметим, что в принципе само свойство может зависеть от п: на-п _ пример, граф обладает свойством Лп, если его хроматическое число больше —. Во-вторых, будем говорить, что свойство Л (или, точнее, последовательность свойств Лп) реализуется с асимптотической вероятностью 1, если P(G(n,p) G Лп) ^ 1 пр и п ^ от. Наконец, пусть / — некоторая функция натурального аргумента п, а д ~ некоторая функция, определенная на множестве всех графов. Будем говорить, что с асимптотической вероятностью 1 выполнено свойство д(G(п,p')') ~ /(п), если существует еще одна функция р аргумента п, которая бесконечно мала по отношению к / при п ^ от и с которой

P(|д(G(п,p)) - /(п)| <  р(п)) ^ 1, п ^ от.

В данной статье мы обратимся к работе [9], в которой глубоко рассмотрено поведение кликового числа случайного подграфа кнезеровского графа Q ^С(п,г, 0),-^ для случая, когда г — некоторая функция от п. Так автором данной работы установлено, что

Теорема 1.1. Пусть стью 1 справедливо

w

Теорема 1.2. Пусть стью 1 справедливо

W

Видим, что при г

г = п“^+о(1), причем а < -. Тогда с асимптотической вероятно-

QQ (о(п,г, 0), 2) > >  (1 + о(1))2(1 - а)г log₂ п.

г = п“^+о(1), причем а <  1. Тогда с асимптотической вероятно-

(Q (о(п,г, 0), 2) ^ < (1 + о(1))2(1 - а)г log₂ п.

п“+°(¹⁾₁ д_ЛЯ а < - нижняя и верхняя оценки в теоремах 1.1

и 1.2 соответственно совпадают. Таким образом, получено асимптотическое значение для кликового числа.

Теорема 1.3. Пусть г = п“+о(1), причем а > -. Тогда с асимптотической вероятностью 1 справедливо w (q (о(п,г, 0), |^ = и^(п,г, 0)).

Таким образом, теоремы 1.1-1.3 дают почти исчерпывающий ответ на вопрос о поведении кликового числа случайного подграфа кнезеровского графа. Открытым остается только вопрос, чему равно кликовое число в случае, когда г = п 2 +^о(1). Приведенная ниже теорема частично проливает свет на поведение кликового числа случайного подграфа кнезеровского графа именно для таких п.

Теорема 2.1 Пусть г = n2f (n), где f (n) = no(1). Тогда для любого е > 0 с асимптотической вероятностью 1 справедливо w (0 ^(п,г, 0), |^ = w(G(n,г, 0)), при f (n) > ^2 + е,

Теорема 2.2 Пусть г = n2 f (n), где f (n) = n^'1. Тогда для любого е > 0 с асимптотической вероятностью 1 справедливо w (0 ^G(n,r, 0), 0) = (1 + о(1))гlog2n, при f (n) <

(log2 n) 2 +

.

Доказательства теорем 2.1-2.2 очень похожи на те подходы, что ранее были применены в доказательствах теорем 1.1-1.3, однако требуют большей аккуратности в отдельных оценках.

Таким образом, теоремы 2.1-2.2 показывают, что в зависимости от f(n) кликовое число соответсвующего случайного подграфа может как с асимптотической вероятностью 1 совпадать с кликовым числом исходного графа (при f (n) ^ X- + е), так и быть асимптотически меньше. Действительно, w 0Q G^^ 0), I}} = (1 + °(1))г log2n = (1 + o(1))n 2f (n)log2n, в месте с тем

w(G(n, г, 0)) = (1 + ₀(1))ⁿ = (1 + ₀(1)) -^L. г               f (n)

Легко видеть, что при f (n) ^------1^ для любого е > 0 кликовое число случайного подграфа будет асимптотически меньше кликового числа исходного кнезеровского графа.

Пороговые значения f(n), при которых кликовое число случайного подграфа становится хотя бы на 1 меньше кликового числа исходного кнезеровского графа, а также при которых кликовое число случайного подграфа становится асимптотически меньше клико-вого числа исходного кнезеровского графа, еще только предстоит найти.

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

Пусть функция f (n) не меньше ——+ е для некоторого е > 0.

Введем случайную величину Xt, равную количеству клик размера t = [—]. Требуется г доказать, что с вероятностью, стремящейся к 1, найдется хотя бы одна клика размера t, то есть P(Xt = 0) -----> 0.

п ^^

Применим неравенство Чебышева

(MX-t^ > p(|Xt - MXt|> MXt) =

= P(X_t - MX_t > MX_t, X_t > MX_t) + P(MX_t

-

It > MXt,Xt < MXt) =

= P(Xt > 2MXt) + P(Xt < 0) > P(Xt < 0) = P(Xt = 0).

. DXt

Таким образом, достаточно доказать, что ---------> 0.

(MX_t)² t ^^

Теперь посчитаем количество клик размера t в графе G(n, г, 0). Очевидно, что для этого достаточно из ^ п выбрать t непересекающихся г-элементных подмножеств. А это можно сделать

г s^r         s^r

° n ^ ( _n- r) . . (n - (t - 1)r) _          n!

t!                    t!(г!)^t(n — tr)!

способами. Для удобства обозначим эту величину к.

Занумеруем все клики Wi, W2,..., Wk и введем случайные величины Y1, Y,..., Ye где

Yi = I Wi в G(n, г, 0) является кликой в Q ^G(n, г, 0), -^ j* .

Тогда очевидно, что X_t _ Y 1 + Y₂ + ... + Y k.

Через | Wi nW j | будем обозначать количество вершин в пересечении г-й и у-й клик. Тогда

1(1 — 1) очевидно, что если |Wi XWj | _ I, то в пересечении г-й и у-й клик ровно ——-- ребер. Ясно,

1                                                                                            i(i-i)

что MY_i _ _t(t-1. . Также иес.тож!ю получить, что M(YY) = 2 ² MYMY-

Таким образом,

DX_t _ MX_t² — (MX_t)² _ MX_t²     _  M(Y + Y₂ + ... + Y_k )²

(MXt)2 =    (MXt)2    = (MXt)2 - = (MYX + MY2 + ... + MYk)2

12 (ij) ^MY i ^Y'    1 _ S(i,l): | W _in W ₃-|< 1 ^MYiY + ^2( ,Д): | Ж П Ш ,|> 2 ^MYiY

EU) MY i MY ^{— _}           E (_M.) MY i MY

Е^ф^ы MYMY + Ей Е^ни-.пи-.н²  MYMY 1

E(1J) MYMY'

Понятно, что —' ""'E', "' "'   '\ ---i <  1a _значит достаточно доказать, что

Ео m^my

E t=2 Е(,_л ।w , nw ,_H²   MYMY ,™ ₀

E_W) my му          * '

Действительно:

Ей E (_tJ): | Л . ПЛ , | =1 ² MYMY Е₍,_л MYMY

t- 1                            l(l-1) /     1     \²

12 Z=2 I2( ij ): | ЖПШ ,| = 1 ^{2 2}   (   t(t-1) )

Ею) (2ф)

E

t - i 1 =2

l(l-1)

^{2  2}    22(,д):|ш.пш, | =l

^ (i,T ¹

Теперь требуется посчитать количество таких пар (г, у), что г-я и у-я клики пересекаются ровно по I вершинам. Несложно понять, что количество таких пар будет не больше, чем

/^ r fгчг

^гХ(п-г) . . . ° (n - (t - 1)r) „I ^п-lr^п-lr

-----------------;---------------Y+---------------- t!                         ^-

-

r r . . . °n-lr-(t-l-1)r _

(t — г)!

n!             t!              (n — 1г)!

(г!)^-(n — tг)!t! Z!(t — Z)! (г!)^--1 (n — tг)!(t — I)

n!(n — 1г)!

(r!)2t-i(t - l)!(t — 1)Ц!(_п — tr)!(n — tr)

Таким образом,

\' ^; ■ 2^-)¹ V

2^ l =2 ^{2 2}   Е(₈ ,]): | У ,П У₃ | =l ¹

^ (i,f ) ¹

t - 1

< E 2

l=2

n !( n — lr )!

A-1) (r!)2t—l(t-l)!(t-l)!l!(n-tr)!(n-tr)! _ ( n!      32           = t!(r!)t(n —tr)!

t - 1

= E 2

l =2

Ф-1) (t!)²(r!)^l ((n — lr)!)

n!((t — l)!)²l!

.

(t!)²(r!)^l ((n — lr)!)

Пусть al = ----• Тогуа n!((t — l)!)2l!

требуется доказать,

Посчитаем отношение

t

E £££-1)

2 2  al l=2

--------> 0.

n ^^

Ф+х к аг.

a l+i a l

(t!) ² (r!) ⁱ⁺¹ ((n - (l+1)r)!) n!((t - l - 1)!) ² (l+1)! (t!) ² (r!) ‘ ((n - lr)!) n!((t - l)!) ² l!

r!((t — l)!)²l!(n — (I + 1)г)!

^{((t — l}

— 1)!)²(l + 1)!(n — lr)!

r!(t — l)²(n — (l + 1)r)!

r!t2

(l + 1)(n — lr)!

(n — (t — 1)r)^r

При t = [—] легко видеть, что n — (t — 1)r = n — tr + r ^ r. Но тогда можно сказать, что r                    '

r!t2

^al +1 <^

a l

гГ

Таким образом, несложно видеть, что a l < ( —— )   ai.

1 ^rr J

А значит, t—1                 t— 1            / .. о \ l— 1             t—1         1—1 / li-\l — 1

E 2^ a l <  E 2^^ ( Д ) a , <  a E( 2 a ) - ( Д )

l=2              l=2                                l=2

= a1 £ (■  ' V < a, E (^Г t-1   2 l2 t2  l 1

=^a1 д

.

r’ l=2 \        /           l=2 \/

Остается вычислить и оценить a1:

a 1 =

(t!)²(r!)((n — r)!) n!((t — 1)!)²

t2r!

(n — r)^r

Для завершения доказательства подставим оценку a1 в исходное выражение:

t - 1 / ⁿ~ 2\ ^{l 1}         ,2      t - 1 /     2\ ^{l 1}

E 2 2^ t             t r!        I 2 2^ t

< —'

.

Вспомнив, что r = n2f (ri), оценим знаменатель геометической прогрессии

п

2 ^ t2

2r

i

■ 2

22f (п) t²

2^{n 2} f ⁽ⁿ⁾

2 ( 1 —2f²(n) \

= 2 У ^2/(n) tt² <         2

f 2(n)

n 2 (        ' ^

2/(п>   j

что стремится к нулю при f (n) ^ ——+ е.

В свою очередь это означает, что и t2r!

(п — r)^r

^ (¥ 1

-------4 0.

п ^ж

Таким образом, вероятность того, что кликовое число графа Q (G(п,r, 0), -) меньше стремится к 0. А это означает, что с асимптотической вероятностью 1 справедливо, ^w (^Q ^!(п,г, ⁰⁾, 0) = w(G(n, r, 0)) и теорема доказана.

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

Верхняя оценка для w Qq ^G(n, r, 0), -^^ является частным случаем теоремы 1.2 a = -. Таким образом, нам нужно доказать, что

[п ] r что

для

w Qy ^(п,г, 0), j) ) > (1 + o(1))r log2n.

Для доказательства этой оценки введем случайную величину Xt, равную количеству клик размера t = [r log2 п — 2r log2 (f(п) log2 п)].

Тогда повторим рассуждения из доказательства теоремы 2.1 до вывода формулы (1) и получим, что требуется доказать следующее:

t -i

Е Ш^-1)

2—

1 =2

(t!)2(r!)i((п — lr)!) п!(Д — l)!)2l!

--------> 0.

п ^ж

Пусть a i =

(t!)2(r!)i ((п — lr)!)

---—---   —. Тогда необходимо доказать, что п!((t — l)!)2l!

Посчитаем отношение ai+i к ai:

t -i

Е Щ^-1)

² — a , i =2

--------4 0.

п мж

a i +i a i

Заметим, что

дМ+Адпддд)

n !(( t - i -i)!)²( i +1)!    _ r!((t — 1)!)²1!(п — (l + 1)r)!

(Wy (( n - ir )!) ~ = ((t — l — 1)!)²(l + 1)!(п — lr) n !(( t - i )!)² i !

r!(t — 1 ) ² ( п — (l + 1)r)! r!t²

(l + 1)(п — lr)!     _ (п — tr)r tr = [r log2 п — 2r log2 (f(п) log2 п)]г ^

Поскольку J(п) ^

большое и

< (r log2 п — 2r log2 (f (п) log2 п )) г =

= r²(log2 п — 2 log2 (f (п) log2 п)) =

= п^{f 2 (}п^)(lOg2 п ^{— 2} log2 ^{(f (}п) log2 п)).

-------1— ii изучается п -4- от. то можно считать, что п достаточно

(log2 п) 2 +

п — tr > ^п.

^a i +1 /

Но тогда --- < ai

r!2^rt² п^г

Таким образом, несложно видеть, что ai < ( —--- )

V ^п" J

А значит,

1- 1

а 1 .

t-i у^ „ Ф—I)

X^{2 2 a}i

1=2

< g 2 ^ (ДЕ)

i =2       \ ^П /

1- 1

t-i ( ai < ai£ i=2

п"

22’" logA J ⁽ⁿ)^log2 ^п)

\ 2 (rw t²\^{1 i}

J (—J <

<

ai £( i=2 \

п 2r!2" t²

f (п)" (log2 п)" п"

) <  A (

( t ) " 2"t²

f(п)" (log2 п)"п²

) '

= ai E ( i=2 V

r" t2

f (п)"(log2 п)" п²

)

E / ( п¹ f (п) ) t² \ ⁱ i=2 \ f (п)"(log2 п)"п² I

= а 1

E (-t^- ) i=2 ^(log2 ^п)"

t- 1

1- 1

.

Остается вычислить и оценить ai:

а 1 =

(t!)2(r!)((n — r)!) п!((t — 1)!)2

t2r!

(п — г)"

Для завершения доказательства подставим оценку ai в исходное выражение:

E / t² V ^{i ai} Е UhEF ) <

t2r!

(п — r)"

E ( -t2- Г

^  ^(log2 ^п)"

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

Таким образом, вероятность того, что кликовое число графа Q(G(n,r, 0), -) не превосходит [r log2 п — 2r log2 (f (п) log2 п)], стремится к 0. А это означает, что с асимптотической вероятностью 1 справедливо, что w Q(J ^G(n,r, 0),-^ ^ > (1 + o(1))r log₂ п и теорема доказана.