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.