Но доказательство его совершенно стандартно, доказательство этого результата фактически мы рассказывали на прошлой лекции, только на прошлой лекции мы разбирали случай, когда p = не 1 / 2, а какой-то там загадочной величине n в степени θ − 1, и тогда там логарифм брался тоже по какому-то другому основанию, было там, помните, логарифм n / p какая-то там целая часть, 3 еще в числителе. Ну это все, ладно, чего я, собственно, болтаю, давайте, действительно, воспроизведем доказательство. Так, вероятность того, что α(G), давайте я даже напишу < строго, чем 2log двоичный n — это будет только более сильное утверждение, то есть, я сейчас стремлюсь доказать, что вероятность даже вот этого события стремится к 1, коль скоро n неограниченно возрастает. Ну из этого, конечно, будет следовать то, что я написал. Значит, вероятность того, что α(G) < чем 2 двоичных логарифма n, это, как и на прошлой лекции, вероятность того, что независимые множества вот такого размера в случайном графе отсутствуют. Ну, я вот сейчас задумался, я было собирался вот так написать, но, понимаете, вот это число нецелое. И если я сейчас хочу сказать, что у меня отсутствуют независимые множества в точности такого размера, то это будет не очень хорошо. Ну давайте я нарисую здесь целую часть, так будет точно понятнее, и уж во всяком случае по-прежнему правильно, потому что целая часть в свою очередь не превосходит своего аргумента, то есть удвоенного двоичного логарифма. Значит нам надо доказать, что вот эта вероятность стремится к 1. Ну, давайте обозначим временно вот эту штучку x, как на прошлой лекции, тогда у нас получится вероятность того, что Y с индексом x от G = 0, где, вспоминаете, что такое Yx(G)? Значит, Yx(G) — это количество независимых множеств размера x в случайном графе G, ну я, конечно, напишу это сейчас. Значит, Yx(G) — это количество независимых множеств в случайном графе G. Математическое ожидание Y с индексом x мы благополучно считали на прошлой лекции, поэтому я могу его радостно написать. Значит, оно считалось вот так: C из n по x на 1 − p в степени C из x по 2. Я могу только вкратце напомнить, что вот это вот за счет линейности — количество просто тех множеств, каждое из которых мы тестируем. 1 − p — это вероятность отсутствия ребра, но p у нас равняется 1 / 2 сейчас. Я просто так написал, чтоб вы вспомнили, что у нас было на прошлой лекции. А C из x по 2 — это количество тех ребер, которые должны отсутствовать, коль скоро мы зафиксировали конкретное x-элементное множество и тестируем его на независимость. Вот, ну давайте перепишем так, как это будет соответствовать текущей ситуации, то есть, сюда напишем 1 / 2. 1 / 2 в степени C из x по 2 — это то же самое, что 2 в степени −C из x по 2, просто так перерисовал. И что я хочу доказать? А я хочу доказать, что вот эта величина при текущем выборе параметра x, то есть целая часть 2log двоичных n, вот эта величина стремится к 0 при n, стремящемся к бесконечности, потому что я смогу применить неравенство Маркова. Ну, всему свое время. Значит, оцениваем стандартно, как n в степени x / на x факториал × 2 в степени −x × (x − 1) / 2. И товарищи, которые хорошо помнят прошлую лекцию, они скажут: а вы же пренебрегли вот этим факториалом в знаменателе. Но на той лекции пренебрег, а сейчас не хочу, сейчас он мне поможет, потому что я хочу вот именно такое неравенство получить, как здесь написано, и вот мне этот x факториал сейчас будет исключительно полезен. Так, ну давайте напишем 2 в степени x на log двоичный n − x квадрат / 2 + x / 2. Собственно вот этот паразитический + x / 2 мне и нужно будет загасить, так сказать, с помощью факториала, который стоит в знаменателе. Давайте разделим на факториал стало быть, то есть, им пренебрегать не будем пока я просто написал точное равенство. Ну и давайте вместо x честно подставлять целую часть от удвоенного двоичного логарифма. Так, смотрите, давайте я вот здесь наверное это напишу сейчас аккуратненько. Смотрите, целая часть от удвоенного двоичного логарифма n, конечно, как я уже неоднократно говорил, не превосходит своего аргумента, но с другой стороны, она же ≥ того же самого аргумента без 1. То есть, целая часть лежит в пределах от арумента уменьшенного на 1 до самого этого аргумента. И я этим сейчас аккуратненько воспользуюсь. Вот здесь x идет со знаком +, поэтому я буду пользоваться неравенством оценкой сверху. Значит, у меня получится 2 в степени 2log двоичный в квадрате n. А вот здесь он идет со знаком −, поэтому я воспользуюсь нижней оценкой, я скажу, что логарифм ≥, нежели логарифм − 1. И со знаком «−» продолжу в правильную сторону неравенство, получится ≤. Так, ну конечно, я размахнулся, у меня вот здесь места сейчас не хватит на это вычитание, ну да ладно, ничего страшного. Давайте как бы нам это лучше сделать... Нет, мне это не нравится, давайте я сейчас вот так вот это аккуратненько сотру и сюда перейду, а то у меня места не хватит. Так, 2 в степени — еще раз подставляю оценку — 2log двоичный в квадрате n — это я пока оценил x — дальше с минусом у меня идет 1 / 2 × 2 log двоичный n − 1 в квадрате. Ну и с плюсом, собственно, идет опять удвоенный двоичный логарифм, который мы делим пополам. Вот такая вот штука. Ну вы видите сейчас, что у меня здесь места просто никак бы не хватило, поэтому я вовремя спохватился и написал понятную запись, а то было бы некрасиво. Так, теперь давайте раскрывать скобки вот в этой замечательной формуле. Что такое 2 логарифм двоичный n − 1 в квадрате? Ну во-первых, надо в квадрат возвести вот эту величину — будет 4log в квадрате n пополам. Пишем. А, виноват, забыл еще поделить на x факториал, это очень важно. Так, получится 2 в степени 2log двоичный в квадрате n, и здесь, как мы выяснили, вычитается, ой, какая удача, тот же самый удвоенный двоичный логарифм в квадрате. Такая вот удивительная вещь: вычитается-то он же. Ну смотрите, с минусом идет удвоенное произведение, оно делится пополам, то есть, в итоге с плюсом идет у меня, а что у меня идет с плюсом? Логарифм двоичный n. И еще раз он идет с плюсом. У меня получается 2log двоичный n, ну и еще вот эта вот −1 / 2. Ну −1 / 2, она вообще никакой роли не играет, давайте я напишу ≤ и не буду таскать ее за собой, потому что −1 / 2 это только <. Вот, замечательно. Ну и, конечно, все надо поделить на x факториал. Наконец можно радостно сделать «шлеп»- «шлеп», я очень люблю этот момент, когда все сокращается, как в тетрисе, вот, они так провалились. И у нас получилось выражение: 2 в степени 2 двоичных логарифма n поделить на x факториал. Ну так, друзья, x-то факториал растет гораздо быстрее, чем 2 в степени x, но тут стоит примерно 2 в степени x, а тут стоит примерно x в степени x. Ну я не знаю, можно воспользоваться, например, неравенством x факториал ≥ x / e в степени x, уж такое неравенство легко доказать просто по индукции — сделайте это как несложное упражнение, и тогда у вас получится какая-то вот такая вот оценка: 2 в степени 2 log двоичный n × e в степени x, то есть, в степени целая часть от 2log двоичный n, и все это поделить на целая часть от 2log двоичный n в степени та же самая целая часть от 2log двоичный n. Вот это все уже какое-то техническое занудство, которое особенного интереса-то не представляет. Тут написана экспонента, видите, в знаменателе стоят константы, а тут растущая функция возводится в такую же степень, в которую здесь возводились константы. Видите, как мне пригодился этот x факториал. Понятно, что с большим запасом это стремится к 0, коль скоро n неограниченно возрастает. И все, значит, мы применяем неравенство Маркова. Вероятность того, что α(G) <, чем x = вероятности того, что Yx(G) = 0 = 1 − вероятность того, что Yx(G) ≥ 1, ну и это ≥ 1 − математическое ожидание x, про которое мы только что выяснили, что оно стремится к 0. Значит, эта разность стремится к 1 при n, стремящемся к бесконечности, и мы действительно доказали, что асимптотически почти наверное число независимости маленькое. Замечательно! Но теперь, все-таки, по поводу кликового числа, то есть, вот этой величины ω(G). Почему на самом деле для нее все то же самое? Ну так, дело в том, что, если Yx будет означать не количество независимых множеств размера x, а количество товарищей клик полных подграфов на x вершинах, так у него будет в точности такое же математическое ожидание при p = 1 / 2. То есть, конечно, оно будет вот таким: C из n по x × p в степени C из x по 2, но при p = 1 / 2 математическое ожидание абсолютно такое же, и дальше читаем прямо по тексту — получаем в точности те же самые неравенства Маркова и опять-таки стремление к 1. То есть, асимптотически почти наверное ω(G) ровно по тем же причинам не превосходит x, по которым его не превосходила только что величина α(G). Вот такой вот замечательный совершенно результат получился у нас с вами.
