论文标题
将超图的微量功能与应用程序界定
Bounding the trace function of a hypergraph with applications
论文作者
论文摘要
派生了HyperGraph $ H $的痕量功能的上限，并证明了其应用程序。例如，$ H $或$ VC（h）$的VC尺寸的新上限是随后的，因此可以在多项式时间内计算$ vc（h）$，前提是$ h $具有限制性变性。这是以前不知道的。特别是，当$ h $是由图的封闭社区引起的超图时，这种方法渐近地改善了计算$ vc（h）$的先前结果的时间复杂性。另一个结果是在$ h $的{\ IT区分横向数}上的一般下限，这引起了图形主导理论的应用。为了有效地应用此处开发的方法，需要良好的退化估计以及其变化或减少的堕落性。
An upper bound on the trace function of a hypergraph $H$ is derived and its applications are demonstrated. For instance, a new upper bound for the VC dimension of $H$, or $vc(H)$, follows as a consequence and can be used to compute $vc(H)$ in polynomial time provided that $H$ has bounded degeneracy. This was not previously known. Particularly, when $H$ is a hypergraph arising from closed neighborhoods of a graph, this approach asymptotically improves the time complexity of the previous result for computing $vc(H)$. Another consequence is a general lower bound on the {\it distinguishing transversal number } of $H$ that gives rise to applications in domination theory of graphs. To effectively apply the methods developed here, one needs to have good estimations of degeneracy, and its variation or reduced degeneracy which is introduced here.
