Metric hypergraphs and metric-line equivalences

DOI10.1016/J.DISC.2023.113473arXiv2207.11811OpenAlexW4368372142MaRDI QIDQ6405875FDOQ6405875

Authors: Vašek Chvátal, Ida Kantor 

Publication date: 24 July 2022

Abstract: In a metric space $M=(X,d)$, we say that $v$ is between $u$ and $w$ if $d(u,w)=d(u,v)+d(v,w)$. Taking all triples $u,v,w$ such that $v$ is between $u$ and $w$, one can associate a 3-uniform hypergraph with each finite metric space $M$. An effort to solve some basic open questions regarding finite metric spaces has motivated an endeavor to better understand these associated hypergraphs. In answer to a question posed in arXiv:1112.0376, we present an infinite family of hypergraphs that are non-metric, i.e., they don't arise from any metric space. Another basic structure associated with a metric space is a binary equivalence on the vertex set, where two pairs are in the same class if they induce the same line. An equivalence that comes from some metric space is a metric-line equivalence. We present an infinite family of so called obstacles, that is, binary equivalences that prevent an equivalence from being a metric-line equivalence.

Full work available at URL: https://doi.org/10.1016/j.disc.2023.113473

Recommendations

• Betweenness structures of small linear co-size
• Lines, betweenness and metric spaces
• Universal lines in graphs
• Graph metric with no proper inclusion between lines
• Lines in bipartite graphs and in 2‐metric spaces

Mathematics Subject Classification ID

Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

This page was built for publication: Metric hypergraphs and metric-line equivalences

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