A simple upper bound for trace function of a hypergraph with applications

Let $H=(V,E)$ be a hypergraph on the vertex set $V$ and edge set $E\subseteq 2^V$. We show that number of distinct {\it traces} on any $k-$ subset of $V$, is most $k\mathrm{.}\widehat{\alpha }(H)$, where $\widehat{\alpha }(H)$ is the {\it degeneracy} of $H$. The result significantly improves/generalizes some of related results. For instance, the $vc$ dimension $H$ (or $vc(H)$) is shown to be at most $\log (\widehat{\alpha }(H))+1$ which was not known before. As a consequence $vc(H)$ can be computed in computed in $n^{O( {\rm log}({\hat \delta}(H)))}$ time. When applied to the neighborhood systems of a graphs excluding a fixed minor, it reduces the known linear upper bound on the $VC$ dimension to a logarithmic one, in the size of the minor. When applied to the location domination and identifying code numbers of any $n$ vertex graph $G$, one gets the new lower bound of $\mathrm{\Omega }(n\mathrm{/}(\widehat{\alpha }(G))$, where ${\hat \alpha}(G)$isthedegeneracyof$G$.