Ну что, друзья, было у вас хоть полсекунды подумать над второй ситуацией?
Давайте еще вам полсекунды дам, напишу ее снова.
Значит, вторая ситуация — это когда у нас p(n) = o(1/n).
То есть ребра-то в графе уже есть, скорее всего.
Это значит, что хроматическое число не должно равняться единице,
только если мы не оказались в рамках первой ситуации, как в следствии.
Но насколько больше единицы?
Ладно, все, томить больше не буду, утверждение такое: асимптотически
почти наверное хроматическое число случайного графа не превосходит 2.
Ну для того, чтобы это доказать, я могу, конечно,
процитировать критерий двудольности графа,
который в курсе графов у нас уж во всяком случае есть.
Ну если кто-то не слушал наш курс графов,
отчаиваться он или она не должны, потому что ну, понятно,
что это простая вещь: граф является двудольным, то есть красится в два цвета.
Двудольный имеет хроматическое число, не большее 2, — это, по сути, одно и то же.
Граф двудолен, — давайте я это напишу,
— граф двудолен тогда и только тогда,
когда в нем нет нечетных простых циклов.
Очень понятный критерий, но замечательно на
самом деле то, что в данной ситуации даже этот критерий не нужен.
Я утверждаю, что верно большее.
Утверждение, которое я сейчас напишу, такое: асимптотически
почти наверное в текущей ситуации случайный граф является лесом.
Ну то есть каждая его компонента — это дерево, ну а дерево-то очевидно двудольно.
Понятно, что дерево можно покрасить в два цвета правильным образом,
так чтобы концы любого ребра имели разные цвета.
Так вот асимптотически почти наверное G является лесом, ну или,
что то же самое, то есть вовсе не содержит никаких циклов.
Связным он не обязан являться, но мы знаем, у нас эта теорема есть,
мы доказывали, что в этом режиме граф, скорее всего, не связен.
Более того, он разваливается на отдельные крошечные компоненты,
сейчас я про это поговорю.
Но мы можем утверждать, что циклов в нем нет.
Что там асимптотически почти наверное граф является лесом,
то есть в нем вовсе нет циклов,
вовсе нет циклов никаких — ни четных, ни нечетных, никаких.
Давайте, прежде чем я докажу это утверждение действительно в свете вот
этого замечательного факта,
который вроде бы я привожу для доказательства вот этого результата,
— давайте я в свете этого замечательного факта еще раз прокомментирую теорему о
гигантской компоненте, которая у нас формулировалась еще на первой лекции.
Помните, там ведь было такое утверждение, что если P P = c/n,
где c < 1, то асимптотически почти наверное
все связные компоненты случайного графа имеют очень мало вершин: каждая, каждая
такая компонента содержит логарифмическое, по сути, количество вершин.
Асимптотически почти наверное размер, то есть число вершин каждой
связной компоненты, каждой связной
компоненты не превосходит там какой-то константы,
общей для всех этих компонент, помножить на логарифм, ну скажем,
двоичный n или натуральный, это неважно, от этого зависит только константа.
Ну вот, значит, количество вершин в каждой связной компоненте не превосходит
константы умножить на логарифм n.
Я это комментировал в таких стратегических терминах, как — исторических, вернее,
— как феодализм: что у нас граф представляет собой такое вот феодальное
явление, феодальную раздробленность, когда все связные компоненты крошечные.
Так вот в свете этого утверждения появляется информация о том,
как они на самом деле устроены.
Оказывается, что все вот эти замечательные связные компоненточки — это просто
деревья, маленькие такие, маленькие деревца.
В графе почти наверное нет циклов.
Этого мы не доказывали.
Мы только формулировали вот этот замечательный результат,
что на самом деле крошечные компоненты, феоды вот эти, являются, по сути,
деревьями, скорее всего, с высокой вероятностью.
Вот это мы узнаем только сейчас, и выведем отсюда как следствие,
что хроматическое число не превосходит 2.
Видите, сути много, пафоса много, а доказательство очень простое.