Так, друзья, прежде чем я сформулирую очередную задачу,

давайте я немножко напомню, вот у нас на лекции была основная теорема, собственно.

Теорема, которая утверждала, что количество копий конкретного

графа H в одном случае почти наверняка равняется 0,

ну а в противоположном случае, почти наверняка не меньше 1.

Если я правильно помню, на лекции я обозначал количество копий графа

H в случайном графе G величиной X с индексом H(G).

H у меня имел k вершин и

l ребер.

ρ(H) — это, естественно, плотность, равная l / k.

Ну и пороговая вероятность, собственно, вот для того утверждения,

которое я только что озвучил, пороговая вероятность p(n) — это

есть n в степени −1 / ρ(H).

Но...

то есть, еще раз, если...

это такая пороговая вероятность, давайте я здесь поставлю звездочку,

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

То есть, если вероятность ребра это o (маленькое) от вот этой величины при n

стремящемся к бесконечности, то асимптотически почти наверное XH-тое = 0.

А если, наоборот, ω (маленькая), то есть вот эта функция помножить на еще

что-нибудь, растущее к бесконечности, то асимптотически почти наверно XH-тое это,

как минимум, единица, то есть хотя бы одна копия присутствует.

Ну и я вам говорил, что в случае, когда, собственно,

вероятность вот какая-то такая, а именно,

когда вероятность ведет себя асимптотически как некоторая константа C,

неважно какая положительная константа, помножить на n в степени −1 / ρ(H),

то в этом случае вероятность вхождения графа H в случайный граф G,

G(np) Эрдёша-Реньи, вот эта вероятность, она не стремится ни к нулю, ни к единице.

Я об этом говорил.

То есть, вот в одном случае к нулю, в другом случае — к единице,

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

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

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

ни единице, а равна какой-то там константе, зависящей от величины C.

И вот на самом деле, несложно написать какой.

Я не буду сейчас это доказывать.

Это, конечно, трудная теорема, это не задачка для разбора на видеосеминаре.

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

хорошую задачу.

А именно, давайте будем утверждать вот что: положим λ равным...

сейчас я вам скажу чему...

C в степени k / a(H),

где C — это вот это C, k — это количество вершин графа H.

А величина a(H) это та самая, которую мы ввели в предыдущей задаче.

То есть, это количество автоморфизмов графа H.

Так вот, теорема утверждает,

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

то для любого m вероятность того,

что X с индексом H равняется m ведет

себя при n стремящемся к бесконечности асимптотически как λ в

степени m e в степени −λ поделить на m!.

То есть, как говорят, случайная величина X с индексом H имеет

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

Ну это действительно распределение Пуассона, да?

Товарищи, кто знает теорию вероятности?

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

вот хитро, забавно выражается через константу C и через число автоморфизмов.

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

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

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

Если аккуратно посчитать...

вот помните, я на лекции писал какие-то чиселки — a(kl), что-то такое,

b(kl) — вот на самом деле, их надо заменять на число автоморфизмов,

и это будет правильный ответ в задаче про математическое ожидание.

Ну да Бог с ним.

Значит, вот в эту теорему давайте просто поверим.

Есть такое замечательное утверждение, что, ну, например, вероятность того, что XH =

0, это приближенно e в степени минус — вот такая вот штука — C в k-той / a(H).

Вот представьте себе.

Да, то есть, вот если m равняется нулю, то λ в m от m!

пропадает, остается e в степени −λ.

Ну, вот давайте предложим, например, такую задачу.

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

и попробуем посчитать асимптотическую вероятность,

ну, предел то есть, при n стремящемся к бесконечности, вероятности того,

что вот в этом случайном графе, в этом случайном графе

ровно один граф на четырех вершинах с не менее пятью ребрами.

Ровно один граф

на четырех вершинах с не менее пятью ребрами.

Вот, конечно, не зная утверждения этой теоремы,

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

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

то уже вот эту вероятность посчитать нам не слабо.

А именно давайте действовать так: ну, во-первых, поймем,

а какие вообще графы на четырех вершинах имеют не менее, чем пять ребер.

Вообще сколько есть всего таких графов?

На самом деле, все исключительно просто.

Один граф вот такой: на четырех вершинах и в точности с пятью ребрами, правильно?

Такой вот ромбик.

С диагональкой.

Это один вариант, а другой, собственно, полный граф,

полный граф на четырех вершинах.

Да, товарищи, я надеюсь вы понимаете,

что вот в этой теореме H по-прежнему предполагается сбалансированным, конечно.

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

случая.

То есть, и здесь в этом утверждении речь идет о том, что граф H,

конечно, является сбалансированным,

иначе это все не так просто устроено и надо рассуждать немножко по-другому.

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

и вот этот граф и, конечно же,

полный граф на четырех вершинах — это сбалансированные графы.

То есть, если обозначить, скажем, первый граф буковкой H1,

а второй граф буковкой H2, то присутствие каждого из них,

ну, то есть, поведение случайной величины X с индексом H1,

и поведение случайной величины X с индексом H2 присутствия в случайном графе,

это поведение вполне себе может быть охарактеризовано вот этой вот теоремой.

Как вот этой теоремой, так, естественно, и теоремой с лекции.

Так, естественно, и теоремой с лекции.

Ну, давайте посмотрим, давайте посмотрим сначала на граф H с индексом 2.

Для его изучения вполне достаточно результата,

который мы строго доказали, который у нас на лекции просто был.

Плотность этого графа — ρ(H2) — это, естественно,

шесть ребер поделить на четыре вершины и это есть 3/2.

Плотность этого графа: 3/2.

Ну значит, 1 / ρ(H2) = 2/3.

Правильно?

А вероятность ребра случайного графа, с которым мы сейчас имеем дело, это 4/5.

То есть, вероятность ребра стремится к нулю гораздо быстрее,

конечно, гора-а-аздо быстрее, чем n в степени −2/3.

То есть, пороговая вероятность (p*) = n в степени −2/3,

а наша текущая вероятность n в степени −4/5, ну понимаете,

n в степени −2/3 = n в степени −0,6 в периоде.

А n в степени −4/5 = n в степени −0,8.

То есть, наша вероятность — это o(p*).

n в степени −4/5 = o(p*).

Поэтому по теореме, которая была доказана на лекции для сбалансированных графах,

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

наверное, нету.

Асимптотически почти наверное такие графы просто отсутствуют,

поэтому вот в эту вероятность они дадут вклад o(1).

Вероятность того, что в случайном графе присутствует такая штуковина,

стремится к нулю при n стремящемся к бесконечности.

Ну и еще есть слагаемое, которое отвечает количеству копий графа H1.

Ну, а граф H1 замечательно подобран,

потому что ρ(H1) это в точности 5/4,

у него пять ребер и четыре вершины.

В точности 5/4, то есть, у нас получается,

что 1 / ρ(H1) это в аккурат 4/5.

Иными словами, наша вероятность текущая — n в степени −

4/5 = n в степени −1 / ρ(H!).

То есть, мы находимся прямо на пороге и C у нас равняется, очевидно, единице.

Правильно?

Ну, конечно!

Так...

дальше...

сейчас, очевидно равняется единице, да...

и чего, собственно говоря?

Давайте λ напишем.

λ у нас получится 1 в 4 степени / a(H1).

Ну и это, конечно, равняется 1/4.

Ну, легко сообразить, что автоморфизмов у такого графа — 4 штуки, это,

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

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

я, собственно, поэтому в шпаргалку поглядел, я забыл!

Ну, это понятно, да, понятно.

Я сейчас вот поглядел — конечно, их 4.

То есть λ = 1/4, ну и согласно вот этой вот замечательной теореме,

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

которое я пока что не дописал, оно имеет асимптотику,

давайте я вот сюда перемещусь, 1 + o(1),

ну, то есть, оно имеет асимптотику, помножить на, собственно,

вот какую величину: нам же надо, чтобы ровно один граф был на четырех вершинах.

То есть, надо m положить равным 1.

Это будет 1/4 в первой степени,

e в степени −1/4 и поделить на 1!.

То есть, итоговый ответ: вероятность

асимптотически равна 1/4 (e в степени −1/4).

И это, собственно, то, к чему мы и стремились.

Вот можно посчитать такую штуку с помощью наших теорем.

Задача об одном подграфе на 4 вершинах и не менее 5 ребрах

Случайные графы

Meet the Instructors