Typical large graphs with given edge and triangle densities
成果类型：
Article
署名作者：
Neeman, Joe; Radin, Charles; Sadun, Lorenzo
署名单位：
University of Texas System; University of Texas Austin
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-023-01187-8
发表日期：
2023
页码：
1167-1223
关键词：
摘要：
The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdos-Renyi graphs. We prove that the typical graph exhibits sharp singularities as the constraining densities vary between different curves of extreme values, and we determine the precise nature of the singularities. The extension to graphs with fixed densities of edges and k-cycles for odd k > 3 is straightforward and we note the simple changes in the proof.