2026-08-07T11:39:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12747 2024-03-06T10:50:44Z ddc:004 open_access

VC Density of Set Systems Definable in Tree-Like Graphs Paszke, Adam Pilipczuk, Michał treewidth cliquewidth definable sets Vapnik-Chervonenkis density 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Paszke and Michał Pilipczuk 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.78 urn:nbn:de:0030-drops-127473 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.78 eng https://creativecommons.org/licenses/by/3.0/legalcode