pith. sign in

arxiv: 0901.0929 · v2 · pith:ZAGHF6QQnew · submitted 2009-01-07 · 🧮 math.CO

Finitely forcible graphons

classification 🧮 math.CO
keywords graphonsfinitelyforciblestructuredensitiessubgraphtypealgebraic
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.