RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды по дискретной математике // Архив

Тр. по дискр. матем., 2000, том 3, страницы 29–36 (Mi tdm35)

О вероятности вложимости случайного мультиграфа с раскрашенными ребрами в двудольный граф

В. А. Ватутин


Аннотация: Рассматривается динамическая процедура построения случайного графа, описываемая следующим образом. В начальный момент времени имеется множество вершин $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\}. $$




© МИАН, 2024