Paszke, Adam ;
Pilipczuk, Michał
VC Density of Set Systems Definable in TreeLike Graphs
Abstract
We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of VapnikChervonenkis 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.
BibTeX  Entry
@InProceedings{paszke_et_al:LIPIcs:2020:12747,
author = {Adam Paszke and Micha{\l} Pilipczuk},
title = {{VC Density of Set Systems Definable in TreeLike Graphs}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {78:178:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12747},
URN = {urn:nbn:de:0030drops127473},
doi = {10.4230/LIPIcs.MFCS.2020.78},
annote = {Keywords: treewidth, cliquewidth, definable sets, VapnikChervonenkis density}
}
18.08.2020
Keywords: 

treewidth, cliquewidth, definable sets, VapnikChervonenkis density 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 