Title: Vertex order in some large constrained random graphs
Author: Hans Koch
Abstract:   We consider a constrained maximization problem for symmetric measurable functions on [0,1]2 that arises in the study of large random graphs with constrained edge density and triangle density. Numerical results in [8] suggest that every constrained maximizer g is finite-podal, meaning that it has only finitely many distinct “vertex types” g(.,y) as y ranges in [0,1]. Here we prove a weaker property: excluding strictly negative correlations between edges and two-stars, the function y→g(.,y) is constant on some set of positive measure. As a first step, we show that the vertex types g(.,y) of g admit a natural order.
Paper: preprint here