A local central limit theorem for triangles in a random graph

Justin Gilmer, Swastik Kopparty

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Rényi random graph G(n, p), where p∈(0,1) is a fixed constant. Our proof is based on bounding the characteristic function ψ(t) of the number of triangles, and uses several different conditioning arguments for handling different ranges of t.

Original languageEnglish (US)
Pages (from-to)732-750
Number of pages19
JournalRandom Structures and Algorithms
Volume48
Issue number4
DOIs
StatePublished - Jul 1 2016

All Science Journal Classification (ASJC) codes

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

Keywords

  • Characteristic function
  • Local limit theorem
  • Random Graphs
  • Subgraph counts

Fingerprint Dive into the research topics of 'A local central limit theorem for triangles in a random graph'. Together they form a unique fingerprint.

Cite this