Русский перевод препринта. Перевод английской статьи Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees, arXiv:2610.04420v1, опубликованной на arXiv 3 октября 2026 года. Оригинальный источник на arXiv (на английском) · PDF оригинала. При цитировании следует ссылаться на английский оригинал.

Пороги размера начального множества и дисперсия степеней в неоднородной бутстрэп-перколяции с растущими степенями

Александр Родионов Место работы: Яндекс, Санкт-Петербург, Россия Место работы: ORCID: 0009-0006-6710-923X Эл. почта: rexarrior@yandex.ru

Препринт — 29 сентября 2026 года

Аннотация

Мы изучаем бутстрэп-перколяцию с независимыми порогами вершин, принимающими значения один и два, причём вероятность порога один равна $(1-c/d)/d$ при фиксированном $c>0$ . Начальное активное множество выбирается равномерно среди множеств заданного детерминированного размера, независимо от графа и порогов. Мы доказываем утверждения о пороге при фиксированных относительных отступах. Для равномерных простых графов с заданными неотрицательными целочисленными степенями, имеющими чётную сумму и точное среднее $d$ , предположим, что $\max_{i}|d_{i}-d|\leq C\sqrt{d}$ и $c+1-v_{n}\geq\kappa>0$ , где $v_{n}=\operatorname{Var}(D)/d$ , а $C,\kappa$ фиксированы. При $d\to\infty$ и $d=o(n^{1/7})$ ведущий масштаб размера начального множества равен $n(c+1-v_{n})^{2}/(2d^{4})$ ; существование предела $v_{n}$ не требуется. При фиксированных относительных отступах ниже и выше этого масштаба размер итогового активного множества с высокой вероятностью равен соответственно $O(n/d^{3})$ и $n-o(n)$ . Отдельный результат для $G(n,d/n)$ справедлив при $d\to\infty$ и $d^{5}/n\to 0$ и даёт масштаб $nc^{2}/(2d^{4})$ . Таким образом, регулярные графы и графы с независимыми рёбрами имеют разные коэффициенты при одной и той же асимптотической средней степени. Локальные оценки процесса исследования графа дают явные оценки числа оставшихся неактивных вершин и сохраняются при условии простоты графа в модели с заданными степенями. Мы также количественно описываем препятствие, связанное с точностью, для переноса результатов через статическое включение и вычисляем детерминированные поправки к барьеру функции отклика, не устанавливая сужающееся случайное критическое окно.

1 Модель и основные результаты

На конечном простом графе с множеством вершин $[n]=\{1,\ldots,n\}$ начнём с начального активного множества $A_{0}$ и будем последовательно активировать каждую неактивную вершину, имеющую не менее $R_{i}$ активных соседей. Активация необратима; обозначим через $A_{\infty}$ итоговое активное множество. Во всей работе $n\to\infty$ , а логарифмы натуральные. При фиксированном $c>0$ пороги взаимно независимы и независимы от графа, причём

\Pr(R_{i}=1)=\pi=\frac{1-c/d}{d},\qquad\Pr(R_{i}=2)=1-\pi.

(1)

Начальное активное множество независимо от графа и всех порогов и равномерно распределено среди подмножеств заданного детерминированного целочисленного размера $a=a_{n}\in\{0,\ldots,n\}$ . Обозначим $\alpha=a/n$ . Все вероятностные утверждения учитывают случайность графа, порогов и начального активного множества. «С высокой вероятностью» означает «с вероятностью, стремящейся к единице вдоль каждой последовательности, удовлетворяющей указанным предположениям». Оценка $X=O(f_{n})$ с высокой вероятностью означает, что существует фиксированная конечная константа $B$ , для которой $\Pr(X\leq Bf_{n})\to 1$ .

1.1 Избыточная степень и масштаб размера начального множества

Для заданных степеней пусть $D$ имеет эмпирическое распределение степеней, $d=\mathbb{E}D$ , и положим $v_{n}=\operatorname{Var}(D)/d$ . Предположим наличие фиксированного положительного зазора $c+1-v_{n}\geq\kappa>0$ . Тождество для избыточной степени и её дефицит имеют вид

\frac{\mathbb{E}[D(D-1)]}{d}=d-1+v_{n},\qquad b=\frac{c+1-v_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}}.

Таким образом, $b\asymp d^{-1}$ равномерно при фиксированных ограничениях на параметры. Если дополнительно $v_{n}\to v$ , ведущий коэффициент принимает вид $(c+1-v)^{2}/2$ . Основная теорема не требует этой сходимости.

Для регулярных степеней оставшаяся степень равна $d-1$ : ребро, по которому мы пришли в вершину, больше недоступно. Для пуассоновского распределения степеней со средним $d$ взвешивание по степени с последующим удалением ребра входа оставляет среднее $d$ . Эта разница в одно ребро меняет дефицит с $(c+1)/d+O(d^{-2})$ на $c/d$ . Следующий коэффициент отклика равен $K\sim d^{2}$ , что даёт масштаб размера начального множества $b^{2}/(2K)$ и, следовательно, два разных ведущих коэффициента. Приведённые ниже теоремы обосновывают этот детерминированный прогноз.

Для заданных степеней мы количественно уточняем известный процесс исследования графа с экспоненциальными часами на сужающемся масштабе узкого места, получая вероятности ошибок, достаточные для перехода к условию простоты. Для независимых рёбер мы применяем известные аргументы с независимыми метками и максимальными оценками эмпирического процесса к смешанному отклику, получая диапазон $d^{5}/n\to 0$ . Оба аргумента дают оценки итогового состояния при фиксированных относительных отступах.

Полученное различие между регулярной моделью и моделью с независимыми рёбрами строго подтверждает прогноз известных уравнений отклика. Пересечение с приближением на конечном временном горизонте в надкритическом случае при медленно растущих степенях приведено в приложении B. Уточнения с использованием моментов более высоких порядков относятся к детерминированным барьерам, а не к центру случайного критического окна.

1.2 Утверждения о пороге

Определим оценки числа оставшихся неактивных вершин

\mathcal{R}_{\rm P}(n,d,C)=n\bigl[d\,2^{-d+C\sqrt{d}}+n^{-1/3}\bigr],\qquad\mathcal{R}_{\rm E}(n,d)=n\bigl[(1+d)e^{-d/2+d/n}+n^{-1/3}\bigr].

(2)

Теорема 1 (P: заданные степени).

Зафиксируем $c>0$ , $C\geq 0$ , $\kappa>0$ и $\gamma\in(0,1)$ . Пусть $d_{1},\ldots,d_{n}$ — неотрицательные целые числа с чётной суммой $nd$ , где $d=n^{-1}\sum_{i}d_{i}$ — точное среднее. Пусть $D$ имеет эмпирическое распределение степеней, и предположим, что

\max_{i}|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\frac{\operatorname{Var}(D)}{d},\qquad c+1-v_{n}\geq\kappa,

(3)

d\longrightarrow\infty,\qquad d=o(n^{1/7}).

(4)

Положим

b=1-\pi\frac{\mathbb{E}[D(D-1)]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[D(D-1)(D-2)]}{d},\qquad A=\frac{b^{2}}{2K}.

(5)

При всех достаточно больших $n$ последовательность степеней реализуема простым графом, $0<\pi<1$ , $b>0$ и $K>0$ . Для равномерного простого графа с этими степенями при указанных выше правилах выбора порогов и начального активного множества существуют конечные константы $B_{-},B_{+}$ , зависящие только от $c,C,\kappa,\gamma$ , такие, что для каждой последовательности заданных детерминированных размеров начального активного множества

	$\displaystyle a\leq(1-\gamma)nA$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(\|A_{\infty}\|\leq B_{-}n/d^{3}\bigr)\longrightarrow 1,$		(6)
	$\displaystyle a\geq(1+\gamma)nA$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(n-\|A_{\infty}\|\leq B_{+}\mathcal{R}_{\rm P}(n,d,C)\bigr)\longrightarrow 1.$		(7)

Здесь и далее неравенство для $a_{n}$ должно выполняться начиная с некоторого индекса. Сходимость $v_{n}$ не предполагается.

Теорема 2 (E: независимые рёбра).

Зафиксируем $c>0$ и $\gamma\in(0,1)$ , и пусть

d\longrightarrow\infty,\qquad\frac{d^{5}}{n}\longrightarrow 0.

(8)

Возьмём $G\sim G(n,d/n)$ с указанными выше правилами выбора порогов и начального активного множества и положим $A_{\rm E}=c^{2}/(2d^{4})$ и $a_{\rm E}=nA_{\rm E}$ . Существуют конечные константы $B_{-}^{\rm E},B_{+}^{\rm E}$ , зависящие только от $c,\gamma$ , такие, что для каждой последовательности заданных детерминированных размеров начального активного множества

	$\displaystyle a\leq(1-\gamma)a_{\rm E}$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(\|A_{\infty}\|\leq B_{-}^{\rm E}n/d^{3}\bigr)\longrightarrow 1,$		(9)
	$\displaystyle a\geq(1+\gamma)a_{\rm E}$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(n-\|A_{\infty}\|\leq B_{+}^{\rm E}\mathcal{R}_{\rm E}(n,d)\bigr)\longrightarrow 1.$		(10)

Эта теорема рассматривает модель с независимыми рёбрами отдельно, без предположений о заданных степенях из теоремы 1. Здесь $d=np$ параметризует вероятность ребра, а точная ожидаемая степень равна $(n-1)d/n$ .

Обе оценки числа оставшихся неактивных вершин равны $o(n)$ в соответствующих диапазонах, поэтому надкритические выводы дают $|A_{\infty}|/n\to 1$ по вероятности. Они не утверждают ни полной активации, ни наличия сужающегося критического окна. Кванторы по размеру начального активного множества относятся к заданным размерам и независимым равномерным начальным множествам, а не к множествам, выбранным после наблюдения графа или порогов.

Константы.

Параметры модели $c,C,\kappa$ и относительный отступ $\gamma$ фиксированы во всех случаях, где они применимы. Константы в вероятностных оценках для заданных степеней могут зависеть только от $c,C,\kappa,\gamma$ ; в оценках для независимых рёбер — только от $c,\gamma$ . Константы в логарифмическом следствии могут дополнительно зависеть от фиксированного в нём $K_{0}$ . Неуказанные константы могут меняться от оценки к оценке, тогда как параметры модели остаются фиксированными. Индекс, начиная с которого выполняется асимптотическая оценка, может зависеть от выбранной последовательности и скоростей её сходимости; равномерность по таким последовательностям не требуется. В абстрактной лемме о детерминированном барьере константы также могут зависеть от равномерных оценок сравнения и производных и от фиксированного локального интервала. Ни одно из этих утверждений не допускает $\gamma\to 0$ или $\kappa\to 0$ .

Лемма 3 (Эмпирические моменты и перенос при фиксированных отступах).

При условии (3), при фиксированных $c,C,\kappa$ и при $d\to\infty$ положим $q_{n}=c+1-v_{n}$ и $A_{0,n}=q_{n}^{2}/(2d^{4})$ . Для $b,K,A$ из (5) равномерно по этим эмпирическим распределениям

b=\frac{q_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}},\qquad K=d^{2}\bigl(1+O(d^{-1})\bigr),\qquad A=\frac{q_{n}^{2}}{2d^{4}}\bigl(1+O(d^{-1})\bigr).

(11)

Следовательно, (6) и (7) остаются справедливыми при замене $A$ на $A_{0,n}$ для каждого фиксированного относительного отступа (возможно, с изменёнными константами). Если дополнительно $v_{n}\to v$ , то $v<c+1$ и

nA\sim\frac{n(c+1-v)^{2}}{2d^{4}},

(12)

и это предельное выражение также можно использовать вместо $nA$ в выводах с фиксированными отступами. Детерминированные оценки в (11) не требуют соотношения между $n$ и $d$ ; вероятностные выводы сохраняют условие (4).

Следствие 4 (Различие для регулярной модели).

Зафиксируем $c>0$ . Пусть $d=d_{n}$ целое, $nd$ чётно, и предположим, что $d\to\infty$ и $d=o(n^{1/7})$ . Сравним равномерный простой $d$ -регулярный граф и $G(n,d/n)$ при одинаковых правилах выбора порогов и начального активного множества. Их ведущие масштабы размера начального множества равны

t_{\rm R}=\frac{(c+1)^{2}n}{2d^{4}},\qquad t_{\rm E}=\frac{c^{2}n}{2d^{4}},\qquad\frac{t_{\rm R}}{t_{\rm E}}=\frac{(c+1)^{2}}{c^{2}}.

Точнее, для каждого фиксированного $\gamma\in(0,1)$ начальное множество размера ниже $(1-\gamma)t_{\rm R}$ даёт $O(n/d^{3})$ итоговых активных вершин в регулярной модели, тогда как начальное множество размера выше $(1+\gamma)t_{\rm R}$ оставляет $O(\mathcal{R}_{\rm P}(n,d,0))$ неактивных вершин, с высокой вероятностью. Соответствующие утверждения E справедливы с $t_{\rm E}$ и $\mathcal{R}_{\rm E}(n,d)$ . Для каждого фиксированного $c^{2}/2<\lambda<(c+1)^{2}/2$ и детерминированного целочисленного $a\sim\lambda n/d^{4}$

|A_{\infty}^{\rm R}|=O(n/d^{3}),\qquad n-|A_{\infty}^{\rm E}|=O(\mathcal{R}_{\rm E}(n,d))=o(n)\quad\hbox{with high probability}.

Если также начиная с некоторого индекса $d\geq K_{0}\log n$ при фиксированном $K_{0}>2/3$ , число оставшихся неактивных вершин в модели E в этом сравнении с высокой вероятностью равно $O(n^{2/3})$ . Сравнение использует одинаковую асимптотическую среднюю степень; точные средние равны соответственно $d$ и $d-d/n$ .

Доказательства леммы 3 и следствия 4 приведены в разделе 2. В этом разделе также указаны достаточное логарифмическое условие для $O(n^{2/3})$ оставшихся неактивных вершин и пример с двумя значениями степени.

1.3 Связь с предыдущими работами

В разделе VI, уравнение (24), версии arXiv:1003.5583v2 (2010) работы Baxter et al. (2010) приведено используемое здесь уравнение для модели с распределением порогов. Положим параметр повреждения в нём равным единице, а вероятности порогов ноль, один и два — равными $\alpha,(1-\alpha)\pi,(1-\alpha)(1-\pi)$ . Коэффициенты в (5) являются коэффициентами Тейлора этого известного уравнения. Мы используем уравнение и его формальное разложение как существующие инструменты; наш вклад состоит в указанном выше количественном контроле итогового состояния.

Для независимых рёбер Janson et al. (2012) используют независимые бернуллиевские метки, а Ballen and Guha (2015) допускают неоднородные пороги. Точный биномиальный отклик в последней работе даёт наш смешанный дрейф. Их теорема 1 предполагает фиксированный положительный зазор $\beta$ через условие $d\zeta_{1}\leq 1-\beta$ ; здесь мы обозначаем через $d$ их параметр ожидаемой степени $\eta\phi$ . В нашем режиме $d\pi=1-c/d$ этот зазор стремится к нулю, поэтому указанная теорема напрямую неприменима. Мы применяем не зависящее от распределения доказательство для прямого и обратного эмпирических процессов из лемм 7.2–7.3 работы arXiv:1012.3535v2 к смешанной функции распределения времени активации, локализуем ранний временной горизонт и используем диадическое распределение допустимых ошибок. Это применение известных аргументов к частному случаю, а не новый процесс исследования графа или новое максимальное неравенство.

Для заданных степеней Amini (2010) требует конечного предельного среднего и ограниченного эмпирического второго момента. Lelarge (2012) также рассматривает независимые случайные пороги на графах с заданными степенями, в том числе на равномерных простых графах. Условие 1 и теорема 10 версии arXiv:1012.2062v4 (2011) предполагают фиксированное предельное распределение степеней с конечным средним и $\sum_{i}d_{i}^{2}=O(n)$ ; эти предположения исключают наши последовательности с растущими степенями. Приближение процесса исследования с ошибкой $o_{p}(n)$ в доказательстве этой работы само по себе не разрешает наше узкое место порядка $n/d^{3}$ . Условие 1.1 версии arXiv:2103.00357v2 (2022) работы Amini et al. (2023) требует предельного совместного распределения степени и порога и равномерных экспоненциальных моментов. Эти предположения не выполняются в (3). Мы используем описанный этими авторами процесс исследования полурёбер с экспоненциальными часами. Наш количественный контроль включает локальную дисперсию потерь, остановленную предсказуемую квадратичную вариацию на малых временах, среднее при фиксированном размере начального множества и интерполяцию по времени. Garetto et al. (2016) уже обсуждают неоднородность степеней и сравнивают регулярные и двухуровневые примеры; их условие, исключающее активацию по одному ребру, и расчёт для однородных заданных степеней не дают нашу смесь напрямую.

Работа Janson (2009) включает начальные множества фиксированного размера и результат о критическом окне для фиксированной регулярной степени и общего порога. Таким образом, заданный размер начального множества уже рассматривается в литературе. Другое сравнение касается приближения на конечном временном горизонте: Rossi et al. (2019) разрабатывают количественное сопряжение на конечном временном горизонте и оценки концентрации для пороговой динамики (разделы 4.2–4.3.1 принятой рукописи 2017 года). Ниже мы доказываем необходимую здесь версию с избыточной степенью. При наших предположениях о заданных степенях и фиксированном надкритическом отступе размера начального множества эта адаптация даёт $O(n^{2/3})$ оставшихся неактивных вершин при $d\log d=o(\log n)$ ; см. приложение B. Здесь используются распределение числа потомков, определяемое избыточной степенью, совместная концентрация спаривания и меток и условие простоты. В установленном здесь сравнении подкритическая верхняя оценка итогового состояния по-прежнему требует контроля активации после подтверждённого конечного временного горизонта. Эта адаптация не охватывает весь наш диапазон степеней и не доказывает аналогичный результат для независимых рёбер.

Для фиксированной степени $d$ и общего порога $2\leq k\leq d-1$ авторы Balogh and Pittel (2007, Теоремаs 1–3) устанавливают оценки порога и окна, в том числе для детерминированных начальных множеств. Их уравнение (3) и уравнения (17)–(20) уже выражают порог через инфимум детерминированного отношения отклика. На уровне детерминированного отклика замена биномиального хвоста смесью хвостов для порогов один и два даёт наш регулярный отклик; сама по себе эта подстановка не расширяет область действия их вероятностных теорем. Их переход от конфигураций к простым графам использует вероятность простоты, отделённую от нуля при фиксированном $d$ ; это не даёт напрямую равномерного аргумента с условием простоты, необходимого здесь.

Структура работы.

В разделе 2 доказаны указанные выше следствия, приведены дополнительные примеры и установлен общий детерминированный барьер. Разделы 3 и 4 связывают его с соответствующими процессами исследования графа и оценками концентрации; затем в доказательстве для заданных степеней осуществляется переход к условию простоты. Раздел 5 объясняет препятствие, связанное с точностью, для переноса результатов через статическое включение. В разделе 6 выведены поправки для конечных степеней и моментов более высоких порядков, а в разделе 7 указаны оставшиеся ограничения. Приложения содержат локальные оценки концентрации и сравнение с приближением на конечном временном горизонте при медленно растущих степенях.

2 Следствия и детерминированные оценки

2.1 Эмпирические моменты и следствия

Доказательство леммы 3.

Обозначим $\mu_{3}=\mathbb{E}[(D-d)^{3}]$ . Ограничение на отклонение даёт $0\leq v_{n}\leq C^{2}$ и $|\mu_{3}|\leq C\sqrt{d}\,\mathbb{E}[(D-d)^{2}]=O(d^{3/2})$ . Точные тождества для факториальных моментов дают приведённую формулу для $b$ и

K=(1-2\pi)\left[d^{2}+(3v_{n}-3)d+2-3v_{n}+\frac{\mu_{3}}{d}\right].

Следовательно, $K/d^{2}=1+O(d^{-1})$ и, поскольку $q_{n}\geq\kappa$ , $b=(q_{n}/d)(1+O(d^{-1}))$ . Это доказывает (11). Для любых положительных плотностей $T_{n},A_{n}$ , таких, что $T_{n}/A_{n}\to 1$ , и фиксированного $\gamma\in(0,1)$ начиная с некоторого индекса

(1-\gamma)T_{n}\leq(1-\gamma/2)A_{n},\qquad(1+\gamma)T_{n}\geq(1+\gamma/2)A_{n}.

Применим соответствующую теорему с отступом $\gamma/2$ . Если $v_{n}\to v$ , фиксированный зазор даёт $c+1-v\geq\kappa$ , и тот же аргумент доказывает предельный частный случай. ∎

Целочисленные размеры начального множества.

В обоих случаях (4) и (8) имеем $n/d^{4}\to\infty$ . Поэтому округление размера порядка $n/d^{4}$ меняет его на относительную величину $o(1)$ . Точнее, для любого центра порога $A_{\star}\asymp d^{-4}$ из теоремы величина $\lfloor(1-\gamma)nA_{\star}\rfloor$ удовлетворяет подкритическому неравенству, а $\lceil(1+\gamma)nA_{\star}\rceil$ — надкритическому. Опорный размер $\lceil(1+\gamma/2)nA_{\star}\rceil$ не превышает ни одного допустимого надкритического размера при всех достаточно больших $n$ . Равномерные начальные множества всех заданных размеров можно сопрячь как начальные отрезки одной равномерной перестановки, независимой от графа и порогов. Монотонность бутстрэп-замыкания затем переносит оценку с опорного размера на каждый допустимый меньший или больший заданный размер.

Следствие 5 (Достаточное логарифмическое условие).

В надкритическом выводе теоремы 1 предположим также, что начиная с некоторого индекса $d\geq K_{0}\log n$ при некотором фиксированном $K_{0}>1/(3\log 2)$ . Тогда $n-|A_{\infty}|=O(n^{2/3})$ с высокой вероятностью. В надкритическом выводе теоремы 2 тот же результат справедлив, если начиная с некоторого индекса $d\geq K_{0}\log n$ при некотором фиксированном $K_{0}>2/3$ . Это достаточные условия, а не необходимые условия или оптимальные константы; граничные равенства не утверждаются.

Доказательство.

Для P функция $f(x)=x\log 2-C\sqrt{x}\log 2-\log x$ возрастает при всех достаточно больших $x$ . Поэтому

f(d)-\tfrac{1}{3}\log n\geq(K_{0}\log 2-\tfrac{1}{3})\log n-O(\sqrt{\log n})-O(\log\log n)\longrightarrow\infty.

Отсюда следует, что $d2^{-d+C\sqrt{d}}=o(n^{-1/3})$ . Для E функция $g(x)=x/2-\log(1+x)$ возрастает начиная с некоторого момента, и $d/n=o(1)$ . Следовательно,

g(d)-\tfrac{1}{3}\log n-d/n\geq(K_{0}/2-\tfrac{1}{3})\log n-O(\log\log n)-o(1)\longrightarrow\infty,

так что $(1+d)e^{-d/2+d/n}=o(n^{-1/3})$ . Подставим эти оценки в (2) и соответствующую надкритическую теорему. ∎

Доказательство следствия 4.

Для регулярной модели $C=v_{n}=0$ и

b_{\rm R}=\frac{c+1}{d}-\frac{c}{d^{2}},\qquad K_{\rm R}=(1-2\pi)(d-1)(d-2),\qquad nA_{\rm R}\sim t_{\rm R}.

Теорема 1 и лемма 3 дают утверждения для регулярной модели. Общий диапазон влечёт (8), поскольку

\frac{d^{5}}{n}=\left(\frac{d}{n^{1/7}}\right)^{5}n^{-2/7}\longrightarrow 0.

Таким образом, теорема 2 также применима. Положим $L=c^{2}/2$ , $U=(c+1)^{2}/2$ и

\gamma_{*}=\frac{1}{4}\min\{1,\lambda/L-1,1-\lambda/U\}>0.

Отношения $a/t_{\rm E}\to\lambda/L$ и $a/(nA_{\rm R})\to\lambda/U$ помещают начальные множества по разные стороны порога с отступом $\gamma_{*}$ . Оценки теорем и оценка вероятности объединения событий дают совместный вывод. Независимость двух графов не нужна: можно использовать любое сопряжение их распределений с общими метками порогов и равномерной перестановкой начальных вершин, независимой от пары графов. Округление $\lambda n/d^{4}$ безвредно ввиду $n/d^{4}\to\infty$ . Последнее утверждение следует из следствия 5. ∎

Следствие 6 (Два значения степени).

Зафиксируем $c>0$ , $\kappa>0$ и $\gamma\in(0,1)$ . Пусть $n$ чётно, $s\geq 0$ , а $d-s,d+s$ — неотрицательные целые числа, причём $nd$ чётно. Припишем степень $d-s$ половине вершин, а $d+s$ — другой половине. Предположим, что $d\to\infty$ , $d=o(n^{1/7})$ и

v_{n}=\frac{s^{2}}{d},\qquad q_{n}=c+1-v_{n}\geq\kappa.

Положим $t_{2,n}=nq_{n}^{2}/(2d^{4})$ и $C_{2}=\sqrt{c+1}$ . Начиная с некоторого индекса последовательность реализуема простым графом. Для равномерного простого графа с этими степенями и указанной независимой моделью порогов и начального множества

\begin{split}a\leq(1-\gamma)t_{2,n}&\ \Longrightarrow\quad|A_{\infty}|=O(n/d^{3})\quad\hbox{with high probability},\\ a\geq(1+\gamma)t_{2,n}&\ \Longrightarrow\quad n-|A_{\infty}|=O(\mathcal{R}_{\rm P}(n,d,C_{2}))\quad\hbox{with high probability}.\end{split}

Если начиная с некоторого индекса $d\geq K_{0}\log n$ при фиксированном $K_{0}>1/(3\log 2)$ , число оставшихся неактивных вершин в надкритическом случае с высокой вероятностью равно $O(n^{2/3})$ . Если дополнительно $v_{n}\to v<c+1$ , величину $t_{2,n}$ в этих утверждениях с фиксированными отступами можно заменить на $n(c+1-v)^{2}/(2d^{4})$ .

Доказательство.

Эмпирическое среднее в точности равно $d$ , дисперсия равна $s^{2}$ , а третий центральный момент равен нулю. Зазор влечёт $s\leq\sqrt{c+1}\sqrt{d}$ , поэтому условие на отклонения в модели P выполнено с фиксированным $C_{2}$ . В частности,

b=\frac{q_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}},\qquad K=(1-2\pi)[d^{2}+(3v_{n}-3)d+2-3v_{n}].

Применим теорему 1, лемму 3 и следствие 5. ∎

Условия относятся к самим двум степеням: обе величины $d,s$ могут быть полуцелыми, а одной чётности $n$ недостаточно для чётности $nd$ . Для конкретного примера с предельной дисперсией зафиксируем $0\leq v<c+1$ , возьмём целое $d\to\infty$ и чётное $n$ в указанном диапазоне и положим $s=\lfloor\sqrt{vd}\rfloor$ . Тогда начиная с некоторого индекса степени являются неотрицательными целыми числами, $nd$ чётно, и

0\leq v-v_{n}\leq 2\sqrt{v/d},\qquad v_{n}\longrightarrow v.

Отсюда следует фиксированный положительный зазор, и применим предельный частный случай. Для поправок при конечной степени по-прежнему необходимо сохранять фактическое $v_{n}=s^{2}/d$ ; этот пример не даёт скорости $o(d^{-1})$ для $v_{n}-v$ . Случай $s=0$ соответствует регулярной модели. Совпадение ведущего коэффициента при формальном значении дисперсии $v=1$ не делает модель с независимыми рёбрами частным случаем предположения о максимальном отклонении заданных степеней.

2.2 Общий детерминированный барьер

Обе модели имеют один и тот же локальный механизм: отклик $F$ без начальной активации с $F^{\prime}(0)=1-b$ и $F^{\prime\prime}(0)=K$ порождает барьер порядка $b^{2}/(2K)$ . Следующая лемма контролирует этот барьер и дрейф за ним; затем вероятностные аргументы сравнят очереди процесса исследования графа с этим дрейфом.

Лемма 7 (Барьер отклика при малом дефиците).

Пусть $d\to\infty$ , а $F:[0,1/2]\to[0,1)$ не убывает и $F(0)=0$ . Предположим, что $F$ принадлежит классу $C^{3}$ на $[0,\varepsilon/d]$ при фиксированном $\varepsilon>0$ , с односторонними производными в концах интервала, и что

F^{\prime}(0)=1-b,\quad F^{\prime\prime}(0)=K,\quad b_{*}/d\leq b\leq b^{*}/d,\quad K_{*}d^{2}\leq K\leq K^{*}d^{2},

F^{\prime\prime}\geq K/2,\quad|F^{\prime\prime\prime}|\leq C_{3}d^{3}\quad(0\leq z\leq\varepsilon/d).

Здесь $b_{*},b^{*},K_{*},K^{*},C_{3}$ — фиксированные положительные константы. Предположим, что $\sup_{\xi\leq z\leq 1/2}(1-F(z))=o(1)$ для каждого фиксированного $\xi\in(0,1/2)$ . Положим $A=b^{2}/(2K)$ , $z_{0}=b/K$ и $h_{\alpha}(z)=\alpha+(1-\alpha)F(z)-z$ . Выберем любое фиксированное $L>8b^{*}/K_{*}$ . Для каждого фиксированного $\eta\in(0,1)$ , если $\alpha_{\pm}=(1\pm\eta)A+o(A)$ , то начиная с некоторого индекса при фиксированном $k_{\eta}>0$

