Tight upper tail bounds for cliques

B. Demarco, J. Kahn

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

With ξ k =ξ kn,p the number of copies of K k in the usual (Erdo{double acute}s-Rényi) random graph G(n,p), p ≥ n -2/(k-1) and η > 0, we show when k > 1 Pr(ξ k(1 + η)Eξ k )< exp [-Ω η,k min {n 2p k-1log(1/p), n kp (2k). This is tight up to the value of the constant in the exponent.

Original languageEnglish (US)
Pages (from-to)469-487
Number of pages19
JournalRandom Structures and Algorithms
Volume41
Issue number4
DOIs
StatePublished - Dec 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Large deviations
  • Random graphs
  • Subgraph counts
  • Upper tails

Fingerprint Dive into the research topics of 'Tight upper tail bounds for cliques'. Together they form a unique fingerprint.

Cite this