16-14 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 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.

Files: 16-14.src( 16-14.comments , 16-14.keywords , ordering3.pdf.mm )