pipette
ESEspañol

Euclidean Embeddings of Acyclic Hypergraph Line Metrics

Nicholas Popescu

Preprint

In the authors' words

We study Euclidean embeddings of higher-order line metrics arising from hypergraphs. For a fixed threshold \(s\geq 1\), the \(s\)-line graph \(L_s(H)\) has one vertex for each hyperedge of \(H\), with two hyperedges adjacent when they intersect in at least \(s\) vertices; its shortest-path metric is the native \(s\)-line metric. In the unrestricted setting, every finite graph occurs as the \(s\)-line graph of some hypergraph, so the worst-case Euclidean distortion is \(\Theta(\log n)\). We show that \(\alpha\)-acyclicity yields a sharp improvement to \(\Theta(\sqrt{\log\log n})\). Although the canonical join tree of an \(\alpha\)-acyclic hypergraph may have arbitrarily large stretch relative to the native metric, we prove that for every \(s\), the \(s\)-line graphs of \(\alpha\)-acyclic hypergraphs are exactly the dually chordal graphs. Using their constant-factor spanning-tree approximations together with classical tree-embedding bounds, we obtain an \(O(\sqrt{\log\log n})\) Euclidean embedding bound. We then show this is asymptotically tight by realizing every finite tree as the \(s\)-line graph of an \(\alpha\)-acyclic hypergraph. Thus, the worst-case distortion is \(\Theta(\sqrt{\log\log n})\), including for hypergraphs of rank at most \(3s+1\).

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.