Premium
The missing log in large deviations for triangle counts
Author(s) -
Chatterjee Sourav
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20381
Subject(s) - logarithm , exponent , struct , mathematics , combinatorics , large deviations theory , random graph , graph , statistics , computer science , mathematical analysis , philosophy , linguistics , programming language
This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erdős‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012