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

Пробл. передачи информ., 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$. Найдены нетривиальные нижние и верхние оценки кликового числа таких графов.

УДК: 621.391.1+519.1

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


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

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


© МИАН, 2024