RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2018, том 54, выпуск 1, страницы 63–77 (Mi ppi2260)

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

Большие системы

Независимые множества общего вида в случайных сильно разреженных гиперграфах

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

a Московский государственный университет им. М. В. Ломоносова, механико-математический факультет, кафедра теории вероятностей
b Московский физико-технический институт (государственный университет), факультет инноваций и высоких технологий, кафедра дискретной математики
c Московский физико-технический институт (государственный университет), лаборатория продвинутой комбинаторики и сетевых приложений

Аннотация: Изучается асимптотическое поведение числа $j$-независимости случайного $k$-однородного гиперграфа $H(n,k,p)$ в биномиальной модели. Доказано, что в сильно разреженном случае, т.е. когда $p=c\big/\binom{n-1}{k-1}$ при положительном постоянном $0<c\le1/(k-1)$, существует такая константа $\gamma(k,j,c)>0$, что число $j$-независимости $\alpha_j(H(n,k,p))$ подчиняется закону больших чисел
$$ \frac{\alpha_j(H(n,k,p))}{n}\xrightarrow{\mathbf P\,}\gamma(k,j,c)\qquad\text{при}\quad n\to+\infty. $$
Более того, величина $\gamma(k,j,c)$ предъявлена явно как функция от решения некоторого трансцендентного уравнения.

УДК: 621.391.1+519.1

Поступила в редакцию: 01.08.2016
После переработки: 13.04.2017


 Англоязычная версия: Problems of Information Transmission, 2018, 54:1, 56–69

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


© МИАН, 2024