Так, друзья, давайте этот факт запомним, запомним,
что α(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²,
то непременно стремление к нулю появится.
Вот подумайте пока, какое будет хроматическое число.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
