标题： 有向图的迹函数界及其应用 显示英文标题

标题： Bounding the trace function of a hypergraph with applications

摘要： 一个超图的迹函数的上界$H$被推导出来，并展示了其应用。 例如，VC 维度的新的上界对于$H$或者$vc(H)$来说是一个结果，并且可以在$H$具有有限退化性的情况下用于以多项式时间计算$vc(H)$。 这是之前未知的。 特别是，当$H$是一个来自图的闭邻域的超图时，这种方法在计算$vc(H)$时渐近地改进了先前结果的时间复杂度。 Another consequence is a general lower bound on the {\it 交叉数} 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. 显示英文摘要

摘要： 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.