Finitely forcible graphons Export

@article{citeulike:3901441, abstract = {We investigate families of graphs and graphons (graph limits) that are defined 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 Turan, Erdos-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.}, archivePrefix = {arXiv}, author = {Lovasz, Laszlo and Szegedy, Balazs}, citeulike-article-id = {3901441}, citeulike-linkout-0 = {http://arxiv.org/abs/0901.0929}, citeulike-linkout-1 = {http://arxiv.org/pdf/0901.0929}, day = {7}, eprint = {0901.0929}, keywords = {graphtheory, lovasz}, month = {Jan}, posted-at = {2009-01-17 17:25:50}, priority = {2}, title = {Finitely forcible graphons}, url = {http://arxiv.org/abs/0901.0929}, year = {2009} }

TY - JOUR ID - citeulike:3901441 L3 - citeulike-article-id:3901441 N2 - We investigate families of graphs and graphons (graph limits) that are defined 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 Turan, Erdos-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. TI - Finitely forcible graphons KW - graphtheory KW - lovasz AU - Lovasz, Laszlo AU - Szegedy, Balazs PY - 2009/Jan/07/ UR - http://arxiv.org/abs/0901.0929 ER -