The asymptotics of large constrained graphs

Abstract

We show, through local estimates and simulation, that if one constrains\nsimple graphs by their densities $\\varepsilon$ of edges and $\\tau$ of\ntriangles, then asymptotically (in the number of vertices) for over $95\\%$ of\nthe possible range of those densities there is a well-defined typical graph,\nand it has a very simple structure: the vertices are decomposed into two\nsubsets $V_1$ and $V_2$ of fixed relative size $c$ and $1-c$, and there are\nwell-defined probabilities of edges, $g_{jk}$, between $v_j\\in V_j$, and\n$v_k\\in V_k$. Furthermore the four parameters $c, g_{11}, g_{22}$ and $g_{12}$\nare smooth functions of $(\\varepsilon,\\tau)$ except at two smooth `phase\ntransition' curves.\n