Замечательная теорема, которую еще в 70-е годы доказали все те же Балабаш и Эрдеш.
То есть доказали они ее в каком-то смысле задолго до того, как Балабаш придумал свой
гениальный подход подсчета асимптотики хроматического числа случайного графа.
Замечательная теорема говорит следующее: пусть у
случайного графа вероятность ребра равняется 1/2,
то есть у нас все графы в этой модели оказываются равновозможными,
равновероятными с вероятностью 2 в степени минус C из n по 2, как водится.
Вот пусть p = 1/2, тогда оказывается,
что асимптотически почти наверное...
Ну кто у нас кого больше?
Давайте (все время забываю вот здесь вписать для полноты
картины) зафиксируем произвольное ε большее 0, любое,
и вот для любого такого фиксированного ε большего 0
асимптотически почти наверное, так,
обычное хроматическое число поделить на жадное хроматическое число — на χж от G.
Ну понятно, обычное все-таки, наверное, больше, чем та аппроксимация,
которую мы получим.
Или наоборот?
Ой, нет!
Наоборот, конечно!
Жадное-то больше будет.
Ведь жадное — это верхняя оценка для обычного хроматического числа.
Давайте-ка я все-таки вот это ж (маленькое) перенесу наверх.
Конечно, да, χ с индексом ж от G — это верхняя оценка хроматического числа.
Вот я утверждаю,
что асимптотически почти наверное это отношение не превосходит 2 + ε.
То есть почти всякий граф, который на вас «капает» из пресловутой «тучки»,
вообще почти любой граф устроен таким образом, что банальный жадный алгоритм,
запущенный на этом графе, дает оценку хроматического числа не более чем в 2 плюс
какой-то мизер, ну, скажем, две целых, не знаю, одна миллионная, например,
в две целых одну миллионную раза...
Дает оценку, которая не более чем в две целых одну
миллионную раза больше, нежели реальное хроматическое число графа.
На почти всяком графе мы ошибаемся не более чем в 2 раза.
При этом совершенно неважно, у графа, там, тысяча вершин, миллион вершин,
квадриллион вершин — все равно с высокой вероятностью,
очень близкой к 1, мы ошибемся при подсчете с помощью «жадненького» вот
этого хроматического числа не более чем в 2 плюс какой-то мизер раз.
Это совершенно замечательный результат.
И точно так же α от G, наоборот, поделить на α с индексом ж от G (ну,
наоборот, потому что на сей раз все-таки действительно α с индексом ж от G — это у
нас нижняя граница для числа независимости графа) тоже не превосходит 2 + ε.
Сколь бы маленькое ε мы ни зафиксировали, с вероятностью,
стремящейся к 1, ошибка будет не более чем в 2 раза.
То есть если вы действительно допускаете возможность какой-то ошибки,
вероятность которой стремится к 0, то вы можете спокойно применять жадный алгоритм,
и у вас получится вполне адекватная оценка столь
трудно вычислимой характеристики графа.
По-моему, это достаточно впечатляюще.
Вот. Ну давайте, наверное, просто,
не мудрствуя лукаво, перейдем к доказательству вот этого факта.
Он технически несколько проще, а идейно, в общем-то, такой же, как и верхний.
Я верхний доказывать не буду, чтобы не перегромождать эти лекции,
а нижний постараюсь максимально аккуратно доказать.
Он технически не вполне тривиален,
но мы уж постараемся картинок порисовать и разберемся.
На самом деле никаких тут мартингалов не нужно.
Все просто, и все должно получиться.
Давайте перейдем, собственно, к доказательству.