Upper tails for triangles

B. Demarco, J. Kahn

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


With ξ the number of triangles in the usual (Erdo{double acute}s-Rényi) random graph G(m,p), p > 1/m and η > 0, we show (for some C η > 0) This is tight up to the value of C η.

Original languageEnglish (US)
Pages (from-to)452-459
Number of pages8
JournalRandom Structures and Algorithms
Issue number4
StatePublished - Jul 2012

All Science Journal Classification (ASJC) codes

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


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


Dive into the research topics of 'Upper tails for triangles'. Together they form a unique fingerprint.

Cite this