|
|
Problemy Peredachi Informatsii, 2018, Volume 54, Issue 2, Pages 73–85
(Mi ppi2267)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Large Systems
Clique numbers of random subgraphs of some distance graphs
A. S. Gusev Department of Mathematical Statistics and Random Processes,
Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
Abstract:
We consider a class of graphs $G(n,r,s)=(V(n,r),E(n,r,s))$, defined as follows:
$$
\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}
$$
where $(x,y)$ is the Euclidean scalar product. We study random subgraphs $\mathcal G(G(n,r,s), p)$ with edges independently chosen from the set $E(n,r,s)$ with probability $p$ each. We find nontrivial lower and upper bounds on the clique number of such graphs.
Received: 18.12.2017 Revised: 23.03.2018
Citation:
A. S. Gusev, “Clique numbers of random subgraphs of some distance graphs”, Probl. Peredachi Inf., 54:2 (2018), 73–85; Problems Inform. Transmission, 54:2 (2018), 165–175
Linking options:
https://www.mathnet.ru/eng/ppi2267 https://www.mathnet.ru/eng/ppi/v54/i2/p73
|
|