## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1-14 |

Number of pages | 14 |

Journal | Random Structures and Algorithms |

Volume | 22 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2003 |

Externally published | Yes |