Premium
On the probability of independent sets in random graphs
Author(s) -
Krivelevich Michael,
Sudakov Benny,
Vu Van H.,
Wormald Nicholas C.
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10063
Subject(s) - mathematics , combinatorics , logarithm , discrete mathematics , random graph , exponent , random variable , independence (probability theory) , constant (computer programming) , exponential function , random regular graph , probability measure , product (mathematics) , expected value , graph , statistics , pathwidth , line graph , computer science , mathematical analysis , linguistics , philosophy , geometry , programming language
Let k be the asymptotic value of the independence number of the random graph G(n, p). We prove that if the edge probability p(n) satisfies p(n) ≫ n −2/5 ln 6/5 n then the probability that G(n, p) does not contain an independent set of size k − c, for some absolute constant c > 0, is at most exp {−cn 2 /(k 4 p)}. We also show that the obtained exponent is tight up to logarithmic factors, and apply our result to obtain new bounds on the choice number of random graphs. We also discuss a general setting where our approach can be applied to provide an exponential bound on the probability of certain events in product probability spaces. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 1–14, 2003
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom