Изменения
Нет описания правки
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
{{Определение
|definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины '''Лучше дать ссылку''' с одним и тем же средним <tex>\lambda</tex>. Положим
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Представлять себе описанный только что процесс можно так. В начальный момент времени есть одна активная частица. Затем она делает <tex>Z_1 \geq 0</tex> (можжет ыть достигнуто, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама перестает быть активной. И так далее. '''Как это связано с формальным определением? Что здесь Y, что Z?''' Данный процесс может как завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.
{{Теорема
|id = th1
}}
{{Определение
|definition='''Ветвящийся процесс на случайном графе.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины с одним и тем же средним '''Что значит с одним и тем же средним?''' <tex>\lambda</tex>. Положим
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
|statement=Рассмотрим модель <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{ c }{n}</tex>.
Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta = \beta(с)</tex>, что а.п.н. размер каждой связной компоненты случайного графа не превосходит <tex>b\ln n</tex>.
Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma = \gamma(c)</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>b\ln n</tex>.'''Что такое b, его же нет в определении?'''
|proof=
Приведем здесь идеи, изложенные А.М. Райгородским [1], основанные на доказательстве Р. Карпа [2]. Данное доказательство может быть, не настолько строгое, как приведенное в [3], однако
отличается лаконичностью и наглядностью.'''Нерабочие ссылки'''
'''Случай <tex>c < 1</tex>'''.
<tex>\thickapprox (</tex>с учетом [[Центральная предельная теорема| центральной предельной теоремы]]) <tex> \thickapprox </tex>
<tex>\int\limits_{\dfrac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \dfrac{1}{\sqrt{2\pi}}e^{-\dfrac{x^2}{2}}\,dx</tex>.
'''выровняй дробь, тут что-то непонятное вообще'''
Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины
<tex>e^{−\delta t_0}</tex>. Выберем <tex>\beta</tex> таким, чтобы <tex>e^{−\delta t_0}</tex> оказалось меньше, чем
<tex>e^{-2 \ln n} = \dfrac{1}{n^2}</tex>, и в случае <tex>c < 1</tex> теорема доказана.
'''Нерабочие ссылки на нирк'''
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичности, их, а также более детальный рассказ можно найти в [4].'''Где найти?'''
{{Утверждение
|statement=Пусть <tex>d > 1</tex>. Тогда вероятность <tex>p</tex>, что <tex>size(cc(v)) = O(\log n)</tex> (<tex>cc</tex> {{---}} компонента связности, содержащая <tex>v</tex>): <tex>p < 1</tex> {{---}} константа.
