RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2006, том 18, выпуск 3, страницы 102–114 (Mi dm63)

Эта публикация цитируется в 2 статьях

Распределения чисел конечных подграфов в случайных неоднородных гиперграфах

А. В. Шаповалов


Аннотация: Рассматриваются два случайных гиперграфа с $n$ вершинами и $M=M(n)$ ребрами, из которых $M_i=M_i(n)$ ребер состоят из $i$ неупорядоченных вершин, $i=0,1,\dots,m$, $M=M_0+M_1+\ldots+M_m$. Выбор вершин для каждого ребра осуществляется случайно, равновероятно из $n$ возможных вершин, для первого случайного гиперграфа по схеме с возвращением, для второго по схеме без возвращения. Исследуются распределения чисел подграфов, изоморфных заданным, при $n\to\infty$, $M=M(n)$. Понятия степени и сбалансированности графов распространены на неоднородные гиперграфы. Получена предельная многомерная пуассоновская теорема для чисел строго сбалансированных подграфов, имеющих одинаковую степень. Построена пороговая функция свойства, заключающегося в наличии подграфа, изоморфного произвольному конечному гиперграфу. Для случайных графов такие результаты получены в работах Эрдёша, Реньи, Боллобаша, для случайных однородных гиперграфов (то есть при $M=M_m$) – в работах автора.

УДК: 519.2

Статья поступила: 10.06.2005

DOI: 10.4213/dm63


 Англоязычная версия: Discrete Mathematics and Applications, 2006, 16:4, 371–383

Реферативные базы данных:


© МИАН, 2024