 1614 Hans Koch
 Vertex order in some large constrained random graphs
(285K, pdf)
Jan 30, 16

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

Abstract. In large random graphs with fixed edge density and triangle density,
it has been observed numerically [9] that a typical graph is finitepodal,
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.
 Files:
1614.src(
1614.comments ,
1614.keywords ,
ordering3.pdf.mm )