Finitely forcible graphons
Finitely forcible graphons
复制标题
有限强制图子
DOI：
10.1016/j.jctb.2011.03.005
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Balázs Szegedy
中科院分区：
文献类型：
--
作者：
L. Lovász;Balázs Szegedy
我们研究由有限数量的规定子图密度决定的图和图族（图极限）。我们主要关注的是当家族只包含一个元素时的情况，即一个独特的结构被有限多个子图密度所强迫。推广Turán， Erdős-Simonovits和Chung-Graham-Wilson的结果，构造了许多有限强制图子。其中大多数可分为两类：一类具有代数结构，另一类具有迭代（类似分形）结构。我们还给出了强制的一些必要条件，这意味着有限强制的图形是“罕见的”，并展示了简单而显式的非强制图形。
We investigate families of graphs and graphons (graph limits) that are determined by a finite number of prescribed subgraph densities. Our main focus is the case when the family contains only one element, i.e., a unique structure is forced by finitely many subgraph densities. Generalizing results of Turán, Erdős–Simonovits and Chung–Graham–Wilson, we construct numerous finitely forcible graphons. Most of these fall into two categories: one type has an algebraic structure and the other type has an iterated (fractal-like) structure. We also give some necessary conditions for forcibility, which imply that finitely forcible graphons are “rare”, and exhibit simple and explicit non-forcible graphons.