The Asymptotics of Large Constrained Graphs

Abstract

We show, through local estimates and simulation, that if one constrains simple graphs by their densities $\epsilon$ of edges and $\tau$ 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 $V_1$ and $V_2$ of fixed relative size $c$ and $1-c$, and there are well-defined probabilities of edges, $g_{jk}$, between $v_j\in V_j$, and $v_k\in V_k$. Furthermore the four parameters $c,g_{11},g_{22}$ and $g_{12}$ are smooth functions of $(\epsilon ,\tau )$ except at two smooth `phase transition' curves.

References in corpus (1)

• An Introduction to the Thermodynamic and Macrostate Levels of Nonequivalent Ensembles

Cited by in corpus (18)

• Clustering implies geometry in networks
• The phases of large networks with edge and triangle constraints
• On the lower tail variational problem for random graphs
• Asymptotic structure and singularities in constrained directed graphs
• On the asymptotics of constrained exponential random graphs
• Reciprocity in directed networks
• Asymptotics for Sparse Exponential Random Graph Models
• The birth of geometry in exponential random graphs
• Elusive extremal graphs
• Asymptotic Structure of Constrained Exponential Random Graph Models
• Large deviations and exact asymptotics for constrained exponential random graphs
• Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
• Simple evolving random graphs
• Regular graphs with linearly many triangles
• Surface effects in dense random graphs with sharp edge constraint
• Nucleation during phase transitions in random networks
• Ground States for Exponential Random Graphs
• Lattice Gas Models with Long Range Interactions