Еще одна хорошая задача на неравенство,
вот неравенство Маркова мы уже научились применять, еще одна хорошая задача на
неравенство Маркова и Чебышева обобщает то, что у нас было на лекции.
Значит, смотрите.
На лекции, рассматривая пресловутый случайный граф с вершинами 1,
..., n и вероятностью ребра P, мы доказали следующее замечательное утверждение.
Мы доказали, что если p — это функция от n и np, ну можно писать np от n,
но я уж не буду этого делать, потому что это стало как бы общим местом для нас.
Мы показали, что если np стремится к 0, то с вероятностью, стремящейся к единице,
ну или там асимптотически, почти наверное это можно называть,
то с высокой вероятностью случайный граф не содержит треугольники.
Не содержит треугольники.
И наоборот, если np стремится к бесконечности,
то с высокой вероятностью, с вероятностью, которая стремится к единице,
асимптотически почти наверное, случайный граф содержит хотя бы один треугольник,
содержит хотя бы один треугольник.
Вот это было доказано на лекции с помощью неравенства Маркова и Чебышева.
И вот если мы хотим с вами научиться в целом понимать структуру
такого доказательства, давайте попробуем задаться следующим вопросом и, собственно,
мы им и задаемся в этой задаче.
А что будет, если свойство содержать треугольник заменить свойством
содержать полный подграф на четырех вершинах?
Подграф содержит или
же не содержит [БЕЗ_ЗВУКА] К4,
полный подграф на четырех вершинах.
И вот как для этого свойства выглядят аналогичные условия,
то есть условия, которые служат переключателем для того,
что случайный граф не содержит, случайный граф содержит с высокой вероятностью?
Ну давайте, наверное, введем случайную величину ξ,
которая на графе принимает значение равное количеству
К4 в этом случайном графе G.
Сколько есть всего полных подграфов на четырех вершинах в этом случайном графе.
Тогда математическое ожидание ξ моментально считается по линейности,
мы просто представляем ξ в виде суммы ξ1,
..., ξ с индексом С из n по 4.
Каждый раз ставя 1 или 0, смотря по тому — очередной
К4 потенциальный есть в нашем конкретном графе или его там нет,
ну давайте напишем ξ i-тая от G — это единица.
Если i-ая по счету четверка
вершин образует К4 в графе G,
образует К4, и 0 — если этого не происходит,
то есть 0 в противном случае, иначе.
Четверок вершин, конечно, С из n по четыре, вот про каждую мы посмотрели,
образует она К4 или не образует.
Ну и в итоге получаем сумму по i от 1 до С
из n по 4 матожиданй ξ i-тых, ну то есть вероятность того, что фиксированная
четверка образует в случайном графе полный подграф на четыре вершинах.
Полный подграф на четырех вершинах, разумеется, имеет шесть ребер.
Поэтому вот это вот математическое ожидание — это просто p в шестой,
вероятность того, что что все шесть ребер, которые образует вот этот К4,
действительно, присутствуют в случайном графе.
Ну это уже общее место, получаем С из n по четыре на p в шестой.
А дальше можно сообразить — откуда на самом деле появлялись вот эти
вот условия для случая полного графа на трех вершинах, то есть для треугольника.
Они на самом деле появлялись из тех соображений, что математическое ожидание
то ли стремится к нулю, то ли стремится к бесконечности.
И действительно, смотрите, вероятность того,
что ξ ≥ 1.
Что это такое по сути?
По сути, это вероятность того, что в графе есть хотя бы один К4.
Ну она точно не превосходит, согласно любимому нами неравенству Маркова,
математического ожидания ξ, то есть в аккурат вот этой величины С из
n по 4 на P в шестой, но C из n по 4 — это,
конечно, n на (n − 1) на (n−2) на (n−3), поделить на 24.
24 — это 4 факториал.
Ну просто факториалы сократились в С и получилось так.
И дальше надо умножить на p в шестой.
Разумеется, с аналитической точки зрения, все равно, что написать (n − 1),
(n − 3) или n в четвертой, асимптотически — это одно и то же,
получается n в четвертой на p в шестой, на 24.
В том смысле, что если мы разделим левую часть на правую,
то в пределе получится единица, конечно.
Так, ну и смотрите, если вот это произведение,
давайте напишем n в четвертой на P в шестой стремится к 0, если это так,
то вот это все тоже стремится к 0 при n, стремящимся, разумеется, к бесконечности.
То есть, оказывается, что стремление к 0 вот такого выражения уже гарантирует нам,
что с высокой вероятностью, ну здесь низкая вероятность написана,
но низкая вероятность того, что ξ больше либо равняется 1, гарантирует нам,
что с высокой вероятностью, с вероятностью, которая, напротив,
стремится к 1 при n стремящимся к бесконечности, ξ равняется 0.
То есть в графе нет К4,
в графе нет К4, и это получается как раз аналогом условия,
n умноженного на p стремится к 0, которое гарантировало нам,
что с высокой вероятностью в графе не будет треугольников.
Ну и дальше возникает гипотеза, что, наверное, если потребовать, наоборот,
вот такое вот условие, что n в четвертой умножить на p в шестой стремится к
бесконечности, то окажется, ну это пока под вопросом,
что с высокой вероятностью
ξ ≥ 1.
То есть в графе есть хотя бы один подграф К4.
Но это пока гипотеза, доказательство которой, естественно, получается так же,
как на лекции доказывалось, что, если np стремится к бесконечности,
то в случайном графе почти наверняка найдется треугольник.
А именно мы выписываем снова вероятность того, что ξ ≥ 1,
но на сей раз мы хотим доказать, что она не к 0 стремится, а к 1.
Переписываем ее как 1 минус вероятность того, что ξ не больше 0.
Пожалуйста, не смущайтесь тем, что здесь написано: ξ не больше 0,
хотя ξ, конечно, отрицательным не бывает в принципе.
Но мне так удобнее, и дальше как на лекции действуем.
1 минус вероятность того, что ( −ξ ) ≥ 0.
1 минус вероятность того,
что Мξ − ξ ≥ Мξ ≥
1 минус вероятность того,
что модуль Мξ − ξ ≥ Мξ,
ну это понятно, почему так, все-таки модуль,
он чаще оказывается большим, нежели исходная случайная величина.
Поэтому вот эта вот вероятность, она, конечно,
не меньше, чем вероятность, которая написана здесь.
Но поскольку она идет со знаком минус, то неравенство написано в правильную сторону.
То есть ну это все вот в точности как на лекции, ну и дальше, наконец,
применяем неравенство Чебышева, которое нам гарантирует вот такую вот
оценку: дисперсия ξ поделить на квадрат математического ожидания ξ.
Все, что остается сделать, для того чтобы убедиться в справедливости
вот этой вот гипотезы, это нудно и мучительно сосчитать дисперсию
числа полных подграфов на четырех вершинах в случайном графе.
Ну это очень противная процедура.
Если кто помнит лекцию, как мы считали дисперсию числа треугольников,
то тот уже помнит, что мы разбирали там некоторые случаи,
а именно мы рассматривали отдельно ситуации,
когда есть пара непересекающихся треугольников.
Отдельно брали ситуацию, когда есть вот такой вот галстук-бабочка
из двух треугольников, примыкающих по одной общей вершине.
И, наконец, отдельно еще рассматривали случай наиболее нетривиальный,
когда два треугольника соседствуют по ребру.
И вот в каждом из этих случаев там получалось свое отдельное слагаемое.
Здесь, в нынешней ситуации,
надо будет смотреть — как между собою соотносятся подграфы К4.
То есть вот есть один подграф К4,
и он самыми разными способами может примыкать к другому подграфу К4.
Например, он может с ним вовсе не пересекаться, но это, по-видимому,
самый приятный из существующих случаев.
Может быть какая-нибудь вот такая ситуация, что тут есть один граф К4,
а другой как-то с ним соседствует по общему треугольнику.
Да? Вот сюда вот вынесем вершину и вот возьмем
такой еще один граф К4.
Вот один.
Вот сейчас вот сюда нарисуем.
Вот один граф К4.
Вот другой граф К4.
И они вот так хитро между собой соседствуют.
И вот надо будет тупо складывать все возможные вот эти вот ситуации.
Сложить, разделить на квадрат математического ожидания и
радостно убедиться, что если действительно n в четвертой на p в шестой стремится
к бесконечности, то эта дробь стремится к 0.
А все вместе стремится к 1.
Ну товарищи, честно говоря,
не хочется сейчас вот нудить до такой степени и перечислять все эти ситуации.
Легко проверить, и вы это точно уже теперь после этого разбора сделаете
самостоятельно, что такая дробь стремится к 0, и задача тем самым полностью решена.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
