Sub-Gaussian tails for the number of triangles in G(n,p)

2009/09/13 by Guy Wolfovitz, Wolfovitz, Guy
Mathematics · #Analytic Number Theory Research #Limits and Structures in Graph Theory #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.0909.2403

Abstract

Let X be the random variable that counts the number of triangles in the random graph G(n,p). We show that for some absolute constant c, the probability that X deviates from its expectation by at least λ\var(X)^1/2 is at most e^-cλ2, provided that n^-1(ln n)¹⁰ ≤ p ≤ n^-1/2(ln n)^-10, λ= ω(ln n) and λ≤ min\(np)^1/2, n^-3/4p^-3/2, n^1/6\.

Related

• Lower tails for triangles inside the critical window
• Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph G(n,m): The Lower Tail
• The missing log in large deviations for triangle counts
• Triangles and subgraph probabilities in random regular graphs
• Upper tail behavior of the number of triangles in random graphs with constant average degree