Euclidean Embeddings of Acyclic Hypergraph Line Metrics

We study Euclidean embeddings of higher-order line metrics arising from hypergraphs. For a fixed threshold $s\ge 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 $\mathrm{\Theta }(\log n)$. We show that $\alpha$-acyclicity yields a sharp improvement to $\mathrm{\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 $\mathrm{\Theta }(\sqrt{\log \log n})$, including for hypergraphs of rank at most $3s+1$.