Asymptotics of the Independence Number of a Random Subgraph of the GraphG(n, r, < s)

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 subgr...

Full description

Saved in:
Bibliographic Details
Published in:Doklady. Mathematics 2021, Vol.104 (1), p.173-174
Main Authors: Karas, V. S., Ogarok, P. A., Raigorodskii, A. M.
Format: Article
Language:English
Subjects:
Asymptotic properties
Combinatorial analysis
Graph theory
Mathematics
Mathematics and Statistics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 does not change asymptotically, provided that the initial edges are deleted independently.
ISSN:1064-5624
1531-8362
DOI:10.1134/S1064562421040074