Optimal graphons in the edge-2star model

Abstract

In the edge-2star model with hard constraints, we prove the existence of an open set of constraint parameters, bisected by a line segment on which there are nonunique entropy-optimal graphons related by a symmetry. At each point in the open set but off the line segment, there is a unique entropy-optimizer, bipodal and varying analytically with the constraints. We also show that throughout another open set, containing a different portion of the same line of symmetry, there is instead a unique optimal graphon, varying analytically with the parameters. We explore the extent of these open sets, determining the point at which a symmetric graphon ceases to be a local maximizer of the entropy. Finally, we prove some foundational theorems in a general setting, relating optimal graphons to the Boltzmann entropy and the generic structure of large constrained random graphs.