Finitely forcible graphons

详细信息    查看全文

• 作者：L. Lová ; sz^a ; ¹ ; B. Szegedy^b
• 关键词：Extremal graph ; Graph limit ; Graphon ; Finitely forcible graphon
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2011
• 出版时间：September 2011
• 年：2011
• 卷：101
• 期：5
• 页码：269-301
• 全文大小：370 K

文摘

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.