h_{\alpha_{+}}(z)\geq k_{\eta}\begin{cases}d^{-4},&0\leq z\leq L/d^{3},\\ d^{2}z^{2},&L/d^{3}\leq z\leq\varepsilon/d,\\ 1,&\varepsilon/d\leq z\leq 1/2,\end{cases}\qquad h_{\alpha_{-}}(z_{0})\leq-\eta A/2.

(13)

Константы зависят только от указанных фиксированных ограничений, $L$ и $\eta$ . Кроме того, $R=(z-F)/(1-F)$ имеет единственный глобальный максимум на $[0,1/2]$ , достигаемый в $(0,8b/K)$ и равный $A+o(A)$ .

Доказательство.

Равномерно на $[0,L/d^{3}]$ при $\alpha=O(A)$

h_{\alpha}(z)=\alpha-A+\frac{K}{2}(z-z_{0})^{2}+O(d^{3}z^{3}+\alpha F(z)).

(14)

Действительно, разложение Тейлора также даёт там $F(z)=O(d^{-3})$ , поэтому два остаточных члена равны $O(d^{-6})$ и $O(d^{-7})$ , и оба имеют порядок $o(A)$ . Это доказывает ранний положительный и отрицательный отступы. При $z\geq L/d^{3}\geq 8b/K$ и $z\leq\varepsilon/d$

F(z)-z\geq-bz+Kz^{2}/4\geq Kz^{2}/8.

Таким образом, начиная с некоторого индекса $F(\varepsilon/d)\geq q_{0}$ при некотором фиксированном $0<q_{0}\leq 1/4$ . На $[\varepsilon/d,q_{0}/2]$ монотонность даёт $F-z\geq q_{0}/2$ ; на $[q_{0}/2,1/2]$ предположение о хвосте даёт $F-z\geq 1/4$ начиная с некоторого индекса. Поскольку $h_{\alpha}=F-z+\alpha(1-F)\geq F-z$ при $\alpha\geq 0$ , это доказывает остальные отступы.

Для $B=1-F$ на $[0,8b/K]$

R^{\prime}=g/B^{2},\quad g=B-(1-z)F^{\prime},\quad g^{\prime}=-(1-z)F^{\prime\prime}.

Здесь $g$ строго убывает, $g(0)=b$ и $g(8b/K)=-7b+O(d^{-3})<0$ . Существует единственный ранний максимум. Предыдущий аргумент для среднего и позднего участков, начиная с $8b/K$ , даёт $F-z>0$ всюду вне этого интервала, так что там $R<0$ . Внутри него равномерно $R=bz-Kz^{2}/2+o(A)$ ; максимум равен $A+o(A)>0$ . Все возмущения $o(A)$ поглощаются фиксированным отступом. ∎

Проверка для двух откликов.

Для заданного эмпирического распределения определим при $y=1-z$

B_{k}(z)=y^{k-1}+(1-\pi)(k-1)zy^{k-2},\qquad F_{\rm P}(z)=1-\frac{1}{d}\mathbb{E}[DB_{D}(z)].

Для независимых рёбер определим

F_{\rm E}(z)=1-e^{-dz}[1+(1-\pi)dz].

Проверка для P использует только (3), фиксированные $c,C,\kappa$ и $d\to\infty$ . Лемма 3 даёт соответствующие $b,K,A$ . Начиная с некоторого индекса $\delta=\min_{i}d_{i}\geq 7$ , $\Delta=\max_{i}d_{i}\asymp d$ . Для $F_{k}=1-B_{k}$ и $1\leq j\leq 5$

F_{k}^{(j)}(z)=(-1)^{j+1}(k-1)_{j}y^{k-2-j}\{[1-j(1-\pi)]y+(1-\pi)(k-1-j)z\}.

В частности, $F_{k}^{\prime}\geq 0$ и

F_{k}^{\prime\prime}=(k-1)(k-2)y^{k-4}\{(1-2\pi)y-(1-\pi)(k-3)z\}.

Для E при $1\leq j\leq 5$

F_{\rm E}^{(j)}(z)=(-1)^{j+1}d^{j}e^{-dz}[1-j(1-\pi)+(1-\pi)dz].

Для него $b=c/d$ , $K=(1-2\pi)d^{2}$ и $A^{\rm quad}=b^{2}/(2K)=A_{\rm E}(1+O(d^{-1}))$ . Оба отклика не убывают и строго меньше единицы на $[0,1/2]$ . При достаточно малом фиксированном $\varepsilon>0$ формулы дают $F^{\prime\prime}\geq K/2$ и $|F^{(j)}|=O(d^{j})$ , $2\leq j\leq 5$ , на $[0,\varepsilon/d]$ . Для P равномерно $k/d=1+O(d^{-1/2})$ , поэтому отношение каждой второй производной к её значению в нуле не меньше $1/2$ при малом $\varepsilon$ . Для E это отношение равно $e^{-dz}[1-(1-\pi)dz/(1-2\pi)]$ и обладает тем же свойством. Для каждого фиксированного $\xi>0$ оценки хвостов имеют вид

1-F_{\rm P}(z)\leq(1+\Delta)(1-\xi)^{\delta-2},\qquad 1-F_{\rm E}(z)\leq(1+d)e^{-d\xi}\quad(\xi\leq z\leq 1/2).

Таким образом, лемма 7 применима к обоим откликам без соотношения между $n$ и $d$ . Те же формулы дают $F^{\prime}=O(1)$ на каждом фиксированном раннем интервале $[0,L/d^{3}]$ .

3 Доказательство для заданных степеней

Обозначим $\delta=\min_{i}d_{i}$ , $\Delta=\max_{i}d_{i}$ и возьмём $n$ достаточно большим, чтобы $\delta\geq 4$ и $0<\pi<1$ . Все константы ниже зависят только от фиксированных параметров теоремы 1. Положим $M=\sum_{i}d_{i}=nd$ . Сначала мы работаем с равномерным спариванием $M$ помеченных полурёбер, учитывая кратность рёбер. Мы сравниваем активную очередь с её детерминированным дрейфом, используем концентрацию для определения остановки или прохождения барьера, а затем оцениваем итоговое число активных или неактивных вершин. Наконец, мы переходим к условию простоты и проверяем, что вероятности неудачи остаются $o(1)$ .

Отклик и детерминированные отступы.

Используем $F=F_{\rm P}$ из раздела 2.2, $B=1-F$ , $M=nd$ и $h_{\alpha}=\alpha+(1-\alpha)F-z$ . Лемма 3 даёт $b\asymp d^{-1}$ , $K\asymp d^{2}$ и $A\asymp d^{-4}$ ; рассматриваемый диапазон степеней даёт $nA\to\infty$ . Возьмём

a_{-}=\lfloor(1-\gamma)nA\rfloor,\qquad a_{+}=\lceil(1+\gamma/2)nA\rceil,\qquad\alpha_{\pm}=a_{\pm}/n.

Ошибки округления равны $o(A)$ . Выберем $L$ как в лемме 7 и применим её с отступами $\gamma$ и $\gamma/2$ соответственно. Положим $\eta=\varepsilon$ , $u=-\log(1-z)$ и $D_{\alpha}(u)=M(1-z)h_{\alpha}(z)$ . Поскольку $1/2\leq 1-z\leq 1$ , при достаточно малом фиксированном $k>0$

D_{\alpha_{+}}(u)\geq\begin{cases}kn/d^{3},&0\leq z\leq L/d^{3},\\ knd^{3}z^{2},&L/d^{3}\leq z\leq\eta/d,\\ knd,&\eta/d\leq z\leq 1/2,\end{cases}\qquad D_{\alpha_{-}}(u_{*})\leq-kn/d^{3},\quad u_{*}=-\log(1-b/K).

(15)

Процесс исследования графа и правило остановки.

Назначим каждому исходному полуребру независимые экспоненциальные часы с интенсивностью один, независимо от начального множества и порогов. Зарезервируем один активный конец, не проверяя будущее время срабатывания его часов, и спарим его с первым незарезервированным концом, часы которого сработают. Запишем метку в вершине партнёра, активируем эту вершину, если достигнут её порог, и зарезервируем следующий активный конец. Для выбора резервируемого конца используем только уже раскрытую информацию. Остановимся в момент $\tau$ , когда после спаривания не остаётся активных концов. Все оставшиеся пары достроим равномерно. Благодаря отсутствию памяти у экспоненциального распределения каждый раскрытый партнёр равномерно распределён среди остальных оставшихся концов. Поэтому индукция по числу оставшихся концов даёт равномерное полное спаривание при условии любого назначения начального множества и порогов; следовательно, это спаривание независимо от указанных назначений.

Каждая активация обоснована раскрытыми рёбрами от активных вершин. При остановке все концы активных вершин уже исследованы; оставшиеся пары соединяют неактивные вершины, каждая из которых получила от активных вершин меньше меток, чем её порог. Поэтому итоговое множество замкнуто относительно правила активации и в точности совпадает с бутстрэп-замыканием. В частности, достраивание не добавляет активаций.

Пусть $X_{i}(u)$ считает исходные часы в вершине $i$ , сработавшие к моменту $u$ , включая скрытые часы удалённых концов, и положим

H(u)=\sum_{i\notin A_{0}}(d_{i}-X_{i}(u))\mathbf{1}_{\{X_{i}(u)<R_{i}\}}.

До момента $\tau$ включительно это фактическое число неактивных концов: до активации ни один конец в этой вершине не удалялся вручную, а после активации число сработавших исходных часов остаётся не меньше её порога. После $\tau$ формула остаётся скрытым процессом и не подразумевает дальнейшей реальной активации. Её безусловное среднее в точности равно

\bar{H}(u)=(1-\alpha)Me^{-u}B(1-e^{-u}),\qquad Me^{-2u}-\bar{H}(u)=D_{\alpha}(u).

(16)

Пусть $W$ считает незарезервированные концы, изначально $W(0)=M-1$ . Каждое спаривание уменьшает $W$ на два, с фиктивным последним резервированием, если активного конца нет. Поэтому учётное значение $W$ в момент $\tau$ на единицу меньше фактического числа оставшихся концов, и

Q(u):=W(u)-H(u)\geq 0\quad(u<\tau),\qquad Q(\tau)=-1.

(17)

Все сравнения очереди ниже учитывают это правило в момент остановки.

Локальная оценка прохождения барьера.

Положим $U=\log 2$ . Следующая оценка сравнивает очередь с тремя масштабами дрейфа в (15).

Лемма 8 (Локальная концентрация активной очереди).

При предположениях теоремы 1 рассмотрим только что определённый процесс исследования конфигурационной модели с одним из опорных размеров $a_{-}$ или $a_{+}$ . Пусть $k,L,\eta$ выбраны как в (15). Существуют константы $C_{2},k_{2}>0$ , зависящие только от $c,C,\kappa,\gamma$ , такие, что вне события вероятности не более

C_{2}(1+d^{2})(1+\log d)\exp(-k_{2}n/d^{5}),

(18)

одновременно выполняются следующие оценки для $0\leq u\leq U\wedge\tau$ , где $z=1-e^{-u}$ :

|Q(u)-D_{\alpha}(u)|<\frac{k}{2}\begin{cases}n/d^{3},&0\leq z\leq L/d^{3},\\ nd^{3}z^{2},&L/d^{3}<z\leq\eta/d,\\ nd,&\eta/d<z\leq 1/2.\end{cases}

Для размера $a_{-}$ на том же событии, если $u_{*}\leq\tau$ , то $|Q(u_{*})-D_{\alpha_{-}}(u_{*})|<kn/(2d^{3})$ .

Доказательство в приложении A использует отдельные оценки для вершин, начального множества и остановленной очереди на трёх масштабах дрейфа.

Для $a_{-}$ , если бы $\tau\geq u_{*}$ , очередь была бы меньше $-1$ в момент $u_{*}$ , что противоречит (17). Поэтому $\tau<u_{*}$ . Для $a_{+}$ остановка в любой момент $\tau\leq U$ дала бы $Q(\tau)>0$ , снова противоречие. Поэтому $\tau>U$ .

Число вершин в двух исходах.

В подкритическом случае каждая в конечном итоге активированная вершина, не входящая в начальное множество, удовлетворяет $X_{i}(u_{*})\geq R_{i}$ . Индикаторы этих событий по всем вершинам независимы при безусловном распределении часов и порогов, а среднее их суммы не превышает

\mu_{*}\leq\sum_{i}\left[\pi d_{i}z_{*}+\binom{d_{i}}{2}z_{*}^{2}\right]\leq C_{3}n/d^{3},\qquad z_{*}=b/K.

Неравенство Бернштейна для сумм бернуллиевских величин с отклонением $n/d^{3}$ ограничивает вероятность того, что эта сумма превысит $(C_{3}+1)n/d^{3}$ , величиной $\exp(-k_{3}n/d^{3})$ . Добавление $a_{-}=O(n/d^{4})$ доказывает требуемую оценку числа вершин на пересечении с событием остановки. Независимость этих двух событий не требуется.

Для надкритического случая положим $N_{U}=\sum_{i}\mathbf{1}_{\{X_{i}(U)<R_{i}\}}$ . Эти индикаторы независимы при безусловном распределении часов и порогов, причём

\mu_{U}=\mathbb{E}N_{U}=\sum_{i}2^{-d_{i}}[1+(1-\pi)d_{i}]\leq n(1+\Delta)2^{-\delta}.

Неравенство Хёффдинга даёт

\Pr(N_{U}>\mu_{U}+n^{2/3})\leq e^{-2n^{1/3}}.

(19)

Возьмём $k_{4}=2$ в (20). На $\{\tau>U\}$ каждая вершина, остающаяся в итоге неактивной, удовлетворяет $X_{i}(U)<R_{i}$ , поскольку ни один конец неактивной вершины не удалялся вручную. Поэтому пересечение события прохождения барьера и этого безусловного события для числа вершин даёт

n-|A_{\infty}|\leq N_{U}\leq\mu_{U}+n^{2/3}\leq B_{+}n[d2^{-d+C\sqrt{d}}+n^{-1/3}].

Простота, реализуемость последовательности степеней и равномерность.

При $M_{r}=\sum_{i}(d_{i})_{r}$ и $\nu=M_{2}/M=d-1+v_{n}$ лемма 5.1 работы McKay and Wormald (1991) даёт в рассматриваемом режиме

\log s=-\nu/2-\nu^{2}/4+O(d^{3}/n),\qquad s=\Pr\{\text{the pairing is simple}\}\geq e^{-C_{0}d^{2}}.

