The asymptotics of large constrained graphs
The asymptotics of large constrained graphs
复制标题
大约束图的渐近
DOI：
10.1088/1751-8113/47/17/175001
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
L. Sadun
中科院分区：
文献类型：
--
作者：
C. Radin;Kui Ren;L. Sadun
我们通过局部估计和模拟表明，如果用边的密度ϵ和三角形的τ来约束简单图，那么对于这些密度的95%以上的可能范围，渐近地(以顶点数)存在一个定义良好的典型图，并且它具有非常简单的结构：顶点被分解成固定相对大小c和1−c的两个子集V1和V2，并且在VJ∈VJ和VK∈VK之间存在明确的边概率Gjk。此外，除两条光滑的“相变”曲线外，四个参数c、G11、G22和G12都是(ϵ，τ)的光滑函数。
We show, through local estimates and simulation, that if one constrains simple graphs by their densities ϵ of edges and τ of triangles, then asymptotically (in the number of vertices) for over 95% of the possible range of those densities there is a well-defined typical graph, and it has a very simple structure: the vertices are decomposed into two subsets V1 and V2 of fixed relative size c and 1 − c, and there are well-defined probabilities of edges, gjk, between vj ∈ Vj, and vk ∈ Vk. Furthermore the four parameters c, g11, g22 and g12 are smooth functions of (ϵ, τ) except at two smooth ‘phase transition’ curves.