Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)

• 成果类型: Article
• 署名作者: Alvarado, Jose D.; de Oliveira, Leonardo Goncalves; Griffiths, Simon
• 署名单位: University of Ljubljana
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-025-01359-8
• 发表日期: 2025
• 页码: 779-851
• 关键词: subgraph counts; asymptotic enumeration; degree sequence; U-statistics; upper tails; inequalities; number; bounds

摘要

We consider the question of determining the probability of triangle count deviations in the Erdos-Renyi random graphs G (n,m) and G (n,p)with densities larger than n(-1/2)(log n)(1/2). In particular, we determine the log probability log P(N-Delta(G) > (1+delta)p(3)n(3))up to a constant factor across essentially the entire range of possible deviations, in both the G (n,m) and G (n,p) model. For the G(n,p) model, we also prove a stronger result, up to a(1+o(1)) factor, in the non-localised regime. We also obtain some results for the lower tail and for counts of cherries (paths of length 2).