Действительно, её условие $\Delta=o(M^{1/3})$ следует из $\Delta^{3}/M=O(d^{2}/n)=o(1)$ . Дополнительные члены в ней равны $O(\Delta^{4}/M)$ , а остаток равен $O(\Delta^{3}/M)$ ввиду $M_{r}\leq M\Delta^{r-1}$ ; это даёт приведённый частный случай. Положительная вероятность также доказывает реализуемость последовательности степеней начиная с некоторого индекса. Каждому простому графу соответствует ровно $\prod_{i}d_{i}!$ спариваний, поэтому условное распределение графа равномерно среди простых графов. Полное спаривание независимо от порогов и начального множества, и потому их совместное распределение сохраняется. После перехода к условию простоты часы не обязаны оставаться независимыми.

Разделим сумму всех применимых вероятностей неблагоприятных событий на $s$ . Для обоих опорных исходов общая верхняя оценка имеет вид

e^{C_{0}d^{2}}\left[C_{2}(1+d^{2})(1+\log d)e^{-k_{2}n/d^{5}}+e^{-k_{3}n/d^{3}}+4e^{-k_{4}n^{1/3}}\right]=o(1).

(20)

Здесь используется только

\frac{n/d^{5}}{d^{2}}=\frac{n}{d^{7}}\to\infty,\qquad\frac{n/d^{5}}{\log n}\geq\frac{n^{2/7}}{\log n}\to\infty,\qquad\frac{d^{2}}{n^{1/3}}\to 0,

где среднее неравенство выполняется начиная с некоторого индекса. В частности, условие $d^{2}\gg\log n$ не требуется. Каждый допустимый подкритический размер не превышает $a_{-}$ , а каждый допустимый надкритический размер начиная с некоторого индекса не меньше $a_{+}$ , поскольку $nA\to\infty$ . Сопряжение с независимой перестановкой из пункта 2.1 переносит опорные выводы по монотонности. Случаи пустого и полного начальных множеств очевидны. Это завершает доказательство.

4 Доказательство для независимых рёбер

Мы применяем построение с независимыми метками и не зависящий от распределения аргумент для эмпирического процесса из работы Janson et al. (2012) к смеси порогов.

Положим $p=d/n$ и $N=n-a$ . Все утверждения ниже относятся к достаточно большим $n$ , поэтому $0<p<1/2$ и $0<\pi<1$ .

Зафиксируем в качестве условия конкретное начальное множество размера $a$ . На каждом реальном шаге $i$ выберем одну активную неиспользованную вершину $u_{i}$ по детерминированному правилу, зависящему только от раскрытой истории и порогов. Раскроем её рёбра ко всем остальным неиспользованным вершинам. Эти рёбра ранее не раскрывались: ни одна из их концевых вершин ранее не использовалась. При условии истории и всех порогов они являются независимыми величинами Бернулли $(p)$ . Для каждой вершины $v$ , не входящей в начальное множество, положим $I_{v}(i)$ равным индикатору этого ребра, когда $v$ является целью шага; во все остальные ячейки (включая $v=u_{i}$ ) поместим новую независимую величину Бернулли $(p)$ . Таким образом, каждый новый столбец имеет распределение, равное произведению распределений Бернулли $(p)$ , и независим от всех предыдущих столбцов и порогов. После остановки реального процесса исследования заполним оставшиеся столбцы новыми величинами. Нераскрытые рёбра графа достроим независимо. Поэтому отложенное раскрытие случайности даёт в точности требуемое распределение графа, независимое от порогов, и массив независимых одинаково распределённых меток, независимый от порогов. Искусственные ячейки — вспомогательные величины, а не дополнительные рёбра графа.

Для целого $0\leq t\leq n$ определим

M_{v}(t)=\sum_{i=1}^{t}I_{v}(i),\quad S(t)=\sum_{v\notin A_{0}}{\bf 1}_{\{M_{v}(t)\geq R_{v}\}},\quad L(t)=a+S(t)-t.

До первой активации вершины, не входящей в начальное множество, она остаётся неиспользованной, и все её метки — реальные рёбра от различных использованных вершин. После активации общее число её меток остаётся не ниже её порога. Поэтому до реальной остановки включительно число активных вершин в точности равно $a+S(t)$ . Поскольку $L(t+1)-L(t)\geq-1$ , процесс исследования останавливается в момент

T=\min\{0\leq t\leq n:L(t)\leq 0\},\qquad L(T)=0,\qquad|A_{\infty}|=T.

(21)

Минимум существует, поскольку $L(n)\leq 0$ . При остановке каждая активная вершина уже использована, а каждая неактивная имеет меньше $R_{v}$ соседей в этом активном множестве. Множество замкнуто, и каждая активация, использованная при его построении, была допустимой бутстрэп-активацией, что доказывает последнее тождество. При $a=0$ непосредственно $T=0$ . Ни одна активация после $T$ во вспомогательном массиве не объявляется реальной активацией.

Независимость строк даёт в каждый детерминированный целочисленный момент времени

S(t)\sim\operatorname{Bin}(N,q(t)),\quad q(t)=1-(1-p)^{t}-(1-\pi)tp(1-p)^{t-1}\ (t\geq 1),\quad q(0)=0.

(22)

Разные моменты времени не обязаны быть независимыми. Обозначим $F=F_{\rm E}$ из раздела 2.2, $z=t/n$ и $h_{\alpha}=\alpha+(1-\alpha)F-z$ . Факториальные моменты дают

q(t)\leq z+d^{2}z^{2}/2,\qquad|q(t)-F(z)|\leq d^{2}z/n.

(23)

Для второй оценки сопряжём величины Бернулли $(p)$ и Пуассона $(p)$ с вероятностью несовпадения $p(1-e^{-p})\leq p^{2}$ , возьмём $t$ независимых копий и один и тот же независимый порог. Для $\mu_{a}(t)=a+Nq(t)-t$ это даёт

|\mu_{a}(t)-nh_{\alpha}(t/n)|\leq d^{2}z.

(24)

Лемма 9 (Максимальный контроль смешанного эмпирического процесса).

Пусть $Y_{1},\ldots,Y_{N}$ — независимые одинаково распределённые положительные целочисленные величины с функцией распределения $q$ , где $q(0)=0$ , $0<q(t)<1$ для конечных $t\geq 1$ и $q(t)\uparrow 1$ . Пусть $N\leq n$ и $D_{t}=\sum_{v}\mathbf{1}_{\{Y_{v}\leq t\}}-Nq(t)$ . Тогда для $x>0$ и каждого целого $u\geq 0$

\Pr(\sup_{t\leq u}|D_{t}|>x)\leq 16nq(u)/x^{2},\qquad\Pr(\sup_{t\geq 0}|D_{t}|>x)\leq 8n/x^{2}.

(25)

Доказательство.

Используем собственные индикаторные фильтрации $\mathcal{F}_{t}=\sigma(\mathbf{1}_{\{Y_{v}\leq s\}}:s\leq t,v)$ и $\mathcal{G}_{t}=\sigma(\mathbf{1}_{\{Y_{v}\leq s\}}:s\geq t,v)$ . Процессы $D_{t}/(1-q(t))$ и $D_{t}/q(t)$ являются соответственно прямым и обратным мартингалами там, где их знаменатели ненулевые. Для индикатора, ещё не равного единице, следующая условная вероятность перехода в единицу равна $(q(t+1)-q(t))/(1-q(t))$ ; в обратном направлении при условии, что индикатор равен единице в момент $t+1$ , вероятность того, что он равен единице в момент $t$ , равна $q(t)/q(t+1)$ . Эти тождества доказывают утверждения об условных ожиданиях; независимость позволяет суммировать. В этих фильтрациях пороги не раскрываются. Неравенство Дуба в $L^{2}$ и $\operatorname{Var}(D_{u})=Nq(u)(1-q(u))$ дают

\mathbb{E}\sup_{t\leq u}|D_{t}|^{2}\leq 4Nq(u)/(1-q(u))\leq 8nq(u)\quad(q(u)\leq 1/2),

и $\mathbb{E}\sup_{t\geq u}|D_{t}|^{2}\leq 4N(1-q(u))/q(u)$ , если $q(u)\geq 1/2$ . Для обратной оценки сначала используем конечный обращённый временной горизонт, а затем устремим его к бесконечности. Пусть $t_{1}$ — последнее целое число, для которого $q(t_{1})\leq 1/2$ . Левая оценка при $t_{1}$ и правая оценка при $t_{1}+1$ обе не превышают $4N$ , даже когда $q$ скачком пересекает $1/2$ . Поэтому глобальный второй момент не превышает $8n$ . Если $q(u)>1/2$ , эта величина также не превышает $16nq(u)$ . Неравенство Маркова доказывает оба утверждения; $u=0$ детерминировано. Это доказательство через эмпирический процесс из лемм 7.2–7.3 работы Janson et al. (2012), применённое к смешанной функции распределения. ∎

Применим эту лемму к $Y_{v}=\min\{t:M_{v}(t)\geq R_{v}\}$ . При необходимости независимо продолжим вспомогательные независимые одинаково распределённые бернуллиевские величины за пределы $n$ ; эти дополнительные величины не являются рёбрами графа. Величины $Y_{v}$ независимы и одинаково распределены со смешанной функцией распределения из (22), включая её продолжение. Возьмём опорные размеры

a_{-}=\lfloor(1-\gamma/2)nA_{\rm E}\rfloor,\qquad a_{+}=\lceil(1+\gamma/2)nA_{\rm E}\rceil.

Выберем $L$ как в лемме 7. Поскольку $A^{\rm quad}/A_{\rm E}=1+O(d^{-1})$ и $1/n=o(d^{-4})$ , лемма 7 применима с отступом $\gamma/2$ и возмущениями $o(A^{\rm quad})$ . Положим $\eta=\varepsilon$ , $m=\lfloor n/2\rfloor$ и $t_{*}=\operatorname{round}(nb/K)$ . Три ошибки в (24) относительно соответствующих масштабов очереди ограничены величинами $Ld^{3}/n$ , $d^{3}/(Ln)$ и $d^{2}/(2n)$ , каждая из которых равна $o(1)$ . Кроме того, $t_{*}=O(n/d^{3})$ относится к раннему участку; оценка $F^{\prime}=O(1)$ на нём делает ошибку дрейфа от округления времени равной $O(1)=o(n/d^{4})$ . Следовательно, при некотором фиксированном $k>0$

\mu_{a_{+}}(t)\geq 2k\begin{cases}n/d^{4},&z\leq L/d^{3},\\ nd^{2}z^{2},&L/d^{3}<z\leq\eta/d,\\ n,&\eta/d<z\leq 1/2,\end{cases}\qquad\mu_{a_{-}}(t_{*})\leq-2kn/d^{4}.

(26)

Для раннего временного горизонта $u=\lfloor nL/d^{3}\rfloor$ имеем $q(u)=O(d^{-3})$ . При допустимой ошибке $kn/d^{4}$ оценка (25) даёт вероятность неудачи $O(d^{5}/n)$ , также контролируя проверку отрицательного дрейфа. Для средних интервалов положим $s_{j}=2^{j}L/d^{3}<\eta/d$ и $u_{j}=\lfloor n\min(2s_{j},\eta/d)\rfloor$ . При $s_{j}\leq t/n\leq\min(2s_{j},\eta/d)$ используем допустимую ошибку $knd^{2}s_{j}^{2}$ . Поскольку $q(u_{j})\leq C(s_{j}+d^{2}s_{j}^{2})$ , вероятность неудачи не превышает

C\{(nd^{4}s_{j}^{3})^{-1}+(nd^{2}s_{j}^{2})^{-1}\}.

Суммы $2^{-3j}$ и $2^{-2j}$ ограничены, что даёт $O((d^{5}+d^{4})/n)$ . Эти интервалы и ранний временной горизонт покрывают все целочисленные моменты времени вплоть до $\eta/d$ ; пустые интервалы можно пропустить. Поздняя глобальная оценка с допустимой ошибкой $kn$ даёт вероятность неудачи $O(1/n)$ . Ни независимость интервалов, ни условие продолжения процесса не используются. Следовательно,

\Pr\{\exists t\leq m:L_{+}(t)\leq 0\}\leq Cd^{5}/n=o(1),\qquad\Pr\{L_{-}(t_{*})\geq 0\}\leq Cd^{5}/n.

(27)

В силу (21) вспомогательная проверка отрицательного дрейфа вынуждает $T\leq t_{*}$ , что даёт $|A_{\infty}|=O(n/d^{3})$ ниже порога. Выше него $T>m$ , поэтому число вершин в момент $m$ является реальным числом активных вершин. Отдельно безусловное биномиальное неравенство Хёффдинга даёт $\Pr(|S(m)-Nq(m)|>n^{2/3})\leq 2e^{-2n^{1/3}}$ . Пересечём это событие с событием прохождения барьера, не рассматривая биномиальное распределение при условии продолжения процесса. Поскольку $p\leq 1/2$ , $mp\leq d/2$ и $mp\geq d/2-d/n$ ,

1-q(m)=(1-p)^{m}[1+(1-\pi)mp/(1-p)]\leq(1+d)e^{-d/2+d/n}.

Таким образом,

n-|A_{\infty}|\leq n-a-S(m)\leq n(1+d)e^{-d/2+d/n}+n^{2/3},

с вероятностью неудачи не более $Cd^{5}/n+2e^{-2n^{1/3}}$ . Это число оставшихся неактивных вершин равно $o(n)$ для каждого допустимого $d\to\infty$ . Поскольку $nA_{\rm E}\to\infty$ , каждый допустимый подкритический размер не превышает $a_{-}$ , а каждый допустимый надкритический размер начиная с некоторого индекса не меньше $a_{+}$ . Пункт 2.1 переносит выводы. Оценки при условии заранее фиксированного начального множества равномерны по меткам его вершин. Они не допускают адаптивного выбора начального множества и не утверждают одновременной гарантии для всех множеств. Случаи $a=0,n$ очевидны. Это доказывает теорему 2.

5 Точность, необходимая для статического двустороннего включения

При общих порогах и начальных множествах включение графов сохраняет включение активных множеств, что следует по индукции по раундам активации. Чтобы изучить точность, необходимую для переноса коэффициента, сначала приведём следствие теоремы с фиксированными параметрами.

Лемма 10 (Компактный диапазон эффективных параметров).

Предположим, что $r\to\infty$ и $r^{5}/n\to 0$ , и зафиксируем $0<m_{0}\leq M_{0}<\infty$ и $\gamma\in(0,1)$ . Пусть $c_{n}^{\prime}\in[m_{0},M_{0}]$ детерминировано, и возьмём $G(n,r/n)$ с независимыми порогами, удовлетворяющими $\Pr(R_{i}=1)=(1-c_{n}^{\prime}/r)/r$ , и независимым равномерным начальным множеством заданного размера $a$ . Положим $T_{n}^{\prime}=n(c_{n}^{\prime})^{2}/(2r^{4})$ . Тогда

