Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun
Multipodal Structure and Phase Transitions in Large 
Constrained Graphs
(1109K, pdf)

ABSTRACT.  We study the asymptotics of large, simple, labeled graphs 
constrained by the densities of k-star subgraphs for two or more 
k, including edges. We prove that for any set of fixed 
constraints, such graphs are "multipodal": asymptotically in the 
number of vertices there is a partition of the vertices into M < 
\infty subsets V1, V2, ..., VM, and a set of well-defined 
probabilities qij of an edge between any vi in Vi and vj in Vj . We 
also prove, in the 2-constraint case where the constraints are on 
edges and 2-stars, the existence of inequivalent optima at 
certain parameter values. Finally, we give evidence based on 
simulation, that throughout the space of the constraint 
parameters of the 2-star model the graphs are not just multipodal 
but bipodal (M=2), easily understood as extensions of the known 
optimizers on the boundary of the parameter space, and that the 
degenerate optima correspond to a non-analyticity in the entropy.