Moderate deviations of subgraph counts in the Erdős-Rényi random graphs ?(?,?) and ?(?,?)
Moderate deviations of subgraph counts in the Erdős-Rényi random graphs ?(?,?) and ?(?,?)
复制标题
Erdős-Rényi 随机图中的子图计数存在中等偏差 ?(?,?) 和 ?(?,?)
DOI：
10.1090/tran/8117
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
A. Scott
中科院分区：
文献类型：
--
作者：
C. Goldschmidt;Simon Griffiths;A. Scott
本文的主要贡献是给出了Erdens-Rényi随机图中子图计数中偏差率的渐近表达式
G
(
n
,
M
)
G（n，m）
.我们的方法是基于应用弗里德曼不等式的概率偏差的鞅表示的子图计数偏差。此外，我们还证明了不同子图的子图数偏差都是通过两个特定图的偏差，即长为2的路和三角形的偏差来联系的。我们还推出了新的界限，
G
(
n
,
p
)
G（n，p）
模型
The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erdős-Rényi random graph
G
(
n
,
m
)
G(n,m)
. Our approach is based on applying Freedman’s inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related
G
(
n
,
p
)
G(n,p)
model.