Multipodal Structure and Phase Transitions in Large Constrained Graphs

Abstract

We study the asymptotics of large, simple, labeled graphs constrained by the densities of edges and of $k$-star subgraphs, $k\ge 2$ fixed. We prove that under such constraints graphs are "multipodal": asymptotically in the number of vertices there is a partition of the vertices into $M<\infty$ subsets $V_1,V_2,\dots ,V_M$, and a set of well-defined probabilities $g_{ij}$ of an edge between any $v_i\in V_i$ and $v_j\in V_j$. For $2\le k\le 30$ we determine the phase space: the combinations of edge and $k$-star densities achievable asymptotically. For these models there are special points on the boundary of the phase space with nonunique asymptotic (graphon) structure; for the 2-star model we prove that the nonuniqueness extends to entropy maximizers in the interior of the phase space.