DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2020.78

VC Density of Set Systems Definable in Tree-Like Graphs

Authors: Adam Paszke and Michał Pilipczuk

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

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 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.

Cite as

Adam Paszke and Michał Pilipczuk. VC Density of Set Systems Definable in Tree-Like Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 78:1-78:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{paszke_et_al:LIPIcs.MFCS.2020.78,
  author =	{Paszke, Adam and Pilipczuk, Micha{\l}},
  title =	{{VC Density of Set Systems Definable in Tree-Like Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{78:1--78:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.78},
  URN =		{urn:nbn:de:0030-drops-127473},
  doi =		{10.4230/LIPIcs.MFCS.2020.78},
  annote =	{Keywords: treewidth, cliquewidth, definable sets, Vapnik-Chervonenkis density}
}

Search Results

Documents authored by Paszke, Adam

VC Density of Set Systems Definable in Tree-Like Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message