Moderate deviations in cycle count
Moderate deviations in cycle count
复制标题
周期计数存在适度偏差
DOI：
10.1002/rsa.21147
复制
发表时间：
2023
影响因子：
1
通讯作者：
Sadun, Lorenzo
中科院分区：
文献类型：
--
作者：
Neeman, Joe;Radin, Charles;Sadun, Lorenzo
证明了随机图中奇圈数的下尾的中偏差界。我们证明了三角形密度减少的概率为，无论何时。这些补充的结果Goldschloss，格里菲斯，和斯科特，谁表明，为，概率是。也就是说，阶数小于的偏差表现为小偏差，阶数大于的偏差表现为大偏差。我们推测，两个政权之间发生急剧变化的偏差的大小，我们与一个单一的大负特征值的邻接矩阵成为负责几乎所有的周期赤字。我们给出了类似的结果的周期密度，所有奇数。我们的结果可以解释为有限尺寸效应在约束随机图的相变。
We prove moderate deviations bounds for the lower tail of the number of odd cycles in arandom graph. We show that the probability of decreasing triangle density by, iswhenever. These complement results of Goldschmidt, Griffiths, and Scott, who showed that for, the probability is. That is, deviations of order smaller thanbehave like small deviations, and deviations of order larger thanbehave like large deviations. We conjecture that a sharp change between the two regimes occurs for deviations of size, which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. We give analogous results for the‐cycle density, for all odd. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.
登录
查看更多内容
DOI：
10.1214/19-aop1398
发表时间：
2018-10
期刊：
The Annals of Probability
影响因子：
--
作者：
A. Guionnet;Jonathan Husson
通讯作者：
A. Guionnet;Jonathan Husson
Erdős-Rényi 随机图中的子图计数存在中等偏差 ?(?,?) 和 ?(?,?)
影响因子：
1.3
作者：
C. Goldschmidt;Simon Griffiths;A. Scott
通讯作者：
A. Scott
一些大型约束随机图中的顶点顺序
DOI：
10.1137/16m1061898
发表时间：
2016
期刊：
SIAM J. Math. Anal.
影响因子：
--
作者：
H. Koch
通讯作者：
H. Koch
影响因子：
2.3
作者：
S. Boucheron;G. Lugosi;P. Massart
通讯作者：
P. Massart
DOI：
10.1137/18m1230852
发表时间：
2018
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Bhattacharya;S. Ganguly
通讯作者：
S. Ganguly