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

Probl. Peredachi Inf., 2020 Volume 56, Issue 4, Pages 50–63 (Mi ppi2328)

This article is cited in 4 papers

Large Systems

On stability of the independence number of a certain distance graph

P. A. Ogaroka, A. M. Raigorodskiibcdeaf

a Moscow Institute of Physics and Technology (State University), Moscow, Russia
b Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology (State University), Moscow, Russia
c Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude, Russia
d Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia
e Department of Mathematical Statistics and Random Processes, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
f Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: We study the asymptotic behavior of the independence number of a random subgraph of a certain $(r,s)$-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.

Keywords: random graph, distance graph, independence number.

UDC: 621.391 : 519.176

Received: 09.03.2020
Revised: 29.10.2020
Accepted: 29.10.2020

DOI: 10.31857/S0555292320040051


 English version:
Problems of Information Transmission, 2020, 56:4, 345–357

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025