|
Эта публикация цитируется в 2 научных статьях (всего в 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}$.
Ключевые слова:
гиперграф, число независимости, разреженные гиперграфы, метод интерполяции, алгоритм Карпа–Сипсера.
Статья поступила: 19.06.2016
Образец цитирования:
А. С. Семенов, Д. А. Шабанов, “О числах независимости случайных разреженных гиперграфов”, Дискрет. матем., 28:3 (2016), 126–144; Discrete Math. Appl., 27:4 (2017), 231–245
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1387https://doi.org/10.4213/dm1387 https://www.mathnet.ru/rus/dm/v28/i3/p126
|
|