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

Рассмотрим множество ^2хп = {G = (К” U V2”, E )} всех неориентированных графов без кратных рёбер с непересекающимися и независимыми множествами вершин V”,V” размера n G N, таких, что допускаются только рёбра между вершинами, принадлежащими различным множествам. Случайный двудольный граф G(n,n,p) является случайным элементом множества ^2х« с распределением, определяемым равенством

P(G(n, n,p) = G) = p|E(G)|(1 — p)n2-lE(G)|, то есть каждое ребро полного двудольного графа появляется с вероятностью p независимо от ДРУГИХ'

Пусть [n] := {1,...,n} — множество помеченных вершин. Напомним, что множество вершин U С [n] в графе, в котором никакие две вершины не являются смежными, называется независимым множеством. Размер наибольшего независимого множества называется числом независимости графа. Хорошо известно, что с вероятносстью, стремящейся к 1, два максимальных независимых множества в графе G(n,n,p) — это его две доли V” и V2”, поэтому число независимости точно равно n.

В [1], [2], [3], [4] было доказано, что для p = const G (0,1) число независимости биномиального случайного графа G(n,p) (в этом графе каждая пара различных вершин из [n] является смежной с вероятностью p независимо от других) с вероятностью, стремящейся к 1, принимает одно из двух значений, /(n) и /(n) + 1, где

/(n) = ^ 2log_bn — 2log_b log_bn + 2log_b 2 + 0.9- 1 , b = 1/(1 — p).

(с) Буитраго Оропеса X. К., 2024

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

Некоторые улучшения этого результата можно найти в [6]. В этом случае мы говорим, что число независимости сконцентрировано в двух точках.

В дальнейшем концентрация в двух точках была доказана и для других характеристик случайного графа. Особое внимание было уделено максимальному размеру индуцированного подграфа в G(п,p), обладающего заданным свойством. Напомним, что множество А С [п] вершин графа G индуцирует в нем подграф G \ a, множество вершин которого равно А, а множество ребер образовано всеми ребрами графа G, оба конца которых принадлежат А. Например, в [6] концентрация в двух точках была доказана для максимального размера индуцированного пути, в [7] — для максимального размера индуцированного дерева, а в [8] — для максимального размера индуцированного леса. Для каждой из этих трех случайных величин было доказано, что найдется функция С(п) = 0(1) такая, что рассматриваемая случайная величина принимает одно из двух значений log₁/(_1-p) п + С(п) и logi/(i_-p) п + С (п) + 1 с вероятностью, стремящейся к 1.

