  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.

Combinatorics;Data Structures and Algorithms