Но доказательство его совершенно стандартно,
доказательство этого результата фактически мы рассказывали на прошлой лекции,
только на прошлой лекции мы разбирали случай, когда 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).
Вот такой вот замечательный совершенно результат получился у нас с вами.