Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity
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^*(λ,μ)=\min_{σ\in S_n}|E(G_λ)\triangleσE(G_μ)|$ 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 $λ$ and $μ$. 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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.17990
curl -X POST /api/v1/records/arxiv/2608.17990/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.17990/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'