|
Проблемы передачи информации, 2018, том 54, выпуск 2, страницы 73–85
(Mi ppi2267)
|
|
|
|
Большие системы
Кликовые числа случайных подграфов некоторых дистанционных графов
А. С. Гусев Московский государственный университет им. М. В. Ломоносова, механико-математический факультет, кафедра математической статистики и случайных процессов
Аннотация:
Рассматривается класс графов $G(n,r,s)=(V(n,r),E(n,r,s))$, определенных следующим образом:
$$
\begin{aligned}
& V(n,r)=\{\boldsymbol x=(x_1, x_2,\dots,x_n)\colon x_i\in\{0,1\},\ x_1+x_2+\dots+x_n=r\},\\
& E(n,r,s)=\{\{\boldsymbol x,\boldsymbol y\}\colon(\boldsymbol x,\boldsymbol y)=s\},
\end{aligned}
$$
где $(x,y)$ – евклидово скалярное произведение. Изучаются случайные подграфы $\mathcal G(G(n,r,s), p)$, ребра в которых выбираются независимо из множества $E(n,r,s)$, каждое с вероятностью $p$. Найдены нетривиальные нижние и верхние оценки кликового числа таких графов.
Поступила в редакцию: 18.12.2017 После переработки: 23.03.2018
Образец цитирования:
А. С. Гусев, “Кликовые числа случайных подграфов некоторых дистанционных графов”, Пробл. передачи информ., 54:2 (2018), 73–85; Problems Inform. Transmission, 54:2 (2018), 165–175
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2267 https://www.mathnet.ru/rus/ppi/v54/i2/p73
|
Статистика просмотров: |
Страница аннотации: | 204 | PDF полного текста: | 40 | Список литературы: | 35 | Первая страница: | 7 |
|