Bipodal structure in oversaturated random graphs
Bipodal structure in oversaturated random graphs
复制标题
过饱和随机图中的双足结构
DOI：
10.1093/imrn/rnw261
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
L. Sadun
中科院分区：
文献类型：
--
作者：
R. Kenyon;C. Radin;Kui Ren;L. Sadun
研究了任意固定图的边的极限密度和极限子图密度约束下的大型简单图的渐近性。我们证明了，对于除有限多个边密度以外的所有值，如果$H$的密度被约束为略高于相应的ERDőS-Renyi图的密度，则典型的大型图是参数随密度解析变化的两足图。渐近地，参数仅依赖于$H$的度序列。
We study the asymptotics of large simple graphs constrained by the limiting density of edges and the limiting subgraph density of an arbitrary fixed graph $H$. We prove that, for all but finitely many values of the edge density, if the density of $H$ is constrained to be slightly higher than that for the corresponding Erdős-Renyi graph, the typical large graph is bipodal with parameters varying analytically with the densities. Asymptotically, the parameters depend only on the degree sequence of $H$.