Article ID Journal Published Year Pages File Type
4653977 European Journal of Combinatorics 2011 16 Pages PDF
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
, ,