Metraipolis › archive › dc_d5fb089195e2
Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity — arXiv:2608.17990
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.17990
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T15:33:29.389Z
- SHA-256 of the archived text
48d5ad21318e60501837015b9fce0e888d5f81d0ee5003e8a543d9ad4db2cea0- Stable URL of this page
https://metraipolis.com/documento/dc_d5fb089195e2
How to cite
Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity — arXiv:2608.17990 — arXiv (en), https://arxiv.org/abs/2608.17990 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d5fb089195e2 (Metraipolis archive dc_d5fb089195e2, sha256 48d5ad21318e60501837015b9fce0e888d5f81d0ee5003e8a543d9ad4db2cea0)
BibTeX
@misc{dcd5fb089195e2,
title = {Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity — arXiv:2608.17990},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.17990},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d5fb089195e2; sha256 48d5ad21318e60501837015b9fce0e888d5f81d0ee5003e8a543d9ad4db2cea0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.17990. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance $q^*(\lambda,\mu)=\min_{\sigma\in S_n}|E(G_\lambda)\triangle\sigma E(G_\mu)|$ makes that set a metric space. Its geometry and its complexity both issue from one identity: $q^*$ is an affine function of the maximum of $\lVert X\rVert_F^2$ over the contingency tables with margins $\lambda$ and $\mu$. Our main result is an explicit optimal embedding. The weighted dyadic sums of the Ferrers staircase, taken at the critical exponent $\frac14$, give a map $F_n$ into $\ell_2^{\,<4n}$ that acts on a single partition and is computable in $O(n)$ time, and its distortion is $\Theta(n^{1/4})$. That order is optimal, since $c_2(\mathcal K_n)=\Theta(n^{1/4})$: the lower half follows from a $\Theta(\sqrt n)$-dimensional Hamming cube of partitions and Enflo's theorem, so the determination needs no other external input. The analytic core is a scale-free inverse inequality for every integer sequence with $v(1)=v(N+1)=0$ and $v(s)-v(s+1)\in s\mathbb Z$: its critical dyadic energy is at least $\lVert v\rVert_1^2/(63504\sqrt{\mathrm{TV}(v)})$. Combinatorially the same identity yields two explicit $\ell_1$ models, the vertex-mass metric on sorted degree sequences with $\frac12\delta_1\le q^*<\frac32\delta_1$ and the block-energy metric with $q^*\le B\le2q^*-1$, both constants optimal; hence $c_1(\mathcal K_n)\le2$, and an $O(n\log n)$-time algorithm returns an alignment of cost below $2q^*$ carrying the certificate $q^*\in[\lceil(B+1)/2\rceil,B]$. Computationally, deciding $q^*(\lambda,\mu)\le Q$ is strongly NP-complete and admits no FPTAS, while the farthest alignment is polynomial-time solvable. The best constant in the inverse inequality remains open; an exactly solvable chirp family caps it at $\frac23$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-19 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Combinatorics (math.CO); Metric Geometry (math.MG).
Pagina del lavoro: https://arxiv.org/abs/2608.17990 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T15:28:41.544Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-19?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).