Charles Radin, Kui Ren, Lorenzo Sadun
The asymptotics of large constrained graphs
(3371K, pdf)
ABSTRACT. We show, through local estimates and simulation, that if one constrains simple
graphs by their densities e of edges and t of triangles, then asymptotically (in the
number of vertices) for over 95% of the possible range of those densities there is a well-
defi ned typical graph, and it has a very simple structure: the vertices are decomposed
into two subsets V1 and V2 of fixed relative sizes c and 1 - c, and there are well-
defi ned probabilities of edges, gjk, between vj in Vj , and vk in Vk. Furthermore the
four parameters c, g11, g22 and g12 are smooth functions of ( e,t) except at two smooth phase transition curves.