Hans Koch Vertex order in some large constrained random graphs (285K, pdf) ABSTRACT. In large random graphs with fixed edge density and triangle density, it has been observed numerically [9] that a typical graph is finite-podal, meaning that it has only finitely many distinct "types" of vertices. In particular, it seems to be a fundamental property of such graphs to have large groups of vertices that are all of the same type. In this paper we describe a mechanism that produces such behavior. By known results on graph limits, the problem reduces to the study of a constrained maximization problem for symmetric measurable functions (graphons) on the unit square. As a first step we prove that, for a wide range of parameter values, the constrained maximizers are in some sense monotone.