\begin{split}a\leq(1-\gamma)T_{n}^{\prime}&\ \Longrightarrow\quad|A_{\infty}|=O(n/r^{3})\quad\hbox{with high probability},\\ a\geq(1+\gamma)T_{n}^{\prime}&\ \Longrightarrow\quad n-|A_{\infty}|=O(\mathcal{R}_{\rm E}(n,r))\quad\hbox{with high probability}.\end{split}

Константы могут зависеть только от $m_{0},M_{0},\gamma$ . Вывод для E из следствия 5 также справедлив при замене $d$ на $r$ .

Доказательство.

Покроем $[m_{0},M_{0}]$ конечным числом интервалов $[u_{j},v_{j}]\subset(0,\infty)$ , настолько коротких, что

(1-\gamma)v_{j}^{2}\leq(1-\gamma/2)u_{j}^{2},\qquad(1+\gamma)u_{j}^{2}\geq(1+\gamma/2)v_{j}^{2}.

Такое покрытие существует, поскольку обе требуемые верхние границы для $v_{j}/u_{j}$ строго больше единицы. При фиксированном $r$ увеличение параметра $c$ уменьшает вероятность порога один. Сопряжём пороги с помощью общих независимых равномерных меток. Тогда при фиксированных графе и начальном множестве итоговое активное множество убывает по $c$ . Если $c_{n}^{\prime}\in[u_{j},v_{j}]$ , подкритическое сравнение проводится с более лёгкой моделью $c=u_{j}$ , а надкритическое — с более трудной моделью $c=v_{j}$ . Приведённые неравенства обеспечивают отступ $\gamma/2$ . Применим теорему 2 к конечному числу фиксированных концов интервалов и возьмём максимум их констант и оценку вероятности объединения событий ошибок. Если интервал выбирается только на подпоследовательности, продолжим проверяемые размеры начального множества вне этой подпоследовательности нулём для подкритического применения и величиной $n$ для надкритического. Тогда теорема с фиксированными параметрами применима на полной последовательности. Наконец, применим явную оценку числа оставшихся неактивных вершин, чтобы получить логарифмическое утверждение. ∎

Зафиксируем $c>0$ , и пусть $d$ удовлетворяет (8). Для каждого $n$ оставим вероятность порога $\pi=(1-c/d)/d$ неизменной, заменив параметр вероятности ребра $d$ на $r=(1+\delta_{n})d>0$ . Обозначим $\beta=c/d$ . Предположим, что при некоторых фиксированных $0<m\leq M<\infty$

\frac{m}{d}\leq b_{n}^{\prime}:=1-\pi r=\beta-\delta_{n}(1-\beta)\leq\frac{M}{d}.

(28)

Тогда $\delta_{n}=O(1/d)$ , $r/d\to 1$ , и $c_{n}^{\prime}=rb_{n}^{\prime}$ остаётся в фиксированном компактном подынтервале $(0,\infty)$ . Кроме того, $\pi=(1-c_{n}^{\prime}/r)/r$ . Поэтому лемма 10 даёт ведущий масштаб размера начального множества $T_{n}^{\prime}=n(b_{n}^{\prime})^{2}/(2r^{2})$ с обоими исходами при фиксированных отступах и указанными оценками числа оставшихся неактивных вершин. По отношению к базовому масштабу точное отношение этих ведущих выражений равно

\frac{T_{n}^{\prime}}{nc^{2}/(2d^{4})}=\frac{[1-\delta_{n}(1-\beta)/\beta]^{2}}{(1+\delta_{n})^{2}}=\left(1-\frac{\delta_{n}}{\beta(1+\delta_{n})}\right)^{2}.

(29)

Выражение до возведения в квадрат положительно при условии (28). Следовательно, это отношение стремится к единице тогда и только тогда, когда $\delta_{n}=o(\beta)=o(1/d)$ . Например, $\delta_{n}=t/d$ при фиксированном $t<c$ даёт предельное отношение $(c-t)^{2}/c^{2}$ . Неположительный или стремящийся к нулю нормированный дефицит находится вне условия (28); возведение в квадрат не расширяет туда область действия теоремы. Предположим, что каждое смещение в полосе $|\delta|\leq\varepsilon_{n}$ удовлетворяет (28) с одними и теми же фиксированными константами $m,M$ . Тогда ведущий коэффициент сохраняется с относительной ошибкой $o(1)$ равномерно по полосе тогда и только тогда, когда $\varepsilon_{n}=o(1/d)$ . Необходимость следует уже из крайней точки $\delta=-\varepsilon_{n}$ , а достаточность — из (29). Это утверждение о полной полосе, а не о фактическом смещении, которое может быть существенно меньше своей верхней границы.

Предложение 11 (Статическое включение с точностью до коэффициента).

Пусть $d=d_{n}$ целое, $nd$ чётно, $d\to\infty$ и $d=o(n^{1/7})$ , и пусть $0\leq\varepsilon_{n}=o(1/d)$ . Для любого сопряжения на одном и том же помеченном множестве вершин

G^{-}\sim G(n,(1-\varepsilon_{n})d/n),\qquad G_{\rm R}\sim G_{n,d},

где $G_{n,d}$ — равномерный простой $d$ -регулярный граф,

\Pr(G^{-}\subseteq G_{\rm R})\leq\tfrac{1}{2}+o(1).

Остаточный член можно выбрать независимо от сопряжения. В частности, включение не может выполняться с вероятностью, стремящейся к единице.

Доказательство.

В любой фиксированной вершине пусть $Y$ — её степень в $G^{-}$ . Положим $p=(1-\varepsilon_{n})d/n$ и $N=n-1$ . Тогда

Y\sim\operatorname{Bin}(N,p),\quad\mu=Np=(1-\varepsilon_{n})d(1-1/n),\quad\sigma^{2}=Np(1-p)\sim d\longrightarrow\infty,

d-\mu=\varepsilon_{n}d+(1-\varepsilon_{n})d/n=o(1).

Для полноты запишем $Y-\mu=\sum_{j=1}^{N}Z_{j}$ с независимыми центрированными бернуллиевскими слагаемыми. При фиксированном вещественном $t$

\mathbb{E}e^{itZ_{j}/\sigma}=1-\frac{t^{2}\mathbb{E}Z_{j}^{2}}{2\sigma^{2}}+\rho_{j},\qquad\sum_{j}|\rho_{j}|\leq\frac{|t|^{3}}{6\sigma^{3}}\sum_{j}\mathbb{E}|Z_{j}|^{3}\leq\frac{|t|^{3}}{6\sigma}\longrightarrow 0.

Максимальный модуль членов, добавляемых к единице, стремится к нулю, а сумма их модулей ограничена. Поэтому логарифмирование их произведения даёт $-t^{2}/2+o(1)$ . Таким образом, $(Y-\mu)/\sigma$ сходится по распределению к стандартной нормальной величине. Поскольку $(d-\mu)/\sigma\to 0$ , $\Pr(Y\leq d)\to 1/2$ . Включение в $d$ -регулярный граф требует $Y\leq d$ при любом сопряжении. Поэтому его вероятность ограничена той же маргинальной вероятностью, что доказывает утверждение. ∎

Вместе с (29) это препятствует прямому переносу ведущего коэффициента через статическое двустороннее включение относительной ширины $o(1/d)$ в общем диапазоне степеней. Это не исключает более грубых двусторонних включений или других аргументов сравнения.

6 Детерминированные поправки при конечных степенях

Теперь уточним квадратичное приближение $A=b^{2}/(2K)$ , используя детерминированные функции отклика. Предположения сформулированы локально: эти вычисления не требуют диапазонов степеней, используемых в вероятностных теоремах.

\alpha_{\rm det}=\max_{0\leq z\leq 1/2}R(z),\qquad R(z)=\frac{z-F(z)}{1-F(z)}.

(30)

Действительно, $h_{\alpha}(z)=(1-F(z))(\alpha-R(z))$ , и $1-F(z)>0$ на этом интервале. Этот барьер уточняет детерминированное квадратичное приближение; он не устанавливает центр случайного критического окна при конечном $n$ .

6.1 Точный барьер для регулярной модели

Для регулярных степеней пусть $d\geq 4$ и $0\leq\pi<1/(d-1)$ , и положим $b=1-\pi(d-1)\in(0,1]$ . Детерминированный барьер задаётся явно:

\widehat{z}_{\rm reg}=\frac{b}{(d-2)(d-3+b)},\qquad\alpha_{\rm det}^{\rm reg}=1-\frac{(1+b/(d-3))^{d-3}}{(1+b/(d-2))^{d-2}}.

Действительно, $R_{d}=1-J_{d}^{-1}$ , где $J_{d}=(1-z)^{d-3}[1+(d-3+b)z]$ , и $J_{d}^{\prime}=(1-z)^{d-4}[b-(d-2)(d-3+b)z]$ . Точка максимума удовлетворяет $0<\widehat{z}_{\rm reg}\leq 1/(d-2)^{2}\leq 1/4$ , поэтому принадлежит интервалу в (30). При $\pi=0$ это сводится к формуле отклика для порога два из работы Balogh and Pittel (2007); здесь она используется только как детерминированное тождество. При выборе $\pi=(1-c/d)/d$ положим $m=d-3$ . Логарифм $J_{d}(\widehat{z}_{\rm reg})$ равен

\ell=(m+1)\log(1+b/(m+1))-m\log(1+b/m)=\frac{b^{2}}{2m(m+1)}+O(d^{-6}).

Линейные члены сокращаются; разность кубических членов равна $\frac{b^{3}}{3}[(m+1)^{-2}-m^{-2}]=O(d^{-6})$ , а каждый остаток четвёртого порядка равен $O(d^{-7})$ . Поскольку $\alpha_{\rm det}^{\rm reg}=1-e^{-\ell}=\ell+O(d^{-8})$ , формулы $b=(c+1)/d-c/d^{2}$ и $[m(m+1)]^{-1}=d^{-2}(1+5/d+O(d^{-2}))$ дают

\alpha_{\rm det}^{\rm reg}=\frac{(c+1)^{2}}{2d^{4}}+\frac{(c+1)(3c+5)}{2d^{5}}+O(d^{-6}).

6.2 Общая последовательность степеней

Предложение 12 (Разложение при конечных степенях).

Зафиксируем $c>0$ , $C\geq 0$ и $\kappa>0$ . Пусть $D$ имеет эмпирическое распределение неотрицательных целых чисел $d_{1},\ldots,d_{n}$ с точным средним $d\to\infty$ , и предположим, что

\max_{i}|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\operatorname{Var}(D)/d,\qquad\rho=c+1-v_{n}\geq\kappa.

Положим $\pi=d^{-1}-cd^{-2}$ и $(x)_{j}=x(x-1)\cdots(x-j+1)$ . Для достаточно больших $d$ определим

\begin{split}B(z)&=\frac{1}{d}\mathbb{E}\!\left[D\left\{(1-z)^{D-1}+(1-\pi)(D-1)z(1-z)^{D-2}\right\}\right],\qquad F=1-B,\\ R(z)&=\frac{z-F(z)}{1-F(z)},\qquad\alpha_{\rm det}=\max_{0\leq z\leq 1/2}R(z),\\ b&=1-\pi\frac{\mathbb{E}[(D)_{2}]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[(D)_{3}]}{d},\qquad A=\frac{b^{2}}{2K},\\ L_{3}&=-(2-3\pi)\frac{\mathbb{E}[(D)_{4}]}{d},\qquad L_{4}=(3-4\pi)\frac{\mathbb{E}[(D)_{5}]}{d}.\end{split}

Максимум достигается единственным образом в точке

\widehat{z}=\frac{b}{K}-\frac{L_{3}b^{2}}{2K^{3}}+\frac{b^{2}}{2K^{2}}+O(d^{-7}),

(31)

\begin{split}\alpha_{\rm det}={}&A-\frac{L_{3}b^{3}}{6K^{3}}+\frac{Ab}{K}-A^{2}\\ &+\frac{L_{3}^{2}b^{4}}{8K^{5}}-\frac{L_{4}b^{4}}{24K^{4}}+O(d^{-9}).\end{split}

(32)

Все коэффициенты здесь являются точными эмпирическими моментами. Остатки равномерны при фиксированных $c,C,\kappa$ ; ни предел $v_{n}$ , ни соотношение между $n$ и $d$ не требуются. Это утверждение о детерминированном отклике, а не о реализуемости последовательности степеней или случайном критическом окне.

Доказательство.

Проверка детерминированного отклика P в разделе 2.2 использует в точности предположения этого предложения. Она даёт $F^{\prime}(0)=1-b$ , $F^{\prime\prime}(0)=K$ , $F^{\prime\prime\prime}(0)=L_{3}$ , $F^{\prime\prime\prime\prime}(0)=L_{4}$ и $|F^{(j)}|=O(d^{j})$ для $2\leq j\leq 5$ на раннем интервале. Лемма 7 даёт единственную точку глобального максимума в $(0,8b/K)$ , причём $b\asymp d^{-1}$ , $K\asymp d^{2}$ и $A\asymp d^{-4}$ . Диапазон степеней из вероятностных результатов не используется.

Положим $z_{0}=b/K$ и $N=z-F$ . На $[0,8b/K]$

N(z)=bz-Kz^{2}/2-L_{3}z^{3}/6-L_{4}z^{4}/24+O(d^{5}z^{5}),\qquad R^{\prime\prime}(z)=-K(1+O(d^{-2})).

Здесь $z_{0}=O(d^{-3})$ , $L_{3}=O(d^{3})$ и $L_{4}=O(d^{4})$ . В точке $z_{0}$ числитель $R^{\prime}$ равен

N^{\prime}(z_{0})B(z_{0})+N(z_{0})F^{\prime}(z_{0})=-L_{3}z_{0}^{2}/2+A+O(d^{-5}).

Теорема о среднем сначала даёт $\widehat{z}-z_{0}=O(d^{-5})$ ; затем то же тождество и оценка кривизны дают (31). Обозначив $\delta_{3}=-L_{3}z_{0}^{2}/(2K)$ , имеем $\widehat{z}-z_{0}=\delta_{3}+O(d^{-6})$ . Выделение полного квадрата даёт

N(\widehat{z})=A-L_{3}z_{0}^{3}/6-L_{4}z_{0}^{4}/24+L_{3}^{2}z_{0}^{4}/(8K)+O(d^{-10}).

