|
Проблемы передачи информации, 2018, том 54, выпуск 1, страницы 63–77
(Mi ppi2260)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 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)$ предъявлена явно как функция от решения некоторого трансцендентного уравнения.
Поступила в редакцию: 01.08.2016 После переработки: 13.04.2017
Образец цитирования:
А. С. Семенов, Д. А. Шабанов, “Независимые множества общего вида в случайных сильно разреженных гиперграфах”, Пробл. передачи информ., 54:1 (2018), 63–77; Problems Inform. Transmission, 54:1 (2018), 56–69
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2260 https://www.mathnet.ru/rus/ppi/v54/i1/p63
|
Статистика просмотров: |
Страница аннотации: | 320 | PDF полного текста: | 41 | Список литературы: | 35 | Первая страница: | 6 |
|