Ну и давайте 5-ый пункт нашего обзора так сказать,
который мы в рамках этой лекции пытаемся сделать.
5-ый пункт- мы резко подскочим, мы не будем рассматривать больше никакие
промежуточные ситуации, а подскочим сразу до случая, когда p — это константа,
причем в точности равная ½ Вот что будет в этом случае, когда p равняется ½?
Ну смотрите, вообще-то мы сегодня доказали,
мы сегодня доказали, буквально в этой лекции,
доказали что асимптотически почти наверное α
от G не превосходит 2 log² n.
Это мы сегодня доказали.
Так.
Почти наверное.
Ну отсюда конечно следует, что асимптотически почти наверное
хроматическое число случайного графа с вероятностью ребра
½ ⩾ n поделить на 2 log² n.
Это мы тоже сегодня упоминали.
Это неравенство которое как выяснилось гораздо более сильное,
нежели оценка снизу величиной ω.
Мы доказали, что вот такая оценка лучше,
гораздо лучше — тем самым ответив на вопрос из прошлой лекции, но,
сейчас окажется что этот, в общем-то простенький результат на который мы не
затратили никаких особенных усилий, является не только лучшим,
нежели оценка X от G ⩾ ω, но и асимптотически не
улучшаемым — а именно есть еще одна тоже совершенно
нетривиальная теорема всё того же Боллобаша.
Также доказанная им с помощью пресловутой «мартингальной» техники в 80-ые годы,
более или менее тогда же когда и теорема, упомянутая только что.
Теорема утверждает, грубо говоря, давайте я сначала грубо сформулирую,
чтобы не запугать слушателей какими-то там формулами, а теорема утверждает так:
асимптотически почти наверное хроматическое число случайного
графа не только ⩾ этой величины, но и асимптотически её не превосходит.
То есть, в итоге просто асимптотически равно n поделить на 2² log n.
Вот такое вот замечательное утверждение.
Давайте я поясню всё-таки, строгую формулировку дам Чтобы не было
вопросов у тех, кто хочет понять здесь аккуратную математику,
значит строгая формулировка звучит следующим образом: существует
такая функция φ что φ от n равняется
o маленькое от n поделить на log² n,
ну то есть она мала в сравнении вот с этой величиной и такая,
что с вероятностью стремящейся к единице модуль
разности хроматического числа и величины
n поделить на 2 log² n не превосходит φ от n,
вот это с вероятностью стремящейся к единице при
n стремящемся к бесконечности, такой вот замечательный результат.
То есть хроматическое число опять-таки плотно сконцентрировано,
так же как это было в случае предыдущем, в разреженной ситуации,
оно на сей раз плотно сконцентрировано около величины n поделить на 2 log ² n, а
плотность концентрации меряется величиной вот этой функции φ от n, которая маленькая
в сравнении с той величиной около которой хроматическое число сконцентрировано.
Значит хроматическое число действительно в асимптотике ведёт себя вот так,
а уклонение от этой величины, на величину не больше чем
φ от n происходит с вероятностью стремящейся к единице.
Вот.
Конечно здесь плотность концентрации не столь впечатляющая как в первой
теореме Боллобаша, потому что φ от n будучи функцией маленькой в сравнении с
главным членом асимптотики, вовсе не обязана быть константой.
φ от n вполне может стремиться к бесконечности и вопрос о том как именно
себя ведёт эта функция φ от n в оптимальной оценке — это вопрос открытый,
то есть тут разбираться ещё и разбираться.
Но тем не менее, концентрация присутствует.
И это очень круто.
Оказывается; вот ещё раз, товарищи практики!
Я к вам обращаюсь в том числе.
Оказывается, что для типичного графа, а ведь при p равном ½,
случайность это просто классическая вероятность.
Вот для типичного, для почти всякого графа, оценка величиной n поделить на
α гораздо лучше, во-первых, чем оценка величиной ω и более того,
мало того что она лучше, она почти всегда неулучшаема.
Это замечательная оценка.
Не чурайтесь её пожалуйста.
Очень хороший результат.
И вот это вот как раз об этом вот говорит теорема Боллобаша.