Действительно, отброшенные члены ограничены константами, умноженными на $d^{5}z_{0}^{5}$ , $Kd^{-12}$ , $|L_{3}|z_{0}\delta_{3}^{2}$ и $|L_{4}|z_{0}^{3}|\delta_{3}|$ , причём каждая из этих четырёх величин равна $O(d^{-10})$ . Наконец, $F(\widehat{z})=z_{0}-A+O(d^{-5})$ , откуда

R(\widehat{z})=N(\widehat{z})(1+F(\widehat{z})+O(F(\widehat{z})^{2}))=N(\widehat{z})+Az_{0}-A^{2}+O(d^{-9}).

Таким образом, знаменатель оставляет остаток $O(d^{-9})$ , хотя остаток числителя выше равен $O(d^{-10})$ . Это доказывает утверждение. ∎

Разложение разделяет три уровня информации о степенях. Ведущий член зависит от $v_{n}$ через дефицит избыточной степени. Третий центральный момент впервые может дать вклад абсолютного порядка $d^{-11/2}$ . После согласования первых трёх моментов различие четвёртых моментов порядка $d^{2}$ всё ещё может изменить детерминированный барьер на величину порядка $d^{-8}$ . Теперь приведём коэффициенты и явный пример.

6.3 Дисперсия, асимметрия и два значения степени

Пусть $\mu_{j}=\mathbb{E}[(D-d)^{j}]$ , $\rho=c+1-v_{n}$ , $r=c(v_{n}-1)$ , $k_{1}=3v_{n}-5$ и $k_{2}=8-9v_{n}+2c$ . Точные тождества

b=\rho/d+r/d^{2},\qquad K=\left(1-\frac{2}{d}+\frac{2c}{d^{2}}\right)\left[d^{2}+(3v_{n}-3)d+2-3v_{n}+\frac{\mu_{3}}{d}\right]

и $\mu_{3}=O(d^{3/2})$ при разложении (32) дают

\begin{split}\alpha_{\rm det}=\frac{\rho^{2}}{2d^{4}}\bigg[1&+\frac{2r/\rho-k_{1}}{d}-\frac{\mu_{3}}{d^{3}}\\ &+\frac{r^{2}/\rho^{2}+k_{1}^{2}-k_{2}-2rk_{1}/\rho+2\rho/3}{d^{2}}+O(d^{-5/2})\bigg].\end{split}

(33)

Член $2\rho/3$ возникает из кубического отклика; поправка знаменателя $Ab/K$ имеет абсолютный порядок $d^{-7}$ и не входит в приведённый относительный коэффициент при $d^{-2}$ . Если $\mu_{3}=0$ , остаток внутри скобок улучшается до $O(d^{-3})$ . Для равных эмпирических масс в точках $d-s$ и $d+s$ потребуем чётность $n$ и неотрицательные целочисленные значения $d-s,d+s$ ; тогда в точности $v_{n}=s^{2}/d$ и $\mu_{3}=0$ . Применения к графам также требуют чётной суммарной степени $nd$ и предположений вероятностной теоремы для заданных степеней. Абсолютный остаток в (33) равен $O(d^{-13/2})$ , или $O(d^{-7})$ при $\mu_{3}=0$ ; это не остаток $O(d^{-9})$ формулы с точными коэффициентами. Эти разложения используют фактические эмпирические моменты при $c+1-v_{n}\geq\kappa>0$ . Предел дисперсии необязателен и без указания скорости сходимости не может заменить $v_{n}$ в поправочных членах. Например, при целом $d$ и фиксированном $0\leq v<c+1$ выбор $s=\lfloor\sqrt{vd}\rfloor$ даёт $v_{n}=v+O(d^{-1/2})$ ; эта ошибка может превышать первую относительную поправку порядка $d^{-1}$ .

6.4 Различие за пределами дисперсии

Третий центральный момент может через $K$ вносить в барьер поправку порядка $d^{-11/2}$ , как показывает (33). Даже согласование этого момента оставляет дальнейшее различие. Действительно, разложение четвёртого факториального момента даёт

\frac{\mathbb{E}[(D)_{4}]}{d}=d^{3}+(6v_{n}-6)d^{2}+(11-18v_{n})d+(11v_{n}-6)+(4-6/d)\mu_{3}+\frac{\mu_{4}}{d}.

Для двух распределений степеней с одинаковыми $d,v_{n},\mu_{3}$ и общей оценкой отклонений величины $b,K$ совпадают точно. Разность их $L_{3}$ равна $-(2-3\pi)(\mu_{4,2}-\mu_{4,1})/d=O(d)$ , тогда как разность их $L_{4}$ равна $O(d^{2})$ : это следует из разложения $(D)_{5}$ и использования $\mu_{4}=O(d^{2})$ , $\mu_{5}=O(d^{5/2})$ . Следовательно, разности членов с $L_{3}^{2}$ и $L_{4}$ в (32) равны $O(d^{-10})$ , и

\alpha_{{\rm det},2}-\alpha_{{\rm det},1}=\frac{(2-3\pi)b^{3}}{6dK^{3}}(\mu_{4,2}-\mu_{4,1})+O(d^{-9}).

(34)

Для конкретного примера возьмём целое $s\to\infty$ и положим $d=s^{2}$ . Распределение с массой $1/2$ в каждой из точек $d-s,d+s$ и распределение с массой $3/4$ в точке $d$ и $1/8$ в каждой из точек $d-2s,d+2s$ оба имеют $v_{n}=1$ и $\mu_{3}=0$ . Их четвёртые центральные моменты отличаются на $3d^{2}$ , поэтому

\alpha_{{\rm det},2}-\alpha_{{\rm det},1}=c^{3}d^{-8}+O(d^{-9}).

Оба являются эмпирическими распределениями степеней, когда $n$ делится на восемь, и допустимые последовательности можно выбрать в (3). Это различает детерминированные барьеры при одинаковых среднем и дисперсии; случайные различия порогов на этом масштабе не устанавливаются.

6.5 Отклик для независимых рёбер

Зафиксируем $c>0$ и положим $\pi=d^{-1}-cd^{-2}$ . Пуассоновский отклик и его детерминированный барьер имеют вид

Q(x)=1-e^{-x}[1+(1-\pi)x],\qquad P(z)=\frac{z-Q(dz)}{1-Q(dz)},\qquad\alpha_{{\rm E},{\rm Pois}}=\max_{0\leq z\leq 1/2}P(z).

При $d\to\infty$ расчёт по формуле Тейлора из предложения 12, применённый непосредственно к $F_{\rm E}(z)=Q(dz)$ , использует точные коэффициенты

b_{\rm E}=c/d,\quad K_{\rm E}=(1-2\pi)d^{2},\quad L_{3,\rm E}=-(2-3\pi)d^{3},\quad L_{4,\rm E}=(3-4\pi)d^{4}.

Он даёт (32) с этими коэффициентами и $A_{\rm E}^{\rm quad}=b_{\rm E}^{2}/(2K_{\rm E})$ , и, в частности,

\alpha_{{\rm E},{\rm Pois}}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-4c/3}{d^{2}}\right]+O(d^{-7}).

(35)

Оценки производных и локализации, необходимые для этого расчёта, проверены в доказательстве ниже; предположение об ограниченном носителе распределения степеней для пуассоновского отклика не требуется.

Предложение 13 (Биномиальный барьер в целочисленные моменты времени).

Пусть $n$ целое, $d\to\infty$ и $n/d^{3}\to\infty$ . Положим $p=d/n$ и для целых $0\leq t\leq\lfloor n/2\rfloor$ определим

q(t)=1-(1-p)^{t}\left[1+\frac{(1-\pi)tp}{1-p}\right],\qquad\beta_{n}=\max_{0\leq t\leq\lfloor n/2\rfloor}\frac{t/n-q(t)}{1-q(t)}.

Максимум берётся по целым числам, и $q(0)=0$ . Тогда

|\beta_{n}-\alpha_{{\rm E},{\rm Pois}}|=O\left(\frac{1}{nd}+\frac{d^{2}}{n^{2}}\right),

(36)

\beta_{n}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-4c/3}{d^{2}}\right]+O\left(d^{-7}+\frac{1}{nd}+\frac{d^{2}}{n^{2}}\right).

(37)

Константы в (36) и (37) зависят только от $c$ . При условии $d^{5}/n\to 0$ последний остаток равен $o(d^{-6})$ . Остаток $O(d^{-7})$ получается, если дополнительно $d^{6}=O(n)$ . Полное выражение с точными коэффициентами (32), с приведёнными выше пуассоновскими коэффициентами, переносится на $\beta_{n}$ с остатком $O(d^{-9})$ , если $d^{8}=O(n)$ . Константы в этих упрощённых остатках могут также зависеть от ограничений на $d^{6}/n$ или $d^{8}/n$ соответственно.

Доказательство.

Все утверждения относятся к достаточно большим $d$ , поэтому $0<\pi<1$ и $p<1/2$ . Для $x=tp$ , $r=t[-\log(1-p)-p]$ и $A_{x}=1+(1-\pi)x$

1-q(t)=e^{-x-r}\left[A_{x}+\frac{(1-\pi)xp}{1-p}\right],\qquad 0\leq r\leq\frac{xp}{2(1-p)}.

Используя $1-e^{-r}\leq r$ и ограниченность $e^{-x}(1+x)$ на $x\geq 0$ , получаем при $z=t/n$

|q(t)-Q(x)|\leq e^{-x}\left[A_{x}r+\frac{(1-\pi)xp}{1-p}\right]\leq C_{1}xp=C_{1}d^{2}z/n.

(38)

В силу проверки отклика и леммы 7 пуассоновский барьер имеет единственную точку максимума $z_{P}\in(0,8b_{\rm E}/K_{\rm E})$ . При фиксированном $L>8b^{*}/K_{*}$ его отклик удовлетворяет $F_{\rm E}-z\geq kd^{2}z^{2}$ на $[L/d^{3},\varepsilon/d]$ и $F_{\rm E}-z\geq k$ на $[\varepsilon/d,1/2]$ . Это оценки числителя до какого-либо сравнения знаменателей. Отношения ошибок отклика в (38) не превышают $C/(nz)\leq Cd^{3}/(Ln)=o(1)$ на среднем интервале и $O(d^{2}/n)=o(1)$ на позднем интервале; здесь используется только $n/d^{3}\to\infty$ . Поэтому $q(t)>t/n$ в каждой точке сетки вне $[0,L/d^{3}]$ ; соответствующие значения биномиального барьера отрицательны, поскольку $1-q(t)>0$ .

На $[0,L/d^{3}]$ имеем $|F_{\rm E}^{(j)}|=O(d^{j})$ для $2\leq j\leq 5$ , $F_{\rm E}^{\prime}=O(1)$ и $P^{\prime\prime}=-K_{\rm E}(1+O(d^{-2}))$ . Поэтому уже доказанный расчёт по формуле Тейлора даёт $z_{P}\asymp d^{-3}$ , $\alpha_{{\rm E},{\rm Pois}}\asymp d^{-4}$ и полное разложение с точными коэффициентами. Разлагая

A_{\rm E}^{\rm quad}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-2c}{d^{2}}+O(d^{-3})\right]

и добавляя $-L_{3,\rm E}b_{\rm E}^{3}/(6K_{\rm E}^{3})=c^{3}/(3d^{6})+O(d^{-7})$ , доказываем (35); остальные члены начинаются с порядка $d^{-7}$ .

Только на локализованном интервале мы сравниваем знаменатели. Там $F_{\rm E}=O(d^{-3})$ и в силу (38) $q=O(d^{-3})$ в точках сетки, поэтому оба знаменателя равны $1-O(d^{-3})$ . Точное тождество

\frac{z-q(t)}{1-q(t)}-P(z)=-\frac{(1-z)(q(t)-F_{\rm E}(z))}{(1-q(t))(1-F_{\rm E}(z))}

затем ограничивает разность величиной $C_{3}/(nd)$ . Выберем целое $t_{P}$ , ближайшее к $nz_{P}$ . Поскольку $n/d^{3}\to\infty$ , соответствующая точка сетки лежит внутри раннего интервала и внутри $[0,\lfloor n/2\rfloor/n]$ . Стационарность $P^{\prime}(z_{P})=0$ и $|P^{\prime\prime}|=O(d^{2})$ дают

P(t_{P}/n)=\alpha_{{\rm E},{\rm Pois}}+O(d^{2}/n^{2}).

Обе величины $1/(nd)$ и $d^{2}/n^{2}$ равны $o(d^{-4})$ . Поэтому значение биномиального барьера в этой точке сетки положительно; максимум биномиального барьера находится на раннем участке. Сравнение в этой точке даёт нижнюю оценку в (36), а сравнение в точке максимума биномиального барьера — верхнюю. Единственность целочисленной точки максимума не требуется.

Объединяя это с (35), доказываем (37). При условии $d^{5}/n\to 0$ имеем $d^{8}/n^{2}=(d^{5}/n)^{2}/d^{2}\to 0$ , что доказывает утверждение об $o(d^{-6})$ . Если $d^{6}=O(n)$ , то $(nd)^{-1}=O(d^{-7})$ и $d^{2}/n^{2}=O(d^{-10})$ . Если $d^{8}=O(n)$ , эти ошибки равны соответственно $O(d^{-9})$ и $O(d^{-14})$ , что доказывает утверждение о полном разложении. ∎

Ошибка от целочисленности времени $O(d^{2}/n^{2})$ отличается от округления числа начальных активных вершин. Для целочисленного размера начального множества $a$ и $\alpha=a/n$ точный средний дрейф равен

\frac{a+(n-a)q(t)-t}{n}=(1-q(t))\left(\alpha-\frac{t/n-q(t)}{1-q(t)}\right).

Следовательно, наименьшее целое $a$ , при котором все эти средние дрейфы неотрицательны, равно $\lceil n\beta_{n}\rceil$ ; для строго положительных средних дрейфов оно равно $\lfloor n\beta_{n}\rfloor+1$ . Их ошибки плотности соответственно меньше $1/n$ и не превышают $1/n$ . Эта дополнительная ошибка округления числа начальных активных вершин не входит в (36) или (37). Все эти барьеры относятся к точным детерминированным средним на указанном временном интервале. Они не определяют центр случайного критического окна и не обосновывают сужающиеся относительные отступы в вероятностных теоремах.

7 Область применимости

Результаты относятся к независимым равномерным начальным множествам заданного размера, фиксированным положительным параметрам модели и фиксированным относительным отступам. Они устанавливают почти полную активацию, а не полную, и не определяют оптимальные начальные множества или сужающееся критическое окно. Предположения для заданных степеней накладывают ограничение на отклонения степеней и требуют фиксированного положительного зазора избыточной степени; они не охватывают произвольные распределения степеней с тяжёлыми хвостами или пороги, коррелированные с графом.

