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

Дискрет. матем., 2016, том 28, выпуск 3, страницы 126–144 (Mi dm1387)

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

О числах независимости случайных разреженных гиперграфов

А. С. Семенов, Д. А. Шабанов

Московский государственный университет им. М. В. Ломоносова

Аннотация: Изучается асимптотическое поведение числа независимости для биномиальной модели случайного $k$-однородного гиперграфа $H(n,k,p)$ в разреженном случае, когда $p=c/{n-1\choose k-1}$ при положительном постоянном $c>0$. Показано, что существует такая константа $\gamma(c)>0$, что число независимости $\alpha(H(n,k,p))$ подчиняется закону больших чисел
$$ \frac{\alpha(H(n,k,p))}n\stackrel{\mathsf P}\to\gamma(c)\quad\text{при}\quad n\to+\infty. $$
Доказано, что $\gamma(c)>0$ является решением некоторого трансцендентного уравнения при малых значениях $c\leqslant(k-1)^{-1}$.

Ключевые слова: гиперграф, число независимости, разреженные гиперграфы, метод интерполяции, алгоритм Карпа–Сипсера.

УДК: 519.214+519.179.1+519.179.4

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

DOI: 10.4213/dm1387


 Англоязычная версия: Discrete Mathematics and Applications, 2017, 27:4, 231–245

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


© МИАН, 2024