RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2021 Volume 499, Pages 17–19 (Mi danma184)

This article is cited in 1 paper

MATHEMATICS

Asymptotics of the independence number of a random subgraph of the graph $G(n,r,<s)$

V. S. Karasa, P. A. Ogarokb, A. M. Raigorodskiiabcd

a Lomonosov Moscow State University, Moscow, Russia
b Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, Russia
c Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia
d Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude, Buryat Republic, Russia

Abstract: In this paper, we deal with a probabilistic version of a classical problem in extremal combinatorics. An extension to the case of nonconstant parameters and to the case of different probabilities of edges is established for a stability theorem asserting that the independence number of a random subgraph of a graph $G(n,r,<s)$ does not change asymptotically, provided that the initial edges are deleted independently.

Keywords: asymptotics, independence number, random subgraphs, graph $G(n,r,<s)$.

UDC: 519.1

Presented: V. V. Kozlov
Received: 26.03.2020
Revised: 15.05.2021
Accepted: 16.05.2021

DOI: 10.31857/S268695432104007X


 English version:
Doklady Mathematics, 2021, 104:1, 173–174

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024