论文标题
固定系统的VC密度可在类似树状的图中固定
VC density of set systems defnable in tree-like graphs
论文作者
论文摘要
我们研究使用具有不同表达能力的逻辑变体在图中定义的设置系统。我们的重点是vapnik-chervonenkis密度的概念：多项式界限的最小程度是这种设置系统的限制。一方面，我们证明，如果$φ（\ bar x，\ bar y）$是固定的cmso $ _1 $公式，$ \ cal c $是具有均匀界限的一类图表，那么由$ \ cal C $中的$ \ cal c $中的$ \ c $中的$ \ c $ the One the the The Indection the the Set Systems的设置系统最多可预期$ \ bar y y y y y SILLE SMILLE | thicle | thicy | east，是一个小的| estest，是一个小| eest，是一个小的| eest，是一个小| eest，是一个小| eest，是一个小| eest，是一个小的| thict。当$φ（\ bar x，\ bar y）$是cmso $ _2 $公式，而$ \ cal c $是一类图形，我们还显示了一个类似的情况。 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 CMSO$_1$ (respectively, CMSO$_2$) formulas in graphs from $\cal C$ may have unbounded VC dimension, hence also unbounded VC 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 $φ(\bar x,\bar y)$ is a fixed CMSO$_1$ 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 $|\bar y|$, which is the smallest bound that one could expect. We also show an analogous statement for the case when $φ(\bar x,\bar y)$ is a CMSO$_2$ 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 CMSO$_1$ (respectively, CMSO$_2$) formulas in graphs from $\cal C$ may have unbounded VC dimension, hence also unbounded VC density.