Для заданных степеней локальный показатель концентрации $n/d^{5}$ должен доминировать над затратой $O(d^{2})$ на условие простоты и логарифмом множителя сетки; $d=o(n^{1/7})$ также контролирует отдельную позднюю оценку. Для независимых рёбер максимальная оценка эмпирического процесса и диадическое распределение допустимых ошибок дают вероятность неудачи прохождения барьера $O(d^{5}/n)$ , поэтому достаточно $d^{5}/n\to 0$ . Это достаточные диапазоны, а не оптимальные границы.

Явные оценки числа оставшихся неактивных вершин, поделённые на $n$ , стремятся к нулю для каждой допустимой последовательности с $d\to\infty$ .

Следствие 5 даёт достаточные логарифмические условия для $O(n^{2/3})$ оставшихся неактивных вершин. Эти условия не заявляются как необходимые: приложение B также даёт эту оценку в модели с заданными степенями при режиме медленного роста $d\log d=o(\log n)$ . Эта адаптация не устанавливает аналогичный результат для независимых рёбер и не завершает подкритическое сравнение итогового состояния с работой Rossi et al.

Результаты для конечных степеней являются утверждениями о детерминированном отклике. Для биномиального барьера в целочисленные моменты времени трёхчленное разложение имеет абсолютный остаток $O(d^{-7}+(nd)^{-1}+d^{2}/n^{2})$ , равный $o(d^{-6})$ во всём диапазоне теоремы для независимых рёбер. Округление числа начальных активных вершин добавляет отдельную ошибку плотности $O(1/n)$ . Ни одна из этих ошибок не является оценкой стохастического окна.

Если $c+1-v_{n}$ приближается к нулю, точное тождество в (11) показывает, что порядок и знак $b$ требуют отдельного анализа. Выводов для граничного зазора здесь не утверждается. Пустое начальное множество остаётся пустым, поскольку все пороги положительны.

Приложение A Локальная концентрация для процесса исследования графа с заданными степенями

Докажем лемму 8, сохраняя распределение начального множества фиксированного размера. Для независимых центрированных величин, ограниченных по модулю величиной $B$ и имеющих суммарную дисперсию не более $V$ , используем двустороннюю оценку $2\exp[-x^{2}/(2(V+Bx/3))]$ . Для мартингала, начинающегося в нуле, та же оценка применима к его текущему максимуму по модулю, если его скачки ограничены величиной $B$ , а предсказуемая квадратичная вариация не превышает $V$ . Эти оценки следуют из $e^{t}-1-t\leq t^{2}/[2(1-|t|/3)]$ при $|t|<3$ , соответствующего экспоненциального (супер)мартингала и выбора $\lambda=x/(V+Bx/3)$ ; применение для обоих знаков даёт множитель два. Мартингальная оценка применяется только к остановленным процессам с детерминированной оценкой квадратичной вариации.

Потери в одной вершине и среднее для начального множества.

При фиксированном $u$ положим $z=1-e^{-u}$ , и пусть $X\sim\operatorname{Bin}(k,z)$ независимо от $R$ . Для $Y=(k-X)\mathbf{1}_{\{X<R\}}$ запишем

L=k-Y=k\mathbf{1}_{\{X\geq R\}}+\mathbf{1}_{\{R=2,X=1\}}.

Эти два события не пересекаются: при активации теряются все $k$ концов, а вершина с порогом два и одной меткой теряет один. Следовательно,

\operatorname{Var}Y\leq\mathbb{E}L^{2}=k^{2}[\pi\Pr(X\geq 1)+(1-\pi)\Pr(X\geq 2)]+(1-\pi)\Pr(X=1)\leq\pi k^{3}z+kz+k^{4}z^{2}/2,

где используются $\Pr(X\geq 1),\Pr(X=1)\leq kz$ и $\Pr(X\geq 2)\leq k^{2}z^{2}/2$ . При условии фиксированного начального множества слагаемые для разных вершин независимы и лежат в $[0,\Delta]$ . Поэтому

\operatorname{Var}(H(u)\mid A_{0})\leq V(z):=\min\{3n[(\pi\Delta^{3}+\Delta)z+\Delta^{4}z^{2}/2],\ n\Delta^{2}\}.

(39)

Пусть $g_{i}(u)=\mathbb{E}Y_{i}(u)\in[0,\Delta]$ и $m_{A_{0}}(u)=\sum_{i\notin A_{0}}g_{i}(u)$ . Раскроем $a$ меток начальных вершин в случайном порядке без возвращения. При $a<n$ приращение Дуба суммы выборки на извлечении $j$ равно

\frac{n-a}{n-j}\bigl(g_{I_{j}}(u)-\bar{g}_{j-1}(u)\bigr),\qquad 1\leq j\leq a,

где $\bar{g}_{j-1}$ — среднее по ещё не извлечённым меткам. Это следует из представления ожидаемой оставшейся выборки как $a-j$ , умноженного на среднее оставшейся совокупности. Модуль приращения не превышает $\Delta$ , поэтому экспоненциальная оценка для ограниченных приращений даёт

\Pr\{|m_{A_{0}}(u)-\bar{H}(u)|>e\}\leq 2e^{-e^{2}/(2a\Delta^{2})}.

(40)

При $a=0,n$ расхождение равно нулю. Та же оценка включает вариацию степеней начальных вершин при $u=0$ . Для опорных размеров $a\Delta^{2}=O(n/d^{2})$ .

Мартингал остановленной очереди.

Используем фильтрацию процесса исследования графа, которая не раскрывает будущие времена срабатывания часов вручную удалённых концов. Если $J$ считает спаривания до $\tau$ включительно, его компенсатор равен $\int_{0}^{u\wedge\tau}W(s-)\,ds$ : до остановки имеются $W$ незарезервированных часов с интенсивностью один. Фиктивное резервирование в момент остановки делает каждый скачок $W$ равным в точности $-2$ , в том числе в момент $\tau$ . Следовательно,

Z(u)=e^{2(u\wedge\tau)}W(u\wedge\tau)-(M-1)=-2\int_{0}^{u\wedge\tau}e^{2s}(dJ(s)-W(s-)\,ds)

является мартингалом. Для каждого детерминированного $r\leq U$

|\Delta Z|\leq 2e^{2r},\qquad\langle Z\rangle_{r}=4\int_{0}^{r\wedge\tau}e^{4s}W(s-)\,ds\leq 4e^{4r}Mr.

Значение $W(\tau)$ может быть равно $-1$ , если спаривание исчерпано, но интенсивность использует неотрицательное значение перед остановкой $W(s-)$ . Поэтому мартингальное неравенство даёт

\Pr\left\{\sup_{u\leq r\wedge\tau}|W(u)-Me^{-2u}|>e+1\right\}\leq p_{W}(e,r):=2\exp\left[-\frac{e^{2}}{2(4e^{4r}Mr+2e^{2r}e/3)}\right].

(41)

Дополнительная единица учитывает $W(0)=M-1$ .

Интерполяция по времени.

Для любого детерминированного интервала $I=[l,r]\subset[0,U]$ и $e\geq 1$ используем сетку, содержащую оба конца, с шагом не более $e/(4n\Delta^{2})$ . Её размер не превышает $N_{I}=\lceil 4(r-l)n\Delta^{2}/e\rceil+1$ (одна точка для вырожденного интервала). В точке сетки условное неравенство Бернштейна и (40) дают $|H-\bar{H}|\leq 2e$ , кроме события вероятности не более

2\exp\left[-\frac{e^{2}}{2(V(1-e^{-r})+\Delta e/3)}\right]+2\exp[-e^{2}/(2a\Delta^{2})].

Каждый $Y_{i}(u)$ не возрастает. Интенсивность событий часов не превышает $d_{i}$ , а каждая потеря не превышает $d_{i}$ , откуда $|g_{i}^{\prime}(u)|\leq d_{i}^{2}$ . Поэтому обе величины $H$ и $\bar{H}$ не возрастают, и $|\bar{H}^{\prime}|\leq n\Delta^{2}$ . Ограничивая промежуточное значение $H$ двумя соседними значениями на сетке и изменяя среднее не более чем на $e/4$ , получаем $|H-\bar{H}|\leq 9e/4$ на всём $I$ , включая скачки. Объединение с (41) даёт

|Q-D_{\alpha}|\leq 4e+1\quad\hbox{on }I\cap[0,\tau],

(42)

вне события вероятности не более

p_{W}(e,r)+N_{I}\left\{2\exp\left[-\frac{e^{2}}{2(V(1-e^{-r})+\Delta e/3)}\right]+2\exp[-e^{2}/(2a\Delta^{2})]\right\}.

Это оценка вероятности объединения событий, не требующая независимости ни между интервалами, ни между $W$ и $H$ , ни между оценками и продолжением процесса.

Три масштаба и общая вероятность прохождения барьера.

Разобьём интервал по $z$ на $[0,L/d^{3}]$ , диадические интервалы $[s,\min(2s,\eta/d)]$ , начиная с $s=L/d^{3}$ , и $[\eta/d,1/2]$ . Переведём их в переменную $u=-\log(1-z)$ и выберем соответственно допустимые ошибки

e_{0}=\rho n/d^{3},\qquad e_{s}=\rho nd^{3}s^{2},\qquad e_{\rm p}=\rho nd.

Зафиксируем $\rho>0$ достаточно малым по отношению к (15). Минимальная допустимая ошибка стремится к бесконечности, поэтому $4e+1$ меньше половины соответствующего отступа, включая проверку отрицательного дрейфа в $u_{*}$ . На раннем интервале (39) даёт верхнюю оценку $O(n/d)$ ; кроме того, $a\Delta^{2}=O(n/d^{2})$ и $Mr=O(n/d^{2})$ . Поэтому три показателя (неравенства Бернштейна для вершин, для начального множества и для очереди) ограничены снизу константами, умноженными на $n/d^{5},n/d^{4},n/d^{4}$ .

На среднем интервале $r=O(s)$ и $z_{r}\leq 2s$ . Соответствующие показатели имеют нижние оценки

k\frac{nd^{4}s^{3}}{1+d^{2}s},\qquad knd^{8}s^{4},\qquad k\frac{nd^{5}s^{3}}{1+d^{2}s},

соответственно. Здесь $V(z_{r})+\Delta e_{s}\leq Cn(d^{2}s+d^{4}s^{2})$ и $Mr+e_{s}\leq Cnds(1+d^{2}s)$ . Поскольку $s^{3}/(1+d^{2}s)$ возрастает и $s\geq L/d^{3}$ , эти оценки не меньше констант, умноженных на $n/d^{5},n/d^{4},n/d^{4}$ . На последнем интервале используем $V\leq n\Delta^{2}$ : все три показателя не меньше $kn$ . Эта последняя допустимая ошибка относится только к прохождению барьера.

Ранняя сетка имеет $O(1+d^{2})$ точек; средняя сетка — $O(1+1/(ds))=O(1+d^{2})$ точек; поздняя сетка — $O(1+d)$ точек. Всего имеется $O(1+\log d)$ интервалов, поскольку отношение концов среднего участка имеет порядок $d^{2}$ . Суммирование оценок вероятностей неудачи из (42) доказывает (18). Это завершает локальную оценку без глобальной ошибки порядка $n^{2/3}d$ в узком месте.

Приложение B Пересечение с приближением на конечном временном горизонте при медленно растущих степенях

Приведём адаптацию, используемую при сравнении с литературой, не вводя отдельной теоремы о пороге. Зафиксируем $c>0$ , $C\geq 0$ , $\kappa>0$ и $\gamma\in(0,1)$ . Заданные неотрицательные целочисленные степени имеют чётную сумму $nd$ , точное среднее $d$ и удовлетворяют

|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\frac{1}{nd}\sum_{i}(d_{i}-d)^{2},\qquad c+1-v_{n}\geq\kappa,\qquad d\to\infty,\quad d\log d=o(\log n).

Пусть $p_{k}=n^{-1}|\{i:d_{i}=k\}|$ , $\delta=\min_{i}d_{i}$ и $\Delta=\max_{i}d_{i}$ . Независимо от графа пороги независимы с вероятностями $\pi=(1-c/d)/d$ и $1-\pi$ для значений один и два, а начальное множество равномерно среди подмножеств детерминированного размера $a$ . При математическом ожидании по распределению $p_{k}$ положим

b=1-\pi\frac{\mathbb{E}[D(D-1)]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[D(D-1)(D-2)]}{d},\qquad A=\frac{b^{2}}{2K}.

Тогда $b\asymp d^{-1}$ , $K\asymp d^{2}$ и $A\asymp d^{-4}$ равномерно при указанных выше фиксированных параметрах. Покажем, что $a\geq(1+\gamma)nA$ влечёт $n-|A_{\infty}|=O(n^{2/3})$ с вероятностью, стремящейся к единице, на равномерном простом графе. Вероятность учитывает граф, пороги и начальное множество. Поскольку $nA\to\infty$ , в силу пункта 2.1 достаточно использовать $a_{0}=\lceil(1+\gamma/2)nA\rceil$ и $\alpha=a_{0}/n$ .

На неориентированных деревьях рекурсия для некорневой вершины исключает родительское ребро, как в лемме 4 принятой рукописи работы Rossi et al. (2019).

Опубликованная теорема 2 ссылается на рекурсию (7), формулы (13)–(14) которой используют $k$ испытаний вместо $k-1$ . Поэтому мы напрямую доказываем оценку на конечном временном горизонте, необходимую для рекурсии с избыточной степенью, следуя стратегии сопряжения и концентрации из раздела 4.2 работы Rossi et al. (2019).

Лемма 14 (Приближение на конечном временном горизонте для неориентированного спаривания).

Зафиксируем степени $d_{i}\geq 0$ с чётной суммой $M=nd>0$ и максимумом $\Delta\geq 2$ , а также целочисленные пороги $r_{i}$ и метки $s_{i}$ , где $s_{i}\in\{0,1\}$ , $r_{i}=0$ , если $s_{i}=1$ , и $r_{i}\geq 1$ в противном случае. Пусть $u_{k,r,s}=n^{-1}|\{i:(d_{i},r_{i},s_{i})=(k,r,s)\}|$ . На равномерном спаривании помеченных полурёбер запустим синхронную необратимую активацию с этими начальными состояниями и порогами, учитывая кратность рёбер, и пусть $Z_{t}=|A_{t}|/n$ . Положим $B_{m,r}(x)=\Pr\{\operatorname{Bin}(m,x)\geq r\}$ , причём $B_{m,0}=1$ и $B_{m,r}=0$ при $r>m$ , и определим

f_{u}(x)=\sum_{k\geq 1,r,s}\frac{ku_{k,r,s}}{d}B_{k-1,r}(x),\qquad g_{u}(x)=\sum_{k,r,s}u_{k,r,s}B_{k,r}(x),

