论文标题
vapnik-chervonenkis维度和约翰逊和锤子图的密度
Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs
论文作者
论文摘要
VC维度和VC密度是集合系统组合复杂性的度量。 VC维度首先是在统计学习理论的背景下引入的，与PAC学习中的样本复杂性密切相关。 VC密度是VC维度的改进。在\ emph {依赖性}理论的背景下，在模型理论中也研究了这两个概念。当且仅当公式是依赖公式时，由具有参数的一阶逻辑公式可以定义的设置系统具有有限的VC-dimension。 在本文中，我们研究了约翰逊图和锤子图上的边缘关系$ exy $的VC维数和VC密度。在图形$ g $上，公式$ exy $定义的设置系统是$ g $的顶点集，以及$ g $的所有\ emph {open neightigns}的集合。 我们表明，边缘关系在Johnson Graphs上最多有VC-Dimension $ 4 $，最多在Hamming图上$ 3 $，这些边界是最佳的。 我们此外表明，所有约翰逊图的类别的边缘关系的VC密度为$ 2 $，并且在所有锤子图的类别上，VC密度也为$ 2 $。此外，我们表明，我们在VC尺寸上的界限分别传递到约翰逊图的所有诱导子图的类别，分别分别为所有诱发的锤子图的类别。还可以得出结论，约翰逊图中的\ emph {封闭社区}的设置系统的VC维数和锤子图的界限是有界的。 Johnson图形和锤子图是距离横向图的众所周知的示例。 这些图形类都没有任何地方，也没有（本地）集团宽度。 我们的结果通过提供图形类别的结构驯服的证据来对比。
VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly related to the sample complexity in PAC learning. VC-density is a refinement of VC-dimension. Both notions are also studied in model theory, in the context of \emph{dependent} theories. A set system that is definable by a formula of first-order logic with parameters has finite VC-dimension if and only if the formula is a dependent formula. In this paper we study the VC-dimension and the VC-density of the edge relation $Exy$ on Johnson graphs and on Hamming graphs. On a graph $G$, the set system defined by the formula $Exy$ is the vertex set of $G$ along with the collection of all \emph{open neighbourhoods} of $G$. We show that the edge relation has VC-dimension at most $4$ on Johnson graphs and at most $3$ on Hamming graphs and these bounds are optimal. We furthermore show that the VC-density of the edge relation on the class of all Johnson graphs is $2$, and on the class of all Hamming graphs the VC-density is $2$ as well. Moreover, we show that our bounds on the VC-dimension carry over to the class of all induced subgraphs of Johnson graphs, and to the class of all induced subgraphs of Hamming graphs, respectively. It also follows that the VC-dimension of the set systems of \emph{closed neighbourhoods} in Johnson graphs and Hamming graphs is bounded. Johnson graphs and Hamming graphs are well known examples of distance transitive graphs. Neither of these graph classes is nowhere dense nor is there a bound on their (local) clique-width. Our results contrast this by giving evidence of structural tameness of the graph classes.
