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.