x_{0}=\sum_{k,r}\frac{ku_{k,r,1}}{d},\qquad y_{0}=\sum_{k,r}u_{k,r,1},\qquad x_{j+1}=f_{u}(x_{j}),\quad y_{j+1}=g_{u}(x_{j}).

Для целого $t\geq 1$ положим

Q_{t}=\sum_{j=1}^{t}\Delta^{j},\qquad b_{t}=\frac{\Delta Q_{t}(Q_{t}+1)}{2M}.

Если $M\geq 2Q_{t}+2$ , то $|\mathbb{E}Z_{t}-y_{t}|\leq b_{t}$ . Для каждого $h>0$ без этого ограничения на размер

\Pr\{|Z_{t}-\mathbb{E}Z_{t}|>h\}\leq 2\exp\left(-\frac{nh^{2}}{128d\Delta^{2t}}\right).

Следовательно, если также $b_{t}\leq\varepsilon/2$ , то

\Pr\{|Z_{t}-y_{t}|>\varepsilon\}\leq 2\exp\left(-\frac{n\varepsilon^{2}}{512d\Delta^{2t}}\right).

Все эти оценки равномерны по фиксированным меткам. Если же метки $(r_{i},s_{i})$ независимы и одинаково распределены, независимо от спаривания, с распределением $\lambda_{r,s}$ , оценка математического ожидания справедлива с $u_{k,r,s}=p_{k}\lambda_{r,s}$ , где $p_{k}=n^{-1}|\{i:d_{i}=k\}|$ . Знаменатель в оценке концентрации становится $(128d+8)\Delta^{2t}$ , а знаменатель в объединённой оценке — $(512d+32)\Delta^{2t}$ . Здесь вероятность учитывает спаривание и метки.

Доказательство.

Выберем равномерную корневую вершину. Её тип имеет распределение $u$ . Для каждой некорневой вершины независимого дерева сравнения выберем с возвращением равномерное полуребро из всех $M$ полурёбер и используем тип инцидентной ему вершины. Эти независимые типы имеют распределение $ku_{k,r,s}/d$ . Корень имеет $k$ потомков, а каждая некорневая вершина степени $k$ — $k-1$ потомков.

На дереве удаление родительского ребра не меняет вклад потомка в первую активацию его родителя: до этой активации родитель был неактивен во все предшествующие моменты времени. Поэтому индукция по времени с применением этого наблюдения к каждому поддереву потомка отождествляет состояние корня с расчётом на дереве, ориентированном от корня. Если начальные активные вершины кодируются нулевым порогом, состояния в этом расчёте не убывают по времени. Тогда независимые поддеревья дают в точности приведённые выше рекурсии, а вероятность активации корня в момент $t$ равна $y_{t}$ .

Исследуем спаривание поиском в ширину из того же корня, раскрывая рёбра только из вершин на расстоянии меньше $t$ . Требуется не более $Q_{t}$ партнёров. После $h$ успешных обнаружений новых вершин дерева просмотрено не более $h+1$ вершин. Выберем следующее полуребро сравнения $U$ равномерно из всех $M$ полурёбер. Если оно является допустимым партнёром текущего полуребра, используем его в спаривании; иначе независимо выберем равномерного допустимого партнёра. Это правило даёт равномерного партнёра: каждое допустимое полуребро имеет вероятность $1/|E|$ , где $E$ — множество допустимых партнёров. Все недопустимые полурёбра принадлежат уже просмотренным вершинам. Поэтому до первой неудачи, если $U$ принадлежит ещё не просмотренной вершине, оба построения совпадают и обнаруживают новую вершину. Объявим неудачу всякий раз, когда $U$ принадлежит просмотренной вершине. Её условная вероятность не превышает $(h+1)\Delta/M$ . Ограничение на размер обеспечивает наличие партнёров в ходе этого процесса исследования. Оценка вероятности объединения событий даёт вероятность неудачи не более

\sum_{h=0}^{Q_{t}-1}\frac{(h+1)\Delta}{M}=b_{t}.

Нераскрытые рёбра, инцидентные только вершинам глубины $t$ , не могут влиять на состояние корня к моменту $t$ . Достроим оставшееся спаривание равномерно. Сопряжённые состояния корня совпадают вне события неудачи, что доказывает оценку математического ожидания.

Для концентрации сгенерируем равномерное спаривание с помощью равномерной перестановки $M$ полурёбер и спарим последовательные позиции. Транспозиция меняет не более двух пар и затрагивает не более четырёх концевых вершин. Состояние в момент $t$ может измениться только на расстоянии не более $t-1$ от этих концов хотя бы в одном из двух графов. Каждый такой шар содержит не более $\sum_{j=0}^{t-1}\Delta^{j}\leq\Delta^{t}$ вершин. Поэтому число активных вершин меняется не более чем на $8\Delta^{t}$ при любой транспозиции. Эта оценка также охватывает петли и кратные рёбра.

Раскроем перестановку по одной позиции. Условные продолжения для двух возможных следующих значений находятся во взаимно однозначном соответствии через транспозицию этих значений в оставшихся позициях. Поэтому их ожидаемые числа активных вершин различаются не более чем на $8\Delta^{t}$ . Каждое приращение мартингала Дуба для $|A_{t}|$ ограничено по модулю величиной $8\Delta^{t}$ . Неравенство Азумы с не более чем $M$ приращениями даёт

\Pr\{\big||A_{t}|-\mathbb{E}|A_{t}|\big|>nh\}\leq 2\exp\left(-\frac{n^{2}h^{2}}{2M(8\Delta^{t})^{2}}\right),

что и является заявленной оценкой концентрации. Выбор $h=\varepsilon/2$ и оценка математического ожидания доказывают последнее утверждение. Для независимых одинаково распределённых меток то же сопряжение при поиске в ширину переносит новую независимую метку каждой впервые обнаруженной вершины на её экземпляр в дереве; при первом повторении вершины назначим этому экземпляру новую независимую метку и независимо заполним остальное дерево сравнения. Порядок обнаружения не использует метки, поэтому получается усреднённое распределение типов $p_{k}\lambda_{r,s}$ и то же смещение $b_{t}$ .

Для концентрации раскроем перестановку спаривания, а затем независимые метки. Изменение одной метки влияет только на шар радиуса $t$ вокруг соответствующей вершины, содержащий не более $\sum_{j=0}^{t}\Delta^{j}\leq 2\Delta^{t}$ вершин. Поэтому дополнительные $n$ мартингальных приращений ограничены величиной $2\Delta^{t}$ . Сумма квадратов ограничений на приращения равна $(64M+4n)\Delta^{2t}$ ; неравенство Азумы даёт знаменатель $(128d+8)\Delta^{2t}$ . Выбор $h=\varepsilon/2$ даёт объединённую оценку. ∎

Сначала используем независимые одинаково распределённые начальные состояния с распределением Бернулли $(\alpha)$ , независимо от порогов и спаривания. Средние отображения на дереве имеют вид

f_{\alpha}(x)=\alpha+(1-\alpha)F_{\rm P}(x),

g_{\alpha}(x)=1-(1-\alpha)\sum_{k}p_{k}\big[(1-x)^{k}+(1-\pi)kx(1-x)^{k-1}\big].

Положим $x_{0}=y_{0}=\alpha$ , $x_{t+1}=f_{\alpha}(x_{t})$ и $y_{t+1}=g_{\alpha}(x_{t})$ .

Лемма 7 применима к среднему отклику P и $\alpha=(1+\gamma/2)A+o(A)$ . Приращения $f_{\alpha}(x)-x$ не меньше $kd^{-4}$ вплоть до $L/d^{3}$ , $kd^{2}x^{2}$ вплоть до $\varepsilon/d$ и $k$ вплоть до $1/2$ . Первый интервал требует $O(d)$ шагов. Пересечение каждого диадического интервала $[s,2s]$ требует не более $1+C/(d^{2}s)$ шагов. Их сумма равна $O(d)$ , поскольку $s$ начинается с $L/d^{3}$ и $\sum_{j}2^{-j}<\infty$ . Оставшийся интервал требует $O(1)$ шагов. Поэтому фиксированное $L_{0}$ даёт $x_{T_{0}}\geq 1/2$ при $T_{0}=\lceil L_{0}d\rceil$ .

При $q_{t}=1-x_{t}\leq 1/2$ приведённые отклики начиная с некоторого индекса дают

q_{t+1}\leq(1+\Delta)q_{t}^{\delta-2}\leq q_{t}^{\delta/2},\qquad 1-g_{\alpha}(x_{t})\leq(1+\Delta)q_{t}^{\delta-1}\leq q_{t}^{\delta/2}.

Во вторых неравенствах используется $\log(1+\Delta)=o(\delta)$ ; они остаются справедливыми при $q_{t}=0$ . Выберем

r=\max\left\{0,\left\lceil\frac{\log((\log n)/(3\log 2))}{\log(\delta/2)}\right\rceil\right\},\qquad T=T_{0}+r+1.

Тогда $1-y_{T}\leq n^{-1/3}$ и $T\log(\Delta+1)=O(d\log d+\log\log n)=o(\log n)$ .

Применим часть леммы 14 для независимых одинаково распределённых меток при $t=T$ с $\varepsilon=n^{-1/3}$ . Поскольку $Q_{T}\leq 2\Delta^{T}=n^{o(1)}$ , начиная с некоторого индекса $nd\geq 2Q_{T}+2$ и $b_{T}=n^{-1+o(1)}\leq\varepsilon/2$ . Вероятность неудачи не превышает

2\exp\left[-\frac{n^{1/3}}{(512d+32)\Delta^{2T}}\right].

Теперь перейдём к условию, что начальных активных вершин ровно $a_{0}$ и граф прост. Число начальных активных вершин $a_{0}$ является модой $\operatorname{Bin}(n,a_{0}/n)$ с вероятностью не менее $1/(n+1)$ ; переход к этому условию даёт равномерное начальное множество размера $a_{0}$ . Спаривание и метки независимы, поэтому пороги остаются независимыми одинаково распределёнными и независимыми от этого начального множества и равномерного простого графа. Оценка McKay–Wormald из раздела 3 применима в диапазоне медленного роста и даёт $s_{n}\geq e^{-C_{0}d^{2}}>0$ , одновременно доказывая реализуемость последовательности степеней. Полученная общая вероятность неудачи не превышает

2(n+1)\exp\left[C_{0}d^{2}-\frac{n^{1/3}}{(512d+32)\Delta^{2T}}\right]=o(1),

поскольку $d=n^{o(1)}$ , $\Delta^{2T}=n^{o(1)}$ , а отрицательный показатель доминирует и над $d^{2}$ , и над $\log(n+1)$ . На благоприятном событии $n-|A_{T}|\leq 2n^{2/3}\leq 3n^{2/3}$ . Необратимость активации даёт $A_{T}\subseteq A_{\infty}$ , что доказывает оценку числа оставшихся неактивных вершин. Этот аргумент не устанавливает подкритической верхней оценки итогового состояния и не применим без изменений к модели с независимыми рёбрами.

Сведения об авторе и конфликте интересов

Автор является сотрудником Яндекса. Это исследование проводилось независимо, в личное время автора, и не получало специального финансирования от Яндекса. Для части вычислительной работы использовались оборудование и вычислительная инфраструктура Яндекса. Высказанные взгляды принадлежат исключительно автору и не обязательно отражают взгляды Яндекса. Автор заявляет об отсутствии иных конкурирующих интересов.

Использование ИИ

Агенты GPT-6 Astra от OpenAI использовались как исследовательские помощники для анализа литературы, математических расчётов и работы над доказательствами, а также подготовки рукописи. OpenResearch использовался для организации исследовательских задач, экспериментов и артефактов. Эти инструменты не заменяют независимое рецензирование людьми. Автор несёт ответственность за все математические результаты и окончательный текст рукописи.

Список литературы

Amini (2010) H. Amini. Bootstrap percolation and diffusion in random graphs with given vertex degrees. Electronic Journal of Combinatorics, 17(1), R25, 2010. doi:10.37236/297.
Amini et al. (2023) H. Amini, E. Bayraktar, and S. Chakraborty. A central limit theorem for diffusion in sparse random graphs. Journal of Statistical Physics, 190(3), article 57, 2023. doi:10.1007/s10955-023-03068-9. Нумерация условий, на которую мы ссылаемся, взята из arXiv:2103.00357v2 (2022).
Ballen and Guha (2015) P. Ballen and S. Guha. Behavioral intervention and non-uniform bootstrap percolation. 2015. arXiv:1512.00834v1 (2015).
Balogh and Pittel (2007) J. Balogh and B. G. Pittel. Bootstrap percolation on the random regular graph. Random Structures & Algorithms, 30(1–2):257–286, 2007. doi:10.1002/rsa.20158.
Baxter et al. (2010) G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. Bootstrap percolation on complex networks. Physical Review E, 82(1), 011103, 2010. doi:10.1103/PhysRevE.82.011103. Нумерация разделов и уравнений, на которую мы ссылаемся, взята из arXiv:1003.5583v2 (2010).
Garetto et al. (2016) M. Garetto, E. Leonardi, and G. L. Torrisi. Generalized threshold-based epidemics in random graphs: the power of extreme values. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, ACM, pp. 37–50, 2016. doi:10.1145/2896377.2901455. Использованная версия — arXiv:1603.04643v1.
Janson (2009) S. Janson. On percolation in random graphs with given vertex degrees. Electronic Journal of Probability, 14:87–118, 2009. doi:10.1214/EJP.v14-603.
Janson et al. (2012) S. Janson, T. Łuczak, T. Turova, and T. Vallier. Bootstrap percolation on the random graph $G_{n,p}$ . Annals of Applied Probability, 22(5):1989–2047, 2012. doi:10.1214/11-AAP822. Адаптированные здесь максимальные оценки — это леммы 7.2–7.3 на с. 22–24 в arXiv:1012.3535v2.
Lelarge (2012) M. Lelarge. Diffusion and cascading behavior in random networks. Games and Economic Behavior, 75(2):752–775, 2012. doi:10.1016/j.geb.2012.03.009. Нумерация условий и теорем, на которую мы ссылаемся, относится к arXiv:1012.2062v4 (2011).
McKay and Wormald (1991) B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$ . Combinatorica, 11(4):369–382, 1991. doi:10.1007/BF01275671. PDF опубликованной статьи на сайте B. D. McKay.
Rossi et al. (2019) W. S. Rossi, G. Como, and F. Fagnani. Threshold models of cascades in large-scale networks. IEEE Transactions on Network Science and Engineering, 6(2):158–172, 2019. doi:10.1109/TNSE.2017.2777941. Адаптированная здесь стратегия сопряжения и концентрации изложена в разделах 4.2–4.3.1, с. 7–10, принятой к публикации рукописи 2017 года. Оценка для избыточной степени, использованная здесь, доказывается отдельно в настоящей статье. См. версию из репозитория Университета Твенте.