The Asymptotics of Large Constrained Graphs

We show, through local estimates and simulation, that if one constrains simple graphs by their densities varepsilon 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 (varepsilon,τ) except at two smooth `phase transition' curves.