То есть осталось, видите, сколько раз я уже говорил,
осталось, но на сей раз, действительно, осталось совсем чуть-чуть.
Осталось доказать, что для любого t в пределах от 1 до k,
просто для каждого фиксированного t,
величина C из n − k по k
− t поделить на C из n по k,
вот эта величина...
А! Не эта величина,
а еще умноженная на p в степени −lt на k,
вот эта величина стремится к нулю при n, стремящемся к плюс бесконечности.
Тут уж если я это докажу, то все, я в героях, мы с вами в героях,
и теорема доказана, все вообще замечательно.
Но это, правда, легко.
Смотрите, давайте вспомним, что у нас p в данной ситуации
— это ω на n в степени −k/l, мы ж так выбирали нашу вероятность ребра.
С самого начала это условия, в которых мы находимся.
Ну значит, величина, которая здесь написана,
это C из n − k по k − t на C из n
по k на ω в какой-то там...
так, щас, щас, щас, щас, щас...
в какой степени?
Как бы мне тут только не провраться...
Нет, все хорошо, все хорошо.
Значит, ω мы возводим в степень −lt/k, и, честно говоря,
мне плевать, на самом деле, в какую степень я эту ω возвожу.
Сейчас вы поймете, что это дело действительно непринципиально,
а самое важное — это вот эта вот часть.
Видите, как все замечательно,
как все подгадано: n в степени −k/l возводится в степень −l/k, да?
Как замечательно.
То есть у нас получается просто n в какой степени?
−k/l помножить на −l/k — это просто 1, то есть остается n в степени t.
Ну потрясающе.
Значит, а может и не плевать, может и не плевать.
Не-не, все замечательно, все замечательно, смотрите.
Значит, все-все-все, сейчас все будет, вот.
Это правильно, да?
Никого не обманул?
Вроде никого не обманул.
Смотрите, ωn в степени −k/l, возвожу эту штуку в степень −l/k на t.
Значит, ω возводится просто в степень −l...
lt на k, lt на k.
Вот.
А n в степени −k/l, в степени −l/k дает 1, ну и еще остается в степени t.
Ага, ну давайте поймем, как себя ведет асимптотически каждая из C-шек,
написанных в числителе и в знаменателе соответственно.
Ну мы сегодня уже такую штуку проделывали.
Значит, в числителе написано n в степени k − t поделить на k − t факториал,
в знаменателе написано n в степени k поделить на k факториал,
поэтому k факториал пошел в числитель, вот тот, который здесь был в знаменателе
за счет стандартной асимптотики для C из n по k при постоянном k.
Так, дальше у нас по-прежнему остается ω в
−lt на k-той и n в степени t.
Так, ну это ж потрясающе просто, смотрите.
n в степени k − t и n в степени t в произведении дают n в степени k,
делим это на n в степени k, и, как обычно, шлеп,
шлеп, шлеп — все благополучно сократилось.
Я вас уже замучал рассуждениями о том, что константа, что не константа,
ну елки-палки, ну k факториал и k − t факториал это же константы.
То есть вот это вот никак не влияет на асимптотику, правильно?
Правильно.
А t у нас начинается от 1, t не может равняться нулю.
Ну и l, конечно, не может равняться нулю, это мы с вами понимаем,
l равняться нулю не может, иначе о какой плотности мы бы вообще говорили?
Поэтому ω здесь возводится в какую-то конкретную отрицательную степень,
в конкретную отрицательную степень.
Но ω — это функция, которая по условию стремится к плюс бесконечности, значит,
ω, возведенная в отрицательную степень, благополучно стремится к нулю.
Фу, теорема-то доказана.
Товарищи, я вас поздравляю.
Мне кажется, что все очень даже неплохо получилось, вот.
Я думаю, что какое-то развитие этой идеи,
этой идеологии мы обязательно пронаблюдаем в еще одном курсе, который я скоро сделаю.
Это курс по моделированию сложных сетей, например, веб-графов,
социальных сетей и прочих им подобных.
И там очень важно будет понимать, как вот это вот все устроено.
И там мы поговорим о том, как это устроено в других случайных графах,
отличных от случайного графа Эрдеша-Реньи, но вот это вот,
вот эти результаты нам будут очень полезны.
Кроме того, я думаю, что в домашней работе, которая последует, естественно,
за этой лекцией, мы поговорим еще об одной очень забавной теме, которая связана с
вхождениями графов фиксированных в случайные графы,
но я не думаю, что здесь стоит ее так в подробностях,
по крайней мере в рамках вот этого короткого варианта курса, освещать.
Возможно, если у меня будет, действительно,
шанс прочитать удлиненный вариант этого курса, а я уже подготовился к этому тоже,
в рамках немножко другой программы, то и об этом [НЕРАЗБОРЧИВО],
на домашнюю работу оставим, вот я тоже расскажу, это очень красиво.
Вот. Ну а так, все, товарищи,
немножко про случайные графы поговорили, поняли как они устроены,
и я надеюсь, что это в общем пошло на пользу.