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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom