Bounding the trace function of a hypergraph with applications

DOI10.1007/978-3-031-05375-7_8MaRDI QIDQ2089531zbMATH OpenOpenAlexFDO

Authors Farhad Shahrokhi

Publication date 22 October 2022

Full work available at URL https://arxiv.org/abs/2007.13016

zbMATH Keywords

transversal numberVC dimension of a hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 736296
• Edge Multiplicity and Other Trace Functions
• Bounding the vertex cover number of a hypergraph
• A note on improved upper bounds on the transversal number of hypergraphs

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Bounds on the identifying codes in trees
• Complexity results for identifying codes in planar graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Domination and location in acyclic graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Identifying codes in hereditary classes of graphs and VC-dimension
• Identifying codes in line graphs
• On a new class of codes for identifying vertices in graphs
• On limited nondeterminism and the complexity of the V-C dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Open neighborhood locating-dominating in trees
• The VC-dimension of set systems defined by graphs
• Total domination in graphs
• -nets and simplex range queries

Cited in

(1)

• scientific article; zbMATH DE number 736296 (Why is no real title available?)

This page was built for publication: Bounding the trace function of a hypergraph with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089531)