论文标题
在部分立方体，良好的家庭及其双重二元组中
On partial cubes, well-graded families and their duals with some applications in graphs
论文作者
论文摘要
良好的家庭，极端系统和最大系统（从VC理论的意义上讲是VC-dimension上的最后两个诱饵）是三个重要类别的集合系统。本文旨在在这些类别的集合系统中研究二元性的概念，然后使用所获得的结果来研究图。更具体地说，我们关注的是有限设置系统的表征，该系统本身及其双重系统既有良好，极端或最大值。在实现这一目标的道路上，甚至可能具有独立的兴趣，我们研究了具有系统大小的属性良好家庭的结构，即系统的大小不比其必需领域的大小大，即，该域的元素集合被系统破碎为单个元素子集。作为论文的另一个目标，我们使用上述结果来表征其套件，其设置的开放式或封闭社区，集团或独立集的系统是良好的，极端或最大的。我们阐明了此类图与著名的半雕像的关系。通过论文，我们经常将调查与系统的VC维度联系起来。另外，我们使用与设置系统相关的一包图作为重要的技术工具。
Well-graded families, extremal systems and maximum systems (the last two in the sense of VC-theory and Sauer-Shelah lemma on VC-dimension) are three important classes of set systems. This paper aims to study the notion of duality in the context of these classes of set systems and then use the obtained results for studying graphs. More specifically, we are concerned with the characterization of the finite set systems which themselves and their dual systems are both well-graded, extremal or maximum. On the way to this goal, and maybe also of independent interest, we study the structure of the well-graded families with the property that the size of the system is not much bigger than the size of its essential domain, that is, the set of elements of the domain which are shattered by the system as single element subsets. As another target of the paper, we use the above results to characterize graphs whose set systems of open or closed neighbourhoods, cliques or independent sets are well-graded, extremal or maximum. We clarify the relation of such graphs to the celebrated half-graphs. Through the paper, we frequently relate our investigations to the VC-dimension of the systems. Also we use one-inclusion graphs associated to set systems as an important technical tool.
