14-38 Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun

Multipodal Structure and Phase Transitions in Large Constrained Graphs (1109K, pdf) May 14, 14

Abstract , Paper (src), View paper (auto. generated pdf), Index of related papers

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.

Files: 14-38.src( 14-38.comments , 14-38.keywords , text31c.pdf.mm )