Все предыдущие результаты применимы к модели случайного графа, где вероятность появления ребра является постоянной величиной. Некоторые из этих результатов были расширены для случая р(п) = о(1). Так, в [9] было доказано, что число независимости G(п,p), г де п^-2/3+е < р <  1/[1од(п)]², сконцентрировано в двух точках. Кроме того, в [9] было доказано, что максимальный размер индуцированного дерева в графе G(п,p'), где п^{- 3е-2 +е}<  р = о(1), также сконцентрирован в двух точках.

Следующим естественным шагом является проверка концентрации в двух точках некоторых из этих характеристик в других моделях случайных графов. В настоящей работе мы сосредотачиваемся на модели двудольного случайного графа G(п,п,p). В частности, нам удалось доказать, что максимальный размер индуцированного пути в двудольном случайном графе G(п,п,p = 1/2) сконцентрирован в трех последовательных точках.

Теорема 1. Обозначим через P максимальную длину (то есть количество вершин) индуцированного пути в графе G(п,п, 1/2). Тогда для любой достаточно малой константы е >  0 с вероятностью, стремящейся к 1, Р G {2д(п), 2д(п) + 1, 2д(п) +2}, где

д(п) = (21од2п - 1 - е~ \ .

Несмотря на то, что в основе доказательства теоремы 1 лежит стандартная техника, применение неравенства Маркова для получения верхней оценки на случайную величину и неравенства Чебышева для получения нижней, проблема, как обычно, заключается в необходимости достаточно точного оценивания второго момента случайной величины, представляющей число индуцированных путей заданной длины. В отличие от стандартной модели биномиального случайного графа G(п,p') здесь возникает дополнительная сложность при оценке вклада пар пересекающихся индуцированных путей во второй момент, так как необходимо также учитывать их пересечения с каждой частью двудольного графа.

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

Для краткости обозначим д := д(п). Далее при упоминании вероятности проведения ребра, равной 1/2, будем в некоторых ситуациях обозначать ее р для большей ясности изложения — а именно, для отличия вклада в оцениваемые величины самой вероятности р и вероятности дополнения события, 1 — р. Как обычно, мы будем использовать методы первого и второго моментов. Сначала покажем, что с вероятностью, стремящейся к 1 при п ^ то. Р < 2д + 3.

Пусть Xk ~ число индуцированных путей длины к в графе G(n, п, р). Пусть к = ©(log п). Нетрудно заметить, что

EX2k = (п) (к!)²р²"^-1(1 — р/2

^2k+1 - п² 2

k2

и

EX_2k+1 = Q (к + 1) к\(к + 1)\Р2^к(1 - р)^к(к+1)-2к - п^2к+12

к ²

^к - EX2 k п2^-к ,

поскольку существует два способа выбрать часть, к которой принадлежат первая и последняя вершины нечетного пути, а количество способов провести такой путь на фиксированном наборе из к + 1 вершин од:юн части н к вершин другой части равно к\(к + 1)!/2.

В частности,

EX_2k = e^{k(2ln п-к ln2)+o(1)}

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

EX2 g +3 - EX2 g +2n2

g ^-1 = _e⁽ g ^+1)(2lnn-( g ^+1)ln2)+ o ⁽¹⁾_n2^- g ^-1< 2^e( g ⁺¹⁾_n2^-2log2^n+e =

= e (n2e-1) = 0(1).

Следовательно, по неравенству Маркова

P(X2g+3 > 1) < EX2g+3 = 0(1), что означает, что P < 2д + 2 с вероятностью, стремящейся к 1 при п ^ то, поскольку

{ P < 29 + 2} = {Х2 д +з = 0}.

Теперь покажем, что P( P > 29) = 1 — о(1) . Сначала заметим, что для 0 < е < 1 получаем

EX_2g = e^{g(2ln n-g ln2)+o(1)} > 2^eg+o(1) ^ то при п ^то.

Таким образом, по неравенству Чебышёва

P(X2 g =0) <

VarX2 g = EX2 g (X2 g — 1) — (EX2 g )

(EX2 g )²

EX2 g (X2 g

(E^2 g )2

⁺ EX2 g

^— 1) ^{— (}E^X2 g )

(E^2 g )2

- + о(1).

Остается показать, что правая часть выражения (1) является о(1).

Случайную величину X 2 g можно представить как сумму индикаторов 1 в ( и 1 и и ₂ ) по всем 9-элементным множествам U 1 С V1^{n и} U₂ С V₂ⁿ, где B(U 1 UU 2 ) — событие, заключающееся

в том, что

U 1 U U 2 индуцирует путь в G(n,n,p). Следовательно,

EX2 g (Х 2 д

- 1) =    ^   P(B(U1 UU2) ПВ ( u 1 u u 2 )) =

U 1 U U 2 ,U ( U U 2 ^⎛

\

где

Е

Е

+

Е

U 1 U U 2 и и ' u u 2           U 1 U U 2 и u 1 u u 2

\имеют общие вершины не имеют общие вершины/

U 1 U U 2 и и ' ’ u u 2 не имеют общие вершины

P(B(U1 UU2) nB(U1 UU2)) = C 1 C

P(B(U 1 UU2) ПВ(и1 UU2)),

-

⁹)² (9\)⁴ X < [CX₂ g ]².

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

2g - i

E^X 2g ^(X 2 g ^— 1) ^{— (}E^X 2 g ⁾²< Е       Е       P ( B ( U j и U 2 ) П В (U J и и 2 )) <

^V =1   U1UU2 aiiU‘uu2

with v common vertices

< е cy-to

n2g-v 7(v)

_p 2(2g - 1) (₁ - _p) 2[g 2 - (2g - 1)]

min {(1 - <1 (У21 ’

^1,^2 t            \1 — P J J где y(v) — это количество возможных перестановок вершин в пересечении двух путей (мы впоследствии оценим это значение в зависимости от величины г), ад — это количество пар общих вершин между различивши частями двудольного графа в пересечении двух путей, а ж2 — количество общих рёбер. Заметим, что ад < Е> так как это точно произведение двух неотрицательных целых чисел, сумма которых равна v. Принимая р = 1/2, получаем

^2g-1 / 2 g \ 2 _n 2 g - v

ЕХ 2д (X 2g - 1) - (EX 2g )²< EX -g^^     _ 7 (v) .               (2)

Z1   2^g 2 ^-“

Теперь мы можем найти подходящую оценку для y(v). Для v < [1.1gJ рассмотрим тривиальную оценку y(v) < v!. С другой с тороны, для v > [1.1gJ зафиксируем один путь, который назовем Pi, затем выберем общие вершины и, начиная с этих вершин, построим второй путь, который назовем P-. Таким образом, мы видим, что пересечение P i 11 P - состонт из 2д — v + 1 связных компонент, котор>ыс разделены вершинами P i. Следовательно, существует не более чем (2д—v + 1)! перестановок этих компонент. С другой стороны, для каждой связной компоненты у нас есть два варианта выбора её ориента-щш внутри P2. С.тедовате.тыю. для v > (1.1gJ мы можем оценить 7(v) <  (2д — v + 1)!2^2g-v+1.

Таким образом, из (1) и (2) следует, что

^EX 2g ^(X 2g ^— 1) ^{— (EX} 2g ) 2 (EX -g )²

<

<

1 Е ( 2vW

E^ g^J   2 g 2 - '2

M¹ I^2g)2n 2 g ^-v 2 т

Е —--- v=1

^Е v=1

2 g ²

(Дд!)2

-

■ v

Mv) =

7(v) <

(2vg) n2g-v2Tv!

С ) 2 (g!)²

2 g - 1

+^Е v= L 1.1g J +1

+

(² v ^g) n^2g-v 2 T (2g —

v + 1)!2 2 ^g-v+1

С ) 2 (g!)²

Теперь задача состоит в том, чтобы показать, что правая часть выражения (3) является о(1). Сначала раеемотрнм слагаемые е v € [1, (1.1gJ]. Так как 1 W д W ДП. получаем следующую асимптотику:

С)

ng

~ --.

д!

С другой стороны, заметим, что

Таким образом, мы получаем

^L 1 ^ ^J (^п²^2т v !

d =i

G ) ²(д!)²

∼

≤

L ^1.19 J /о \

Е (?)

V=1   4   7

L 1.19 J

Е (2д)² ^

г)=1

L 1.19 J

п-2 4

v !

п- 2 ^ V

,v

≤

L 1.19 J

= Е

г)=1

(

Дз)²^ / ⁴

п

)<

≤

^ (_n - 0.45+yiY =

V=1

о(1)-

Теперь перейдем к доказательству того, что сумма V е фШ +1, 2д — 1]:

в (3) является о(1), для

29 - 1