Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653977 | European Journal of Combinatorics | 2011 | 16 Pages |
Abstract
We prove that the asymptotic logarithmic density of copies of a graph FF in the graphs of a nowhere dense class CC is integral and we determine the range of its possible values. This leads to a generalization of the trichotomy theorem of Nešetřil and Ossona de Mendez (2011) [18] and to a notion of the degree of freedom of a graph FF in a class CC. This provides yet another formulation of the somewhere dense–nowhere dense classification. We obtain a structural result concerning the asymptotic shape of graphs with given degree of freedom.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jaroslav Nešetřil, Patrice Ossona de Mendez,