Раз нас такой катарсис тут подстерег неожиданно.
Так...
Пункт один.
Давайте я его перенесу на новую доску, чтоб как-то это дело,
ну, выделить все-таки, ну, мы перешли к новому пункту.
Теперь у нас p — это c логарифм n поделить на n, и c строго > 1.
Давайте сразу заметим, что пресловутая
величина n помножить на (1 − p) в n −1 степени,
которое, как мы знаем из доказательства пункта 2, служит, по сути,
математическим ожиданием числа изолированных вершин.
Вот эта величина в данном режиме к бесконечности не стремится.
Давайте еще раз напишем, что там получается.
Получается вот так: n / n в степени c (1 +o малое от 1).
Это мы с вами уже проходили.
Зачем я буду заново это доказывать?
Это в точности доказывается так же, но теперь у нас c не <1, а строго >1.
То есть, начиная с некоторого момента, произведение c (1 +
o малое от 1) — это величина, которая строго >1.
Строго >1.
Отделена от 1 некоторой константой.
Но тогда n, поделенное на n вот в этой степени,
это n поделенное на n в какой-то степени >1.
То есть эта дробь очевидно в этом режиме стремится к нулю.
Сколь бы близким к 1 c ни было, если c — это константа строго >1,
то здесь имеет место стремление к 0 при n, стремящемся к бесконечности.
Давайте я даже попробую некоторую суть, суть вам здесь продемонстрировать,
а потом уже будем заниматься какими-то голыми страшными расчетами.
Суть такая: конечно, мы снова можем взять...
Вот воспринимайте это не как доказательство,
а как некое общее рассуждение.
Друзья, вот вдумайтесь, сейчас не будет доказательства,
сейчас будет некое «показательство», некая идея.
Конечно, мы могли бы снова взять в качестве случайной величины ξ —
число изолированных вершин.
Ну, давайте на минуту допустим, что нам действительно захотелось так сделать.
Тогда смотрите, вероятность того,
что ξ ≥1,
мы такую вероятность оценивали в рамках пункта 2 с помощью неравенства Чебышева.
Конечно, эту вероятность можно оценить и с помощью неравенства Маркова,
причем оценка будет не снизу, как это у нас было в предыдущем пункте, а сверху.
Эта оценка с помощью неравенства Маркова величиной математическое ожидание ξ / 1.
Ну, делить на 1, это я просто, чтобы вы понимали,
как применяется неравенство Маркова в этом месте.
Ну, конечно, делить на 1 не нужно.
Вот.
У нас бы получилось n (1 − p) в (n − 1)-й, и это
благополучно в данной ситуации стремится к 0, при n, стремящимся к бесконечности.
То есть получается,
что асимптотически почти наверное в графе нет изолированных вершин.
Оно бы замечательно, да только ничего из этого не следует.
Потому что нам-то нужно доказать, что почти наверное граф связен,
а то, что в нем отсутствуют изолированные вершины с высокой вероятностью,
это пока ничего не объясняет.
Мало ли нет изолированных вершин!
А может быть, вот как мы уже говорили, когда только начали доказывать теорему,
может быть, граф разваливается на две отдельных компоненты,
каждая из которых огромная, там, по n пополам вершина.
Может такое быть, вполне.
Но вот нет.
Некоторым образом сейчас окажется, что самое главное слагаемое
среди всех слагаемых, которые отвечают за компоненты связности случайного графа,
это как раз слагаемое, про которое мы уже знаем, что оно стремится к 0.
Слагаемое, равное количеству изолированных вершин.
Дальше мы посчитаем количество компонент связности на 2-х вершинах,
количество компонент связности на 3-х вершинах, на 4-х и так далее.
И убедимся в том, что среднее число таких количеств,
среднее число этих случайных величин, оно еще намного меньше.
Настолько меньше, что даже в сумме получится мало.
Ну, имеющий уши, что называется, да слышит.
То есть я вовсе не утверждаю, что вот эта моя речь, которую я сейчас произнес,
была абсолютно всем понятна.
Сейчас мы сделаем формальное доказательство,
и все будет совершенно замечательно и здорово.
Давайте я отделю вот эти общие рассуждения, зерна,
так сказать, от плевел и буду рассказывать формальное доказательство.