A local central limit theorem for triangles in a random graph

Justin Gilmer; Swastik Kopparty

doi:10.1002/rsa.20604

A local central limit theorem for triangles in a random graph

Justin Gilmer, Swastik Kopparty

SAS - Mathematics

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	732-750
Number of pages	19
Journal	Random Structures and Algorithms
Volume	48
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20604
State	Published - 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

Access to Document

10.1002/rsa.20604

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

@article{b29b15dd395c4f3eba6c93830ddc9015,

title = "A local central limit theorem for triangles in a random graph",

abstract = "In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-R{\'e}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.",

keywords = "Characteristic function, Local limit theorem, Random Graphs, Subgraph counts",

author = "Justin Gilmer and Swastik Kopparty",

note = "Funding Information: Supported by NSF CCF-083727 and CCF-1218711 (J.G.); Sloan Fellowship and NSF CCF-125388 (S.F.) Publisher Copyright: {\textcopyright} 2016 Wiley Periodicals, Inc.",

year = "2016",

month = jul,

day = "1",

doi = "10.1002/rsa.20604",

language = "English (US)",

volume = "48",

pages = "732--750",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - A local central limit theorem for triangles in a random graph

AU - Gilmer, Justin

AU - Kopparty, Swastik

PY - 2016/7/1

Y1 - 2016/7/1

N2 - 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.

AB - 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.

KW - Characteristic function

KW - Local limit theorem

KW - Random Graphs

KW - Subgraph counts

UR - http://www.scopus.com/inward/record.url?scp=84975764616&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975764616&partnerID=8YFLogxK

U2 - 10.1002/rsa.20604

DO - 10.1002/rsa.20604

M3 - Article

AN - SCOPUS:84975764616

VL - 48

SP - 732

EP - 750

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -

A local central limit theorem for triangles in a random graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Cite this