436
правок
Изменения
м
small changes
|about=о гигантской компоненте
|statement=Рассмотрим модель <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{ c }{n}</tex>.
: Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta</tex>, зависящая от <tex>c</tex>, что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит <tex>\beta \ln n</tex>.: Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma</tex>, зависящая от <tex>c</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>\beta \ln n</tex>.
|proof=
Приведем здесь идеи<ref>Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7</ref>, изложенные А.М. Райгородским, основанные на доказательстве<ref>Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.</ref> Р. Карпа. Такой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в <ref name="trueproof">Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.</ref>.
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta</tex> {{---}} константа, которая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер <tex>\le t_0</tex>.
Но размер компоненты {{---}} это момент вырождения процесса <tex>Y_t</tex> на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде: <tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \rightarrow 0, n \rightarrow \infty</tex>
Поскольку <tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \le nP_{n, p}(Y_{t_0} \ge 0)</tex>, достаточно найти такое <tex>\beta</tex>, при котором <tex>P_{n, p}(Y_{t_0} > 0) = o\left(\frac{1}{n}\right).</tex><br>
<br>
: <tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} > t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) > t_0) \thickapprox</tex><br>: (с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>: <tex>\thickapprox P_{n, p}(Binomial(n, pt_0) > t_0) \thickapprox</tex><br>: (с учетом центральной предельной теоремы) <br>: <tex> \thickapprox \int\limits_{\frac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx</tex>.
Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины
Применим центральную предельную теорему к
<tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
Пределы интегрирования в данном случае: от <tex>-\infty</tex> lj до <tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
Если <tex>\alpha < 1 - e^{-c\alpha}</tex>, то мы получим искомое стремление вероятности к нулю.
