Эта публикация цитируется в
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