VC density of set systems defnable in tree-like graphs

Abstract

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 $\ddot{I}†(\bar{x},\bar{y})$ is a fixed CMSO${}_1$ formula and $\mathcal{C}$ is a class of graphs with uniformly bounded cliquewidth, then the set systems defined by $\ddot{I}†$ in graphs from $\mathcal{C}$ have VC density at most $|\bar{y}|$, which is the smallest bound that one could expect. We also show an analogous statement for the case when $\ddot{I}†(\bar{x},\bar{y})$ is a CMSO${}_2$ formula and $\mathcal{C}$ is a class of graphs with uniformly bounded treewidth. We complement these results by showing that if $\mathcal{C}$ has unbounded cliquewidth (respectively, treewidth), then, under some mild technical assumptions on $\mathcal{C}$, the set systems definable by CMSO${}_1$ (respectively, CMSO${}_2$) formulas in graphs from $\mathcal{C}$ may have unbounded VC dimension, hence also unbounded VC density.

14 pages, 1 figure