2020/03/31 by Adam Paszke, Michał Pilipczuk, Paszke, Adam +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.14177
openalex publication_date 2020/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 φ( x, y) is a fixed CMSO1 formula and \cal C is a class of graphs with uniformly bounded cliquewidth, then the set systems defined by φ in graphs from \cal 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 φ( x, y) is a CMSO2 formula and \cal C is a class of graphs with uniformly bounded treewidth. We complement these results by showing that if \cal C has unbounded cliquewidth (respectively, treewidth), then, under some mild technical assumptions on \cal C, the set systems definable by CMSO1 (respectively, CMSO2) formulas in graphs from \cal C may have unbounded VC dimension, hence also unbounded VC density.