Эта публикация цитируется в
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