2019/02/22 by Farhad Shahrokhi, Shahrokhi, Farhad
Mathematics · Decision Sciences · #Graph theory and applications #Statistical Methods and Inference #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.1902.08366
Let H=(V, E) be a hypergraph on the vertex set V and edge set E⊆ 2V. We show that number of distinct \it traces on any k- subset of V, is most k. α(H), where α(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( α(H))+1 which was not known before. As a consequence vc(H) can be computed in computed in n^O( \rm log( δ(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 Ω(n/( α(G)), where α(G) is the degeneracy of G.