Давайте перейдём к попыткам оценить хроматическое число.
Как вы помните… Вернее, даже давайте я так скажу.
Конечно же,
нелепо пытаться в этой задаче оценивать хроматическое число величиной омега.
Неважно, какая из двух оценок лучше, это мы пока не обсуждали,
но омегой оценивать никак не имеет смысла, потому что мы же желаем избавиться от
циклов, значит, клик там тем более не будет, в том-то всё и дело.
Поэтому единственная оценка, которая, как вы понимаете,
есть теперь в нашем распоряжении — это оценка
величиной n / α (G), где n — это количество вершин в нашем графе,
это мощность V / α (G), то есть мы сумеем доказать,
что e (G) больше наперёд заданного k, например,
с высокой вероятностью, коль скоро оценим как-нибудь сверху величину α (G).
Замечательно.
Ну давайте вот так.
Вероятность того, что α (G) не
превосходит или даже меньше, можно сказать, какого-нибудь x.
Давайте меньше скажем.
Не не превосходит, а строго меньше.
Вот как оценить вероятность того,
что число независимости случайного графа меньше заданной наперёд величины?
Число независимости меньше какого-то x.
Какого x, это мы сейчас подберём, вы не волнуйтесь.
Α (G) меньше какого-то x.
Как оценить эту вероятность?
А давайте введём случайную величину Y.
Можно даже если угодно, с индексом x, подчёркивающую,
что мы работаем именно с этим параметром x, а не с каким-то другим.
Что такое Yx (G)?
Давайте это будет количество
независимых множеств, независимых множеств
размера x,
то есть на x вершинах в случайном графе G.
Количество независимых множеств размера x.
А теперь смотрите, вот написано в скобках событие α (G) < x.
В чём состоит это событие?
Это событие состоит в том, что в случайном
графе отсутствуют независимые множества на x вершинах.
Ведь α (G) — это размер самого большого независимого множества, самого жирного.
Если бы в графе были независимые множества размера x,
ну тогда α (G) больше либо равнялся бы x, правильно?
Но α (G) < x, и, значит, в графе отсутствуют независимые
множества размера x, то есть эта вероятность есть в точности
вероятность того, что Yx (G) = 0.
Отсутствуют — это значит их количество равняется 0.
Вот такая вот простая техника.
Это есть, конечно, 1 минус вероятность того, что Yx (G) больше либо равняется 1.
Здесь я просто написал отрицание события, состоящего в том,
что отсутствуют независимые множества.
Отрицание состоит в том, что они присутствуют, есть хотя бы одно.
Хе! Так мы можем снова воспользоваться
неравенством Маркова.
По неравенству Маркова эта штука не превосходит математического ожидания Y,
а стало быть, вся разность больше либо равна 1
− MYx.
Вот такая вот замечательная опять же техника.
Ну хорошо, давайте, наконец, сосчитаем, чему равняется математическое
ожидание числа независимых множеств, каждый из которых имеет мощность x.
Ну я могу проявить занудство и рассказать во всех подробностях.
Давайте я вот так нарисую.
Вот она сарделька, в ней n вершин, нас интересует количество
независимых множеств, каждое из которых состоит из x вершин.
Ну только что считали для циклов.
Понятно, что Yx надо представить вот в таком виде.
Какой будет последний индекс?
Сколько всего индикаторов?
Ну понятное дело, надо просто перебрать все x-элементные подмножества
n-элементного множества и каждое протестировать на независимость,
то есть последнее будет иметь индекс C из n по x.
Согласно линейности, получаем сумму по
i от 1 до C из n по x MYx,i
просто за счёт линейности математического ожидания,
а мат ожидание Yx,i — это просто вероятность того,
что конкретная подсарделька образует независимое множество в случайном графе.
Так, товарищи, я не очень гоню?
По-моему, не очень, но я надеюсь.
Значит, нам нужно понять, с какой вероятностью вот эта
конкретная штука является полной дыркой, в ней нет ни одного ребра.
Но сколько всего рёбер на множестве из x вершин?
Ясное дело, C из x по 2.
Всего рёбер, конечно, C из x по 2, и каждое из них должно отсутствовать,
то есть мы получаем сумму по i от 1 до C из n по x вероятностей того,
что отсутствуют C из x по 2 конкретных рёбер.
Отсутствие ребра имеет вероятность 1 − p,
всего отсутствующих рёбер, как я уже сказал, C из x по 2, но, значит,
вероятность того, что все они отсутствуют, это (1 − p) в степени C из x по 2.
эта величина никак не зависит от i, получаем C из n
по x * (1 − p) в степени C из x по 2.
Мат ожидание сосчитали.
Теперь смотрите, я выберу сейчас совершено конкретный параметр x,
подставлю его в эту формулу, оценю сверху,
получу некоторую нижнюю оценку интересующей меня вероятности,
и в итоге у меня будет нечто похожее на то, что написано здесь, в верхней строчке.
Верхнюю строчку, товарищи, умоляю, не забывайте, мы к ней обязательно вернёмся,
она скоро сработает, это ружьё выстрелит, вот,
а из этого говорю — сейчас выберем параметр x и получим такую же штуку.
Потом сосчитаем их вместе, и будет катарсис.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
