Аннотация:
Рассматривается динамическая процедура построения случайного графа, описываемая следующим образом. В начальный момент времени имеется множество вершин $V=\{1,2,\dots,N\}$, служащее основой при построении случайного мультиграфа $M=M(2N,m)$, который получается в результате проведения $m$ последовательных двухэтапных независимых испытаний. При каждом испытании на первом этапе из множества $V$ выбираются (независимо от результатов предшествующих испытаний) два ребра по схеме равновероятного выбора с возвращением, а на втором этапе каждому ребру независимо от остальных приписывается тип: с вероятностью 1/2 – нулевой
и с вероятностью 1/2 – первый. В работе получена оценка сверху для вероятности события
$$
B(2N,m)=
\left\{\begin{matrix}
\text{существует такая раскраска вершин множества~$V$}\\
\text{в белый и черный цвета, что количество вершин}\\
\text{каждого цвета равно$N$ и при этом каждое ребро}\\
\text{нулевого типа соединяет вершины одного цвета,}\\
\text{а~каждое ребро первого типа соединяет вершины}\\
\text{разных цветов } \hfill
\end{matrix}\right\}.
$$