Diversities and the Geometry of Hypergraphs

MaRDI QIDQ5167716zbMATH OpenFDO

Authors David Bryant, Paul F. Tupper

Publication date 1 July 2014

Full work available at URL https://arxiv.org/abs/1312.5408, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2541/0.html

zbMATH Keywords

diversitiesfractional Steiner tree packinghypergraphsmetric embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial optimization (90C27)

Abstract: The embedding of finite metrics in $el{l}_1$ has become a fundamental tool for both combinatorial optimization and large-scale data analysis. One important application is to network flow problems in which there is close relation between max-flow min-cut theorems and the minimal distortion embeddings of metrics into $el{l}_1$. Here we show that this theory can be generalized considerably to encompass Steiner tree packing problems in both graphs and hypergraphs. Instead of the theory of $el{l}_1$ metrics and minimal distortion embeddings, the parallel is the theory of diversities recently introduced by Bryant and Tupper, and the corresponding theory of $el{l}_1$ diversities and embeddings which we develop here.

Recommendations

• On fully diverse sets of geometric objects and graphs
• Maximum degree and diversity in intersecting hypergraphs
• scientific article; zbMATH DE number 850070
• The geometry connectivity of hypergraphs
• A geometric theory of hypergraph colouring
• Geometry of graph varieties
• Diversity vectors of balls in graphs and estimates of their components
• Graph varieties in high dimension
• Hypergraphs, entropy, and inequalities
• Dimensions of hypergraphs

Cited in

(14)

• Ultradiversification of diversities
• Automorphism groups of universal diversities
• A universal separable diversity
• Negative-type diversities, a multi-dimensional analogue of negative-type metrics
• scientific article; zbMATH DE number 6616703 (Why is no real title available?)
• Hard Metrics from Cayley Graphs of Abelian Groups
• Fraïssé limits for relational metric structures
• Diversity-normed spaces and diversity embeddings
• Diversities and the generalized circumradius
• Topological k-metrics
• Subtree distances, tight spans and diversities
• Topological \(k\)-metrics
• Constant distortion embeddings of symmetric diversities
• Ultradiversities and their spherical completeness

This page was built for publication: Diversities and the Geometry of Hypergraphs

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