Vertex Order in Some Large Constrained Random Graphs
Vertex Order in Some Large Constrained Random Graphs
复制标题
一些大型约束随机图中的顶点顺序
DOI：
10.1137/16m1061898
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. Koch
中科院分区：
文献类型：
--
作者：
H. Koch
在具有固定边密度和三角形密度的大型随机图中，已在数值上观察到了这一点[C。Radin，K. Ren和L. Sadun，J. Phys. A，47（2014）]，一个典型的图是有限的podal，这意味着它只有1000个不同的“类型”的顶点。特别是，它似乎是这样的图的一个基本性质，有大组的顶点都是相同的类型。在本文中，我们描述了一种机制，产生这样的行为。根据图极限的已知结果，该问题归结为单位正方形上对称可测函数（图子）的约束最大化问题的研究。作为第一步，我们证明，在一个假设下，适用于广泛的参数值，约束最大化在某种意义上是单调的。
In large random graphs with fixed edge density and triangle density, it has been observed numerically [C. Radin, K. Ren, and L. Sadun, J. Phys. A, 47 (2014)] 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, under an assumption that holds for a wide range of parameter values, the constrained maximizers are in some sense monotone.