摘要：We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of Vapnik-Chervonenkis density: the smallest possible degree of a polynomial bounding the cardinalities of restrictions of such set systems. On one hand, we prove that if phi(x,y) is a fixed CMSO_1 formula and C is a class of graphs with uniformly bounded cliquewidth, then the set systems defined by phi in graphs from C have VC density at most y , which is the smallest bound that one could expect. We also show an analogous statement for the case when phi(x,y) is a CMSO_2 formula and C is a class of graphs with uniformly bounded treewidth. We complement these results by showing that if C has unbounded cliquewidth (respectively, treewidth), then, under some mild technical assumptions on C, the set systems definable by CMSO_1 (respectively, CMSO_2) formulas in graphs from C may have unbounded VC dimension, hence also unbounded VC density.
关键词：treewidth; cliquewidth; definable sets; Vapnik-Chervonenkis density
