RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2017 Volume 53, Issue 4, Pages 3–15 (Mi ppi2249)

This article is cited in 9 papers

Coding Theory

Independence numbers of random subgraphs of some distance graph

N. M. Derevyanko, S. G. Kiselev

Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: The distance graph $G(n,2,1)$ is a graph where vertices are identified with twoelement subsets of $\{1,2,\dots,n\}$, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph $G_p(n,2,1)$ in the Erdős–Rényi model is obtained by selecting each edge of $G(n,2,1)$ with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph $G_{1/2}(n,2,1)$.

UDC: 621.391.1+519.1

Received: 25.02.2017
Revised: 04.05.2017


 English version:
Problems of Information Transmission, 2017, 53:4, 307–318

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024