Так, друзья, давайте этот факт запомним, запомним, что α(G) у нас почти наверняка не превосходит удвоенного двоичного логарифма, и мы обязательно этим еще воспользуемся в дальнейшем, когда будем обсуждать алгоритмические аспекты отыскания чисел независимости, кликовых чисел и хроматических чисел графа. Мне кажется, это одна из очень важных, в том числе прикладных тем, о которых мы обязательно здесь поговорим, но это не на сегодняшней лекции. Сейчас я хочу с вами обсудить, а, вообще, все-таки как устроены числа независимости и хроматические числа случайных графов при различных p? Так, давайте, наверное, обратимся прежде всего к хроматическому числу, и я попробую пробежаться по каким-то ситуациям, которые ну достаточно просты, которые можно, в общем, обсуждать как, если угодно, упражнения на теорию случайных графов. Значит, следующая тема, которую я сейчас хочу осветить, после того как мы разобрались с этими оценками, это тема, собственно, «Хроматическое число хроматическое число случайного графа». Это безумно красивая тема, про которую можно рассуждать исключительно долго, но я думаю, что мы сделаем так: в рамках такого общечеловеческого курса, который, я считаю, ну вот всякому полезно прослушать абсолютно, я расскажу только какие-то наиболее значимые вещи, касающиеся хроматического числа случайного графа. А вот в рамках какой-то модификации этого курса, в который, возможно, я расскажу более глубокие теоремы, нежели те, которые удастся уложить вот в такой общечеловеческий курс, я докажу некоторые из тех результатов, которые сегодня исключительно заявлю и, может быть, как-то прокомментирую, а вот там я их докажу. Но давайте вот в нашем нынешнем курсе просто пробежимся по тем ситуациям, в которых легко разобраться, и потом как-то чиркнем по поверхности, затронем суть того, что происходит в более сложных ситуациях. Но повторяю, тема безумно красивая, и тут есть чем заниматься и исследователю, и практику. Значит, ну давайте рассмотрим совсем простую первую ситуацию. Предположим, что у нас вероятность ребра p маленькое от n — это очень быстро стремящаяся к нулю функция, совсем крошечная вероятность у каждого ребра. Давайте предположим, что она вообще o малое от 1/n². Ну или, что то же самое, если p(n) умножить на n², то даже такое произведение будет стремиться к нулю с ростом n. Что тогда? Как будет устроено хроматическое число? А? Ну я надеюсь, что слушатели, которые сейчас задумаются, они легко сообразят. Ну, действительно, давайте обозначим X(G) — просто число ребер, просто число ребер в случайном графе G. У этой величины совершенно легко с помощью линейности посчитать математическое ожидание. Математическое ожидание X — это просто C из n по 2 умножить на p. Понятно: всего C из n по 2 ребер, и каждое тестируем на попадание в случайный граф. Естественно, эта величина ведет себя как n²/2 × p. Ну и мы только что сказали, что p устроено таким образом, что едва ты его умножишь на n² и ты получишь функцию, которая все равно стремится к нулю при n, стремящемся к бесконечности. Но это означает согласно нашему любимому и уже ставшему совершенно стандартным неравенству Маркова, что с вероятностью, стремящейся к нулю, X больше либо равняется единице, а стало быть с вероятностью стремящейся к единице, X равняется нулю. Ну то есть в случайном графе с высокой вероятностью нету ребер вовсе. Но если в случайном графе вовсе нету ребер, то он сам из себя представляет независимое множество, ну которое, естественно, можно покрасить одним цветом. Таким образом, мы можем сказать, что вот в этой ситуации асимптотически почти наверное хроматическое число случайного графа не превосходит единицы, ну а стало быть ей равняется. То есть это совсем простенькая ситуация. Вот давайте, покуда я буду перемещаться на чистую доску, вы на мгновение задумайтесь (для вас-то это будет мгновение, вам ничего стирать не надо), вы на мгновение задумаетесь и попробуете ответить на вопрос заранее, на тот, на который я отвечу на чистой доске: а что будет... Давайте здесь будет второй пункт. Я его потом перепишу снова. Что будет, если p(n) чуть-чуть помедленнее стремится к нулю, а именно ведет себя как o маленькое от 1/n. Конечно, в эти ситуации укладывается и это тоже. То есть хроматическое число может равняться единице. Но, как видите, все-таки p уже не столь быстро, вообще говоря, стремится к нулю. Мы лишь знаем, что если p умножить на n, то у нас получится стремление к нулю, но мы не утверждаем, что если p умножить на n², то непременно стремление к нулю появится. Вот подумайте пока, какое будет хроматическое число.
