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.