2020/07/25 by Farhad Shahrokhi, Shahrokhi, Farhad
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2007.13016
openalex publication_date 2020/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.