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

Пробл. передачи информ., 2018, том 54, выпуск 2, страницы 73–85 (Mi ppi2267)

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

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

Кликовые числа случайных подграфов некоторых дистанционных графов

А. С. Гусев

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет, кафедра математической статистики и случайных процессов

Аннотация: Рассматривается класс графов $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

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


© МИАН, 2025