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

被引：0

作者：

Alvarado, Jose D. ^{[1
]}

de Oliveira, Leonardo Goncalves ^{[2
]}

Griffiths, Simon ^{[2
]}

机构：

[1] Univ Ljubljana, Fac Math & Phys, Jadranska ul 19, Ljubljana 1000, Slovenia

[2] Pontificia Univ Catolica Rio de Janeiro, Dept Matemat, Rua Marques de Sao Vicente 225 Gavea, BR-22451900 Rio de Janeiro, Brazil

来源：

PROBABILITY THEORY AND RELATED FIELDS | 2025年 / 191卷 / 3-4期

基金：

巴西圣保罗研究基金会;

关键词：

SUBGRAPH COUNTS; ASYMPTOTIC ENUMERATION; DEGREE SEQUENCE; U-STATISTICS; UPPER TAILS; INEQUALITIES; NUMBER; BOUNDS;

D O I：

10.1007/s00440-025-01359-8

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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

引用

页码：779 / 851

页数：73

共 41 条

[11] The large deviation principle for the Erdos-Renyi random graph [J].

Chatterjee, Sourav ;

Varadhan, S. R. S. .

EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (07) :1000-1017

[12] Large deviations of subgraph counts for sparse Erdos-Renyi graphs [J].

Cook, Nicholas ;

Dembo, Amir .

ADVANCES IN MATHEMATICS, 2020, 373

[13] Upper tails for triangles [J].

DeMarco, B. ;

Kahn, J. .

RANDOM STRUCTURES & ALGORITHMS, 2012, 40 (04) :452-459

[14] Moderate Deviations via Cumulants [J].

Doering, Hanna ;

Eichelsbacher, Peter .

JOURNAL OF THEORETICAL PROBABILITY, 2013, 26 (02) :360-385

[15] Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices [J].

Doering, Hanna ;

Eichelsbacher, Peter .

ELECTRONIC JOURNAL OF PROBABILITY, 2009, 14 :2636-2656

[16] Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations [J].

Eldan, Ronen .

GEOMETRIC AND FUNCTIONAL ANALYSIS, 2018, 28 (06) :1548-1596

[17]

Fray V., 2016, CONVERGENCE NORMALIT, DOI [10.1007/978-3-319-46822-8, DOI 10.1007/978-3-319-46822-8]

[18] TAIL PROBABILITIES FOR MARTINGALES [J].

FREEDMAN, DA .

ANNALS OF PROBABILITY, 1975, 3 (01) :100-118

[19] Upper Tail Behavior of the Number of Triangles in Random Graphs with Constant Average Degree [J].

Ganguly, Shirshendu ;

Hiesmayr, Ella ;

Nam, Kyeongsik .

COMBINATORICA, 2024, 44 (04) :699-740

[20] MODERATE DEVIATIONS OF SUBGRAPH COUNTS IN THE ERDOS-RENYI RANDOM GRAPHS G(n, m) AND G(n, p) [J].

Goldschmidt, Christina ;

Griffiths, Simon ;

Scott, Alex .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2020, 373 (08) :5517-5585

← 1 2 3 4 5 →