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

Abstract

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.\hat{\alpha }(H)$, where $\hat{\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 (\hat{\alpha }(H))+1$ which was not known before. As a consequence $vc(H)$ can be computed in computed in $n^{O(\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 $\Omega (n/(\hat{\alpha }(G))$, where $\hat{\alpha }(G)$ is the degeneracy of $G$.

One of lemmas 2.2 is wrong