Осталось сделать один совершенно гениальный шаг — поправить граф G.
Мы доказали, что он существует.
Давайте исправим граф G, перейдем от него к некоторому новому графу G'.
Сейчас объясню, как.
Итак, мы нашли граф G с очень-очень большим, вообще говоря,
количеством вершин, который одновременно имеет маленькое число независимости и в
котором мало вредоносных циклов.
Ну давайте сделаем так: удалим из
каждого вредоносного цикла...
Я напишу просто «вред.
цикла».
Из каждого вредоносного цикла любую какую-нибудь вершину,
какую-нибудь вершину, совершенно произвольную.
Какую-нибудь вершину.
То есть вот был граф G, давайте я нарисую картину,
в нем было несколько коротких циклов, каждый из которых вредил.
Ну, если эти циклы пересекались, вообще говоря,
мы могли постараться и, удалив одну вершину, разрушить сразу несколько циклов.
Но мы плюем на эту возможность.
Мы говорим так: давайте наобум лазаря выкинем вершину из первого плохого цикла.
Опять наобум лазаря выкинем вершину из второго плохого цикла,
из третьего и так далее.
Но мы точно знаем, что в нашем исходном графе G плохих циклов мало,
меньше, чем n / 2.
Поэтому как бы много вершин мы ни удаляли, но больше,
чем n / 2 вершин мы точно не удалим.
То есть это означает, что...
Давайте я вот здесь буду писать уже.
Что у G' не менее или даже более строго n / 2 вершин.
Мы из каждого вредного цикла в графе G удалили вершину,
но у графа G было n вершин, а вредных циклов было меньше, чем n / 2.
Поэтому, удаляя даже по вершине по отдельной из каждого цикла,
мы все равно получаем, что на выходе остается граф, у которого не меньше никак,
чем n / 2 вершин.
Это-то уж точно.
При этом понятно, что обхват
этого нового графа больше, чем l, потому что в исходном
графе было мало вредоносных циклов, а в новом графе их просто нет.
Мы же разрушили каждый вредоносный цикл.
Мы из каждого вредного цикла удалили вершину,
новые вредные циклы появиться никак не могли в результате этой процедуры.
Значит у нового графа по-прежнему достаточно много вершин,
но обхват, слава богу, уже такой, как нам хотелось бы, то есть >, чем l.
Теперь.
Очевидно, что α (G') не могло вырасти по отношению к α (G).
Мы удаляли вершины.
Естественно...
вот здесь вот мы удаляли вершины, да?
Естественно, вместе со всеми ребрами, которые к ним примыкали.
Поэтому число независимости вырасти никак не могло.
α (G') не превосходит α (G), которое, как мы знаем, < x.
Замечательно.
Но отсюда, в свою очередь, следует, и я уже об этом фактически говорил,
что χ (G') ≥ количество вершин в этом графе поделить на его число независимости,
а это, в свою очередь, ≥ (n/2) / x, потому что α < x.
Можно даже строго > написать в этом месте.
Потрясающе!
Это асимптотически равно...
Мы же знаем, чему асимптотически равен x.
n / 2x, где x — это (3 логарифм n) / p.
Правильно?
Это асимптотика для x.
То есть мы получаем np / 6 * логарифмов n.
Вспоминаем, что p выбиралось как n в степени (θ − 1),
то есть получаем n в степени θ.
p — это n в степени (θ − 1), поэтому произведение — это как раз n в степени θ.
Поделить на 6 логарифмов n.
θ у нас равняется 1 / 2l.
Вот тут еще очень важный момент.
l — это может быть огромнейшее число.
Но оно от n никак не зависит.
Это заранее зафиксированная константа.
Поэтому тут у нас стоит функция в числителе,
которая растет как n в степени «некоторое фиксированное положительное число»,
а в знаменателе стоит 6 логарифмов n.
Я думаю, слушатели знакомы с анализом до такой степени,
чтобы понимать, что вот эта функция, сколь бы маленьким фиксированным θ ни было,
растет быстрее все-таки, чем логарифм.
Поэтому вот это вот стремится к бесконечности,
коль скоро n неограниченно возрастает.
Вот это отношение стремится к бесконечности,
каким бы мы заранее ни зафиксировали l.
Пусть огромным, но стремление к бесконечности все равно будет.
Это означает, что существует такое n3,
что для любого n ≥ максимума из n1,
n2, n3 g (G'),
конечно, больше, чем l, это мы уже получили по построению.
Но более того, χ (G'), которое стремится к бесконечности,
после вот этого n3 >, чем заданное наперед k.
Ведь повторяю, k — это была константа, а тут у нас рост к бесконечности.
Значит, начиная с некоторого момента,
бесконечно большая функция превзойдет наперед заданное k.
И наступает полный катарсис.
Мы совершенно никак не описали конструкцию графа, тем не менее, мы точно знаем,
что его можно найти.
Он существует, есть такой граф на очень большом количестве вершин,
у которого одновременно нету коротких циклов и большое хроматическое число.
Теорема полностью доказана.