- 16-14 Hans Koch
- Vertex order in some large constrained random graphs
Jan 30, 16
(auto. generated pdf),
of related papers
Abstract. In large random graphs with fixed edge density and triangle density,
it has been observed